Sublinear Time Algorithms
From MaRDI portal
Publication:3225140
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
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
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
