Sublinear Time Algorithms

DOI10.1137/100791075zbMath1252.68126OpenAlexW2026244324MaRDI QIDQ3225140

Ronitt Rubinfeld, Asaf Shapira

Publication date: 15 March 2012

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: http://hdl.handle.net/1721.1/70521

zbMATH Keywords

approximation algorithmsrandomized algorithmsproperty testingsublinear time algorithms

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87)

Related Items (25)

Testing Lipschitz functions on hypergrid domains ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata ⋮ New techniques and tighter bounds for local computation algorithms ⋮ Fast domino tileability ⋮ An optimal tester for \(k\)-linear ⋮ Descriptive complexity of deterministic polylogarithmic time and space ⋮ A tight bound for Green's arithmetic triangle removal lemma in vector spaces ⋮ On Approximating the Stationary Distribution of Time-reversible Markov Chains ⋮ Unavoidable tournaments ⋮ On the predictability of the abelian sandpile model ⋮ An optimal tester for \(k\)-Linear ⋮ Detecting curved edges in noisy images in sublinear time ⋮ Range partitioning within sublinear time: algorithms and lower bounds ⋮ Deterministic vs non-deterministic graph property testing ⋮ Testing outerplanarity of bounded degree graphs ⋮ Boosting distinct random sampling for basic counting on the union of distributed streams ⋮ Dynamic graph stream algorithms in \(o(n)\) space ⋮ On approximating the stationary distribution of time-reversible Markov chains ⋮ Efficient approximation schemes for economic lot-sizing in continuous time ⋮ Constant-Query Testability of Assignments to Constraint Satisfaction Problems ⋮ Multiscale Matrix Sampling and Sublinear-Time PageRank Computation ⋮ Detection of Long Edges on a Computational Budget: A Sublinear Approach ⋮ Partially Symmetric Functions Are Efficiently Isomorphism Testable ⋮ Linear-time parameterized algorithms with limited local resources ⋮ Sublinear-Time Language Recognition and Decision by One-Dimensional Cellular Automata

This page was built for publication: Sublinear Time Algorithms