26 papers:
LATA-2015-NdioneLN #sublinear- Sublinear DTD Validity (AN, AL, JN), pp. 739–751.
ICML-2015-Bou-AmmarTE #learning #policy #sublinear- Safe Policy Search for Lifelong Reinforcement Learning with Sublinear Regret (HBA, RT, EE), pp. 2361–2369.
STOC-2014-HenzingerKN #algorithm #graph #reachability- Sublinear-time decremental algorithms for single-source reachability and shortest paths on directed graphs (MH, SK, DN), pp. 674–683.
- STOC-2013-RothblumVW #interactive #proving #proximity #sublinear
- Interactive proofs of proximity: delegating computation in sublinear time (GNR, SPV, AW), pp. 793–802.
ICALP-v2-2013-HenzingerKN #maintenance #network- Sublinear-Time Maintenance of Breadth-First Spanning Tree in Partially Dynamic Networks (MH, SK, DN), pp. 607–619.
- ICALP-v2-2013-LipmaaT #complexity #online #similarity #sublinear #testing
- Secure Equality and Greater-Than Tests with Sublinear Online Complexity (HL, TT), pp. 645–656.
- ICML-c2-2013-WestonMY #clustering #ranking #sublinear
- Label Partitioning For Sublinear Ranking (JW, AM, HY), pp. 181–189.
- STOC-2011-KoppartySY
- High-rate codes with sublinear-time decoding (SK, SS, SY), pp. 167–176.
ESOP-2010-LagoS #functional #programming #sublinear- Functional Programming in Sublinear Space (UDL, US), pp. 205–225.
AFL-J-2008-MalcherMP10 #array #bound- Sublinearly Space Bounded Iterative Arrays (AM, CM, BP), pp. 843–858.
- ICALP-v2-2009-IbrahimKYZ #sublinear
- Secure Function Collection with Sublinear Storage (MHI, AK, MY, HSZ), pp. 534–545.
- AFL-2008-MalcherMP #array #bound
- Sublinearly Space Bounded Iterative Arrays (AM, CM, BP), pp. 292–301.
- ICALP-A-2008-RodittyS #fault #sublinear
- All-Pairs Shortest Paths with a Sublinear Additive Error (LR, AS), pp. 622–633.
- ICALP-2005-BadoiuCIS #sublinear
- Facility Location in Sublinear Time (MB, AC, PI, CS), pp. 866–877.
- STOC-2004-BatuKR #algorithm #sublinear #testing
- Sublinear algorithms for testing monotone and unimodal distributions (TB, RK, RR), pp. 381–390.
- STOC-2004-CzumajS #metric
- Estimating the weight of metric minimum spanning trees in sublinear-time (AC, CS), pp. 175–183.
- ICALP-2004-CzumajS #approximate #clustering #random
- Sublinear-Time Approximation for Clustering Via Random Sampling (AC, CS), pp. 396–407.
- STOC-2003-BatuEKMRRS #algorithm #approximate #distance #edit distance #sublinear
- A sublinear algorithm for weakly approximating edit distance (TB, FE, JK, AM, SR, RR, RS), pp. 316–324.
- STOC-2003-ChazelleLM #algorithm #geometry #sublinear
- Sublinear geometric algorithms (BC, DL, AM), pp. 531–540.
- ICALP-2001-ChazelleRT #approximate #sublinear
- Approximating the Minimum Spanning Tree Weight in Sublinear Time (BC, RR, LT), pp. 190–200.
- ICALP-2000-BenderR #graph #sublinear #testing
- Testing Acyclicity of Directed Graphs in Sublinear Time (MAB, DR), pp. 809–820.
- STOC-1999-Indyk #algorithm #metric #problem #sublinear
- Sublinear Time Algorithms for Metric Space Problems (PI), pp. 428–434.
- STOC-1998-GoldreichR #graph #sublinear
- A Sublinear Bipartiteness Tester for Bunded Degree Graphs (OG, DR), pp. 289–298.
- STOC-1991-BarnesR #algorithm #polynomial #sublinear #using
- Deterministic Algorithms for Undirected s-t Connectivity Using Polynomial Time and Sublinear Space (Extended Abstract) (GB, WLR), pp. 43–53.
- STOC-1988-GurevichS #linear #nondeterminism #sublinear
- 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 #sublinear #transitive
- Two Familiar Transitive Closure Algorithms which Admit No Polynomial Time, Sublinear Space Implementations (MT), pp. 333–338.
