## Tag #sublinear

### 26 papers:

- ICML-2019-AcharyaSFS #communication #distributed #learning
- Distributed Learning with Sublinear Communication (JA, CDS, DJF, KS), pp. 40–50.
- ICML-2019-LeiHKT #nearest neighbour
- Sublinear Time Nearest Neighbor Search over Generalized Weighted Space (YL, QH, MSK, AKHT), pp. 3773–3781.
- ICML-2019-LiCW #algorithm #classification #kernel #linear #quantum
- Sublinear quantum algorithms for training linear and kernel-based classifiers (TL, SC, XW), pp. 3815–3824.
- ICML-2019-Upadhyay #algorithm
- Sublinear Space Private Algorithms Under the Sliding Window Model (JU), pp. 6363–6372.
- ICML-2018-ShazeerS #adaptation #learning #memory management #named
- Adafactor: Adaptive Learning Rates with Sublinear Memory Cost (NS, MS), pp. 4603–4611.
- KDD-2017-Cohen #sketching #statistics
- HyperLogLog Hyperextended: Sketches for Concave Sublinear Frequency Statistics (EC), pp. 105–114.
- ICML-2016-ChoromanskiS #kernel
- Recycling Randomness with Structure for Sublinear time Kernel Expansions (KC, VS), pp. 2502–2510.
- LATA-2015-NdioneLN
- Sublinear DTD Validity (AN, AL, JN), pp. 739–751.
- ICML-2015-Bou-AmmarTE #learning #policy
- Safe Policy Search for Lifelong Reinforcement Learning with Sublinear Regret (HBA, RT, EE), pp. 2361–2369.
- ICALP-v2-2013-LipmaaT #complexity #online #similarity #testing
- Secure Equality and Greater-Than Tests with Sublinear Online Complexity (HL, TT), pp. 645–656.
- ICML-c2-2013-WestonMY #clustering #ranking
- Label Partitioning For Sublinear Ranking (JW, AM, HY), pp. 181–189.
- STOC-2013-RothblumVW #interactive #proving #proximity
- Interactive proofs of proximity: delegating computation in sublinear time (GNR, SPV, AW), pp. 793–802.
- ESOP-2010-LagoS #functional #programming
- Functional Programming in Sublinear Space (UDL, US), pp. 205–225.
- ICALP-v2-2009-IbrahimKYZ
- Secure Function Collection with Sublinear Storage (MHI, AK, MY, HSZ), pp. 534–545.
- ICALP-A-2008-RodittyS #fault
- All-Pairs Shortest Paths with a Sublinear Additive Error (LR, AS), pp. 622–633.
- ICALP-2005-BadoiuCIS
- Facility Location in Sublinear Time (MB, AC, PI, CS), pp. 866–877.
- STOC-2004-BatuKR #algorithm #testing
- Sublinear algorithms for testing monotone and unimodal distributions (TB, RK, RR), pp. 381–390.
- STOC-2003-BatuEKMRRS #algorithm #approximate #distance #edit distance
- A sublinear algorithm for weakly approximating edit distance (TB, FE, JK, AM, SR, RR, RS), pp. 316–324.
- STOC-2003-ChazelleLM #algorithm #geometry
- Sublinear geometric algorithms (BC, DL, AM), pp. 531–540.
- ICALP-2001-ChazelleRT #approximate
- Approximating the Minimum Spanning Tree Weight in Sublinear Time (BC, RR, LT), pp. 190–200.
- ICALP-2000-BenderR #graph #testing
- Testing Acyclicity of Directed Graphs in Sublinear Time (MAB, DR), pp. 809–820.
- STOC-1999-Indyk #algorithm #metric #problem
- Sublinear Time Algorithms for Metric Space Problems (PI), pp. 428–434.
- STOC-1998-GoldreichR #graph
- A Sublinear Bipartiteness Tester for Bunded Degree Graphs (OG, DR), pp. 289–298.
- STOC-1991-BarnesR #algorithm #polynomial #using
- Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (GB, WLR), pp. 43–53.
- STOC-1988-GurevichS #linear #nondeterminism
- Nondeterministic Linear-Time Tasks May Require Substantially Nonlinear Deterministic Time in the Case of Sublinear Work Space (YG, SS), pp. 281–289.
- STOC-1980-Tompa80a #algorithm #implementation #polynomial #transitive
- Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations (MT), pp. 333–338.