| Publication | Date of Publication | Type |
|---|
New partitioning techniques and faster algorithms for approximate interval scheduling
| 2024-11-14 | Paper |
New partitioning techniques and faster algorithms for approximate interval scheduling
Algorithmica | 2024-10-07 | Paper |
Massively parallel algorithms for small subgraph counting
| 2024-08-22 | Paper |
Testing distributional assumptions of learning algorithms
| 2024-05-08 | Paper |
scientific article; zbMATH DE number 7829256 (Why is no real title available?)
| 2024-04-09 | Paper |
Sampling Multiple Edges Efficiently
| 2023-11-20 | Paper |
Towards a Decomposition-Optimal Algorithm for Counting and Sampling Arbitrary Motifs in Sublinear Time
| 2023-11-20 | Paper |
Approximating the Noise Sensitivity of a Monotone Boolean Function
| 2023-02-03 | Paper |
scientific article; zbMATH DE number 7650375 (Why is no real title available?)
| 2023-02-03 | Paper |
scientific article; zbMATH DE number 7650376 (Why is no real title available?)
| 2023-02-03 | Paper |
Local computation algorithms for spanners
| 2022-07-18 | Paper |
Fractional set cover in the streaming model
| 2021-07-28 | Paper |
Improved Local Computation Algorithm for Set Cover via Sparsification
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
Local Computation Algorithms
Proceedings of the 2019 ACM Symposium on Principles of Distributed Computing | 2021-01-20 | Paper |
Local algorithms for sparse spanning graphs
Algorithmica | 2020-02-28 | Paper |
Improved massively parallel computation algorithms for MIS, matching, and vertex cover
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
| 2019-05-10 | Paper |
Space-efficient local computation algorithms
| 2019-05-10 | Paper |
Testing halfspaces
| 2019-05-06 | Paper |
Sampling correctors
SIAM Journal on Computing | 2018-08-03 | Paper |
A local algorithm for constructing spanners in minor-free graphs
| 2018-04-19 | Paper |
Sublinear-time algorithms for counting star subgraphs via edge sampling
Algorithmica | 2018-04-06 | Paper |
Set cover in sub-linear time
| 2018-03-15 | Paper |
Testing shape restrictions of discrete distributions
Theory of Computing Systems | 2018-03-01 | Paper |
Testing shape restrictions of discrete distributions
| 2018-01-24 | Paper |
Can we locally compute sparse connected subgraphs?
| 2017-08-22 | Paper |
Local computation algorithms for graphs of non-constant degrees
Algorithmica | 2017-05-02 | Paper |
Constructing near spanning trees with few local inspections
Random Structures & Algorithms | 2017-04-18 | Paper |
Local algorithms for sparse spanning graphs
| 2017-03-22 | Paper |
Fast approximate PCPs
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | Paper |
A self-tester for linear functions over the integers with an elementary proof of correctness
Theory of Computing Systems | 2016-09-21 | Paper |
On the learnability of discrete distributions
Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 | 2016-09-01 | Paper |
Sampling correctors
Proceedings of the 2016 ACM Conference on Innovations in Theoretical Computer Science | 2016-04-15 | Paper |
Selective private function evaluation with applications to private statistics
Proceedings of the twentieth annual ACM symposium on Principles of distributed computing | 2016-03-04 | Paper |
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
scientific article; zbMATH DE number 6469129 (Why is no real title available?)
| 2015-08-03 | Paper |
Efficient learning of typical finite automata from random walks
Proceedings of the twenty-fifth annual ACM symposium on Theory of computing - STOC '93 | 2015-05-07 | Paper |
Testing similar means
SIAM Journal on Discrete Mathematics | 2015-04-17 | Paper |
Testing properties of collections of distributions
Theory of Computing | 2014-10-06 | Paper |
Random walks with “back buttons” (extended abstract)
Proceedings of the thirty-second annual ACM symposium on Theory of computing | 2014-09-26 | Paper |
Maintaining a large matching and a small vertex cover
Proceedings of the forty-second ACM symposium on Theory of computing | 2014-08-13 | Paper |
Testing probability distributions underlying aggregated data
Automata, Languages, and Programming | 2014-07-01 | Paper |
Testing closeness of discrete distributions
Journal of the ACM | 2014-02-17 | Paper |
Robust characterizations of \(k\)-wise independence over product spaces and related testing results
Random Structures & Algorithms | 2013-10-29 | Paper |
Local reconstructors and tolerant testers for connectivity and diameter
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2013-10-04 | Paper |
Testing Similar Means
Automata, Languages, and Programming | 2013-08-12 | Paper |
A local decision test for sparse polynomials
Information Processing Letters | 2012-03-27 | Paper |
Sublinear time algorithms
SIAM Journal on Discrete Mathematics | 2012-03-15 | Paper |
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Testing Halfspaces
SIAM Journal on Computing | 2010-11-04 | Paper |
Dynamic approximate vertex cover and maximum matching
Property Testing | 2010-10-12 | Paper |
Testing (Subclasses of) Halfspaces
Property Testing | 2010-10-12 | Paper |
Sublinear algorithms in the external memory model
Property Testing | 2010-10-12 | Paper |
Testing non-uniform \(k\)-wise independent distributions over product spaces (extended abstract)
Automata, Languages and Programming | 2010-09-07 | Paper |
A sublinear algorithm for weakly approximating edit distance
Proceedings of the thirty-fifth annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Testing monotone high-dimensional distributions
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Sublinear algorithms for testing monotone and unimodal distributions
Proceedings of the thirty-sixth annual ACM symposium on Theory of computing | 2010-08-15 | Paper |
Monotonicity testing over general poset domains
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
The complexity of approximating entropy
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
Testing ±1-weight halfspace
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
External Sampling
Automata, Languages and Programming | 2009-07-14 | Paper |
Testing monotone high‐dimensional distributions
Random Structures & Algorithms | 2009-03-04 | Paper |
scientific article; zbMATH DE number 5485485 (Why is no real title available?)
| 2009-01-05 | Paper |
Non‐Abelian homomorphism testing, and distributions close to their self‐convolutions
Random Structures & Algorithms | 2008-01-18 | Paper |
Tolerant property testing and distance approximation
Journal of Computer and System Sciences | 2006-10-05 | Paper |
scientific article; zbMATH DE number 5057523 (Why is no real title available?)
| 2006-09-26 | Paper |
The Complexity of Approximating the Entropy
SIAM Journal on Computing | 2005-10-28 | Paper |
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
SIAM Journal on Computing | 2005-10-28 | Paper |
Approximating the Minimum Spanning Tree Weight in Sublinear Time
SIAM Journal on Computing | 2005-09-16 | Paper |
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2005-08-25 | Paper |
Fast approximate PCPs for multidimensional bin-packing problems
Information and Computation | 2005-03-08 | Paper |
Fast approximate probabilistically checkable proofs
Information and Computation | 2004-10-04 | Paper |
scientific article; zbMATH DE number 2079416 (Why is no real title available?)
| 2004-07-28 | Paper |
scientific article; zbMATH DE number 1775411 (Why is no real title available?)
| 2004-01-14 | Paper |
scientific article; zbMATH DE number 2019621 (Why is no real title available?)
| 2003-12-17 | Paper |
On Testing Convexity and Submodularity
SIAM Journal on Computing | 2003-09-28 | Paper |
Random walks with ``back buttons
The Annals of Applied Probability | 2003-05-06 | Paper |
Testing membership in parenthesis languages
Random Structures & Algorithms | 2003-03-19 | Paper |
scientific article; zbMATH DE number 1833419 (Why is no real title available?)
| 2002-11-21 | Paper |
scientific article; zbMATH DE number 1756011 (Why is no real title available?)
| 2002-06-25 | Paper |
Checking approximate computations of polynomials and functional equations
SIAM Journal on Computing | 2002-04-23 | Paper |
Spot-checkers
Journal of Computer and System Sciences | 2001-05-28 | Paper |
Learning polynomials with queries: The highly noisy case
SIAM Journal on Discrete Mathematics | 2001-03-19 | Paper |
scientific article; zbMATH DE number 1256688 (Why is no real title available?)
| 1999-11-08 | Paper |
On the Robustness of Functional Equations
SIAM Journal on Computing | 1999-10-28 | Paper |
scientific article; zbMATH DE number 1306862 (Why is no real title available?)
| 1999-08-31 | Paper |
Reconstructing Algebraic Functions from Mixed Data
SIAM Journal on Computing | 1998-09-21 | Paper |
Efficient learning of typical finite automata from random walks
Information and Computation | 1998-06-02 | Paper |
Robust Characterizations of Polynomials with Applications to Program Testing
SIAM Journal on Computing | 1996-08-18 | Paper |
Designing checkers for programs that run in parallel
Algorithmica | 1996-08-13 | Paper |
scientific article; zbMATH DE number 799768 (Why is no real title available?)
| 1996-08-07 | Paper |
Learning fallible deterministic finite automata
Machine Learning | 1995-10-29 | Paper |
scientific article; zbMATH DE number 742944 (Why is no real title available?)
| 1995-04-11 | Paper |
Self-testing/correcting with applications to numerical problems
Journal of Computer and System Sciences | 1994-09-18 | Paper |
scientific article; zbMATH DE number 176552 (Why is no real title available?)
| 1993-05-18 | Paper |
Batch checking with applications to linear functions
Information Processing Letters | 1993-01-16 | Paper |
On the time and space complexity of computation using write-once memory or is pen really much worse than pencil?
Mathematical Systems Theory | 1992-09-26 | Paper |
A competitive 2-server algorithm
Information Processing Letters | 1992-06-27 | Paper |
scientific article; zbMATH DE number 4195192 (Why is no real title available?)
| 1991-01-01 | Paper |
The cover time of a regular expander is O(n log n)
Information Processing Letters | 1990-01-01 | Paper |
Reversing trains: A turn of the century sorting problem
Journal of Algorithms | 1989-01-01 | Paper |
