| Publication | Date of Publication | Type |
|---|
| Testing juntas [combinatorial property testing] | 2026-05-29 | Paper |
| Conflict-free colorings of simple geometric regions with applications to frequency assignment in cellular networks | 2026-05-29 | Paper |
| Testing polynomials over general fields | 2026-05-29 | Paper |
| Testing dynamic environments: back to basics | 2026-05-12 | Paper |
| Testing of clustering | 2026-05-08 | Paper |
| Testing C_k-freeness in bounded-arboricity graphs | 2026-01-14 | Paper |
| One-sided error testing of monomials and affine subspaces | 2026-01-08 | Paper |
| Testing monotonicity | 2025-10-29 | Paper |
| Approximately counting triangles in sublinear time | 2025-08-05 | Paper |
| On learning and testing dynamic environments | 2025-08-05 | Paper |
| Testing properties of sparse images | 2025-04-29 | Paper |
| Sample-based distance-approximation for subsequence-freeness | 2024-11-14 | Paper |
Sample-based distance-approximation for subsequence-freeness
Algorithmica | 2024-08-13 | Paper |
| Approximating the arboricity in sublinear time | 2024-07-19 | Paper |
Testing distributions of huge objects
TheoretiCS | 2024-07-03 | Paper |
| Almost optimal bounds for sublinear-time sampling of k-cliques in bounded arboricity graphs | 2024-06-24 | Paper |
scientific article; zbMATH DE number 7829310 (Why is no real title available?)
(available as arXiv preprint) | 2024-04-09 | Paper |
| scientific article; zbMATH DE number 7788360 (Why is no real title available?) | 2024-01-15 | Paper |
scientific article; zbMATH DE number 7788436 (Why is no real title available?)
(available as arXiv preprint) | 2024-01-15 | Paper |
A lower bound on the complexity of testing grained distributions
Computational Complexity | 2023-12-02 | Paper |
| Almost Optimal Distribution-Free Sample-Based Testing of k-Modality | 2023-10-31 | Paper |
| The Structure of Configurations in One-Dimensional Majority Cellular Automata: From Cell Stability to Configuration Periodicity | 2023-03-31 | Paper |
Optimal Distribution-Free Sample-Based Testing of Subsequence-Freeness with One-Sided Error
ACM Transactions on Computation Theory | 2022-09-24 | Paper |
A Probabilistic Error-Correcting Scheme that Provides Partial Secrecy
Lecture Notes in Computer Science | 2022-08-30 | Paper |
On the Relation Between the Relative Earth Mover Distance and the Variation Distance (an Exposition)
Lecture Notes in Computer Science | 2022-08-30 | Paper |
The arboricity captures the complexity of sampling edges
(available as arXiv preprint) | 2022-07-21 | Paper |
| The subgraph testing model | 2022-07-18 | Paper |
The subgraph testing model
ACM Transactions on Computation Theory | 2022-03-07 | Paper |
| Sublinear-time algorithms for approximating graph parameters | 2022-02-16 | Paper |
Property testing of the Boolean and binary rank
Theory of Computing Systems | 2021-12-18 | Paper |
| On the testability of graph partition properties | 2021-08-04 | Paper |
Testing bounded arboricity
ACM Transactions on Algorithms | 2021-05-03 | Paper |
Property testing of planarity in the \textsf{CONGEST} model
Distributed Computing | 2021-03-12 | Paper |
Faster sublinear approximation of the number of <i>k</i>-cliques in low-arboricity graphs
Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms | 2021-02-02 | Paper |
On approximating the number of k-cliques in sublinear time
SIAM Journal on Computing | 2020-08-18 | Paper |
| scientific article; zbMATH DE number 7204459 (Why is no real title available?) | 2020-05-27 | Paper |
Local algorithms for sparse spanning graphs
Algorithmica | 2020-02-28 | Paper |
Tolerant junta testing and the connection to submodular optimization and function isomorphism
ACM Transactions on Computation Theory | 2019-12-16 | Paper |
The power of an example: hidden set size approximation using group queries and conditional sampling
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
On sample-based testers
ACM Transactions on Computation Theory | 2019-12-06 | Paper |
Sublinear time estimation of degree distribution moments: the arboricity connection
SIAM Journal on Discrete Mathematics | 2019-11-25 | Paper |
Property testing of planarity in the \textsf{CONGEST} model
Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing | 2019-09-19 | Paper |
On approximating the number of k-cliques in sublinear time
Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing | 2019-08-22 | Paper |
Testing equivalence between distributions using conditional samples
Proceedings of the Twenty-Fifth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-06-20 | Paper |
The Boolean rank of the uniform intersection matrix and a family of its submatrices
Linear Algebra and its Applications | 2019-05-29 | Paper |
Exponentially improved algorithms and lower bounds for testing signed majorities
Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms | 2019-05-15 | Paper |
A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size
(available as arXiv preprint) | 2019-05-10 | Paper |
| A near-optimal sublinear-time algorithm for approximating the minimum vertex cover size | 2019-05-10 | Paper |
Approximating the distance to properties in bounded-degree and general sparse graphs
ACM Transactions on Algorithms | 2018-11-05 | Paper |
Testing Properties of Sparse Images
ACM Transactions on Algorithms | 2018-10-30 | Paper |
A quasi-polynomial time partition oracle for graphs with an excluded minor
ACM Transactions on Algorithms | 2018-10-30 | Paper |
Best of two local models: centralized local and distributed local algorithms
Information and Computation | 2018-09-27 | Paper |
On learning and testing dynamic environments
Journal of the ACM | 2018-05-17 | Paper |
A local algorithm for constructing spanners in minor-free graphs
(available as arXiv preprint) | 2018-04-19 | Paper |
| Tolerant junta testing and the connection to submodular optimization and function isomorphism | 2018-03-15 | Paper |
| Testing bounded arboricity | 2018-03-15 | Paper |
Approximately counting triangles in sublinear time
SIAM Journal on Computing | 2017-11-22 | Paper |
On Sample-Based Testers
Proceedings of the 2015 Conference on Innovations in Theoretical Computer Science | 2017-05-19 | Paper |
On the possibilities and limitations of pseudodeterministic algorithms
Proceedings of the 4th conference on Innovations in Theoretical Computer Science | 2017-05-16 | Paper |
Constructing near spanning trees with few local inspections
Random Structures & Algorithms | 2017-04-18 | Paper |
Local algorithms for sparse spanning graphs
(available as arXiv preprint) | 2017-03-22 | Paper |
Chinese remaindering with errors
Proceedings of the thirty-first annual ACM symposium on Theory of Computing | 2016-09-29 | 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 |
On universal learning algorithms
Information Processing Letters | 2016-05-26 | Paper |
Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
On approximating the number of relevant variables in a function
ACM Transactions on Computation Theory | 2015-09-24 | Paper |
Exponentially improved algorithms and lower bounds for testing signed majorities
Algorithmica | 2015-07-10 | Paper |
Testing probability distributions using conditional samples
SIAM Journal on Computing | 2015-06-11 | 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 metric properties
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
On proximity oblivious testing
Proceedings of the forty-first annual ACM symposium on Theory of computing | 2015-02-04 | Paper |
Approximating the distance to monotonicity in high dimensions
ACM Transactions on Algorithms | 2014-11-18 | Paper |
Finding cycles and trees in sublinear time
Random Structures & Algorithms | 2014-10-16 | Paper |
Deterministic stateless centralized local algorithms for bounded degree graphs
Algorithms - ESA 2014 | 2014-10-08 | Paper |
Testing properties of collections of distributions
Theory of Computing | 2014-10-06 | Paper |
| Counting stars and other small subgraphs in sublinear time | 2014-05-22 | Paper |
Testing Similar Means
Automata, Languages, and Programming | 2013-08-12 | Paper |
A quasi-polynomial time partition oracle for graphs with an excluded minor
Lecture Notes in Computer Science | 2013-08-06 | Paper |
Comparing the strength of query types in property testing: the case of \(k\)-colorability
Computational Complexity | 2013-04-11 | Paper |
Distribution-free testing for monomials with a sublinear number of queries
Theory of Computing | 2012-09-27 | Paper |
Counting stars and other small subgraphs in sublinear-time
SIAM Journal on Discrete Mathematics | 2012-03-15 | Paper |
Testing computability by width-two OBDDs
Theoretical Computer Science | 2012-03-13 | Paper |
Testing Eulerianity and connectivity in directed sparse graphs
Theoretical Computer Science | 2012-01-09 | Paper |
On testing expansion in bounded-degree graphs
Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation | 2011-08-19 | 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 |
On approximating the number of relevant variables in a function
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2011-08-17 | Paper |
Algorithmic aspects of property testing in the dense graphs model
SIAM Journal on Computing | 2011-07-29 | Paper |
On Proximity-Oblivious Testing
SIAM Journal on Computing | 2011-07-29 | Paper |
On the benefits of adaptivity in property testing of dense graphs
Algorithmica | 2010-11-08 | Paper |
Algorithmic Aspects of Property Testing in the Dense Graphs Model
Property Testing | 2010-10-12 | Paper |
Comparing the strength of query types in property testing: the case of testing \(k\)-colorability
Property Testing | 2010-10-12 | Paper |
Distribution-free testing algorithms for monomials with a sublinear number of queries
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
| scientific article; zbMATH DE number 5764842 (Why is no real title available?) | 2010-08-06 | Paper |
Testing computability by width-2 OBDDs where the variable order is unknown
Lecture Notes in Computer Science | 2010-05-28 | Paper |
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Lecture Notes in Computer Science | 2010-05-26 | Paper |
Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
Lecture Notes in Computer Science | 2010-05-26 | Paper |
On finding large conjunctive clusters.
Lecture Notes in Computer Science | 2010-03-23 | Paper |
Algorithmic and analysis techniques in property testing
Foundations and Trends® in Theoretical Computer Science | 2010-03-12 | Paper |
The hardness of the expected decision depth problem
Information Processing Letters | 2010-01-29 | Paper |
Testing Computability by Width Two OBDDs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Algorithmic Aspects of Property Testing in the Dense Graphs Model
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
Scheduling with conflicts: Online and offline algorithms
Journal of Scheduling | 2009-09-25 | Paper |
Testing Triangle-Freeness in General Graphs
SIAM Journal on Discrete Mathematics | 2009-05-27 | Paper |
| Property testing. A learning theory perspective | 2009-03-24 | Paper |
On the Benefits of Adaptivity in Property Testing of Dense Graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
Finding a dense-core in jellyfish graphs
Computer Networks | 2009-01-20 | Paper |
Testing Reed–Muller Codes
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
A Characterization of Low-Weight Words That Span Generalized Reed–Muller Codes
IEEE Transactions on Information Theory | 2008-12-21 | Paper |
Approximating average parameters of graphs
Random Structures & Algorithms | 2008-07-21 | Paper |
Finding a Dense-Core in Jellyfish Graphs
Algorithms and Models for the Web-Graph | 2008-04-11 | Paper |
Approximating the minimum vertex cover in sublinear time and a connection to distributed algorithms
Theoretical Computer Science | 2007-09-03 | Paper |
Approximating Average Parameters of Graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Distance Approximation in Bounded-Degree and General Sparse Graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Testing Polynomials over General Fields
SIAM Journal on Computing | 2007-06-26 | Paper |
Tolerant property testing and distance approximation
Journal of Computer and System Sciences | 2006-10-05 | Paper |
Testing of Clustering
SIAM Review | 2005-02-25 | Paper |
Tight Bounds for Testing Bipartiteness in General Graphs
SIAM Journal on Computing | 2005-02-21 | Paper |
Property testing and its connection to learning and approximation
Journal of the ACM | 2005-01-25 | Paper |
A new conceptual clustering framework
Machine Learning | 2005-01-19 | Paper |
Testing metric properties
Information and Computation | 2004-08-19 | Paper |
Testing juntas
Journal of Computer and System Sciences | 2004-08-06 | Paper |
Conflict-Free Colorings of Simple Geometric Regions with Applications to Frequency Assignment in Cellular Networks
SIAM Journal on Computing | 2004-01-08 | Paper |
Testing of Clustering
SIAM Journal on Discrete Mathematics | 2004-01-08 | 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 |
Errata for: ``On randomized one-round communication complexity''
Computational Complexity | 2003-08-26 | Paper |
Testing membership in parenthesis languages
Random Structures & Algorithms | 2003-03-19 | Paper |
Testing Basic Boolean Formulae
SIAM Journal on Discrete Mathematics | 2003-01-05 | Paper |
| scientific article; zbMATH DE number 1833419 (Why is no real title available?) | 2002-11-21 | Paper |
| scientific article; zbMATH DE number 1833420 (Why is no real title available?) | 2002-11-21 | Paper |
Testing the diameter of graphs
Random Structures & Algorithms | 2002-08-08 | Paper |
Testing properties of directed graphs: acyclicity and connectivity*
Random Structures & Algorithms | 2002-08-08 | Paper |
| scientific article; zbMATH DE number 1775414 (Why is no real title available?) | 2002-08-01 | Paper |
On disjoint chains of subsets
Journal of Combinatorial Theory. Series A | 2002-07-14 | Paper |
Property testing in bounded degree graphs
Algorithmica | 2002-03-07 | Paper |
| scientific article; zbMATH DE number 1670872 (Why is no real title available?) | 2001-11-11 | Paper |
Testing monotonicity
Combinatorica | 2001-06-12 | Paper |
Testing problems with sublearning sample complexity
Journal of Computer and System Sciences | 2001-04-17 | Paper |
| scientific article; zbMATH DE number 1559556 (Why is no real title available?) | 2001-02-28 | Paper |
| scientific article; zbMATH DE number 1857651 (Why is no real title available?) | 2001-01-01 | Paper |
Chinese remaindering with errors
IEEE Transactions on Information Theory | 2000-09-07 | Paper |
| scientific article; zbMATH DE number 1418269 (Why is no real title available?) | 2000-03-19 | Paper |
| scientific article; zbMATH DE number 1418268 (Why is no real title available?) | 2000-03-19 | Paper |
Computational Sample Complexity
SIAM Journal on Computing | 2000-03-19 | Paper |
A sublinear bipartiteness tester for bounded degree graphs
Combinatorica | 2000-02-21 | Paper |
On randomized one-round communication complexity
Computational Complexity | 1999-09-01 | Paper |
| scientific article; zbMATH DE number 1263236 (Why is no real title available?) | 1999-03-16 | Paper |
On the learnability and usage of acyclic probabilistic finite automata
Journal of Computer and System Sciences | 1998-11-10 | Paper |
Efficient learning of typical finite automata from random walks
Information and Computation | 1998-06-02 | Paper |
The power of amnesia: Learning probabilistic automata with variable memory length
Machine Learning | 1997-08-20 | Paper |
Agreement in the presence of faults, on networks of bounded degree
Information Processing Letters | 1997-02-27 | Paper |
Learning fallible deterministic finite automata
Machine Learning | 1995-10-29 | Paper |
