| Publication | Date of Publication | Type |
|---|
Strongly sublinear algorithms for testing pattern freeness
TheoretiCS | 2024-07-03 | Paper |
| Strongly sublinear algorithms for testing pattern freeness | 2024-06-24 | Paper |
| Parameterized convexity testing | 2024-05-14 | Paper |
scientific article; zbMATH DE number 7759300 (Why is no real title available?)
(available as arXiv preprint) | 2023-11-02 | Paper |
Large simple \(d\)-cycles in simplicial complexes
Israel Journal of Mathematics | 2023-10-12 | Paper |
Self-simulation for the Passive Optical Star model
Lecture Notes in Computer Science | 2023-05-08 | Paper |
| Testing of graph properties | 2022-12-21 | Paper |
Hamiltonian and pseudo-Hamiltonian cycles and fillings in simplicial complexes
Journal of Combinatorial Theory. Series B | 2021-07-06 | Paper |
On the characterization of 1-sided error strongly testable graph properties for bounded-degree graphs
Computational Complexity | 2020-03-06 | Paper |
| Query Complexity | 2020-03-04 | Paper |
On connectivity of the facet graphs of simplicial complexes
Israel Journal of Mathematics | 2019-12-17 | Paper |
Testing for forbidden order patterns in an array
Random Structures & Algorithms | 2019-11-07 | Paper |
| Contractors' minimum spanning tree | 2019-09-19 | Paper |
| On multiplicative \(\lambda\)-approximations and some geometric applications | 2019-05-10 | Paper |
Extremal hypercuts and shadows of simplicial complexes
Israel Journal of Mathematics | 2019-02-07 | Paper |
A lower bound on the distortion of embedding planar metrics into Euclidean space
Proceedings of the eighteenth annual symposium on Computational geometry | 2018-11-23 | Paper |
Testing for forbidden order patterns in an array
Proceedings of the Twenty-Eighth Annual ACM-SIAM Symposium on Discrete Algorithms | 2018-07-16 | Paper |
| Every property of outerplanar graphs is testable | 2018-04-19 | Paper |
| scientific article; zbMATH DE number 6472652 (Why is no real title available?) | 2015-08-14 | Paper |
| Boundaries of Hypertrees, and Hamiltonian Cycles in Simplicial Complexes | 2015-07-16 | Paper |
Hats, auctions and derandomization
Random Structures & Algorithms | 2015-05-29 | Paper |
Testing of matrix properties
Proceedings of the thirty-third annual ACM symposium on Theory of computing | 2015-02-27 | Paper |
A combinatorial characterization of the testable graph properties, it's all about regularity
Proceedings of the thirty-eighth annual ACM symposium on Theory of Computing | 2014-11-25 | Paper |
On the query complexity of testing orientations for being Eulerian
ACM Transactions on Algorithms | 2014-09-09 | Paper |
| Extremal problems on shadows and hypercuts in simplicial complexes | 2014-08-04 | Paper |
Every property of hyperfinite graphs is testable
Proceedings of the forty-third annual ACM symposium on Theory of computing | 2014-06-05 | Paper |
On multiplicative \(\lambda\)-approximations and some geometric applications
SIAM Journal on Computing | 2013-09-25 | Paper |
Every property of hyperfinite graphs is testable
SIAM Journal on Computing | 2013-09-25 | Paper |
The Stackelberg minimum spanning tree game on planar and bounded-treewidth graphs
Journal of Combinatorial Optimization | 2013-04-08 | Paper |
Treewidth governs the complexity of target set selection
Discrete Optimization | 2012-10-16 | Paper |
Hierarchy theorems for property testing
Computational Complexity | 2012-06-26 | Paper |
Local versus global properties of metric spaces
SIAM Journal on Computing | 2012-05-30 | Paper |
Constant approximation algorithms for embedding graph metrics into trees and outerplanar graphs
Discrete & Computational Geometry | 2012-03-02 | Paper |
Hard metrics from Cayley graphs of abelian groups
Theory of Computing | 2011-05-24 | Paper |
Testing periodicity
Algorithmica | 2011-05-10 | Paper |
LCS approximation via embedding into locally non-repetitive strings
Information and Computation | 2011-04-28 | Paper |
The Stackelberg minimum spanning tree game
Algorithmica | 2011-03-02 | Paper |
Computing in fault tolerant broadcast networks and noisy decision trees
Random Structures & Algorithms | 2010-11-09 | Paper |
Property testing of massively parametrized problems -- a survey
Property Testing | 2010-10-12 | Paper |
Hierarchy theorems for property testing
Property Testing | 2010-10-12 | Paper |
Constant Approximation Algorithms for Embedding Graph Metrics into Trees and Outerplanar Graphs
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2010-09-10 | Paper |
Testing versus estimation of graph properties
Proceedings of the thirty-seventh annual ACM symposium on Theory of computing | 2010-08-16 | Paper |
Local versus global properties of metric spaces
Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm - SODA '06 | 2010-08-16 | Paper |
Monotonicity testing over general poset domains
Proceedings of the thiry-fourth annual ACM symposium on Theory of computing | 2010-08-05 | Paper |
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity
SIAM Journal on Computing | 2010-03-17 | Paper |
Lower bounds for testing Euclidean minimum spanning trees
Information Processing Letters | 2010-01-29 | Paper |
A new derandomization of auctions
Algorithmic Game Theory | 2009-12-01 | Paper |
Hierarchy Theorems for Property Testing
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-10-28 | Paper |
LCS Approximation via Embedding into Local Non-repetitive Strings
Combinatorial Pattern Matching | 2009-07-07 | Paper |
Testing st-Connectivity
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2009-02-17 | Paper |
The Stackelberg Minimum Spanning Tree Game
Lecture Notes in Computer Science | 2009-02-17 | Paper |
On the Query Complexity of Testing Orientations for Being Eulerian
Lecture Notes in Computer Science | 2008-11-27 | Paper |
Quantum Property Testing
SIAM Journal on Computing | 2008-10-28 | Paper |
Space complexity vs. query complexity
Computational Complexity | 2008-08-20 | Paper |
Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs
SIAM Journal on Computing | 2008-06-19 | Paper |
Testing versus Estimation of Graph Properties
SIAM Journal on Computing | 2008-04-22 | Paper |
Testing of matrix-poset properties
Combinatorica | 2007-11-12 | Paper |
Hard Metrics from Cayley Graphs of Abelian Groups
STACS 2007 | 2007-09-03 | Paper |
Space Complexity vs. Query Complexity
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques | 2007-08-28 | Paper |
Robust polynomials and quantum algorithms
Theory of Computing Systems | 2007-08-23 | Paper |
Partitioning multi-dimensional sets in a small number of ``uniform parts
European Journal of Combinatorics | 2006-12-07 | Paper |
Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
Lecture Notes in Computer Science | 2006-07-07 | Paper |
Embedding k-Outerplanar Graphs into l1
SIAM Journal on Discrete Mathematics | 2006-06-01 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
STACS 2005
Lecture Notes in Computer Science | 2005-12-02 | Paper |
Approximating the Weight of the Euclidean Minimum Spanning Tree in Sublinear Time
SIAM Journal on Computing | 2005-10-28 | Paper |
Cuts, trees and \(\ell_1\)-embeddings of graphs
Combinatorica | 2005-02-14 | Paper |
| scientific article; zbMATH DE number 2079381 (Why is no real title available?) | 2004-07-28 | Paper |
| scientific article; zbMATH DE number 2079416 (Why is no real title available?) | 2004-07-28 | Paper |
scientific article; zbMATH DE number 2079374 (Why is no real title available?)
(available as arXiv preprint) | 2004-07-28 | Paper |
Functions that have read‐twice constant width branching programs are not necessarily testable
Random Structures & Algorithms | 2004-03-29 | Paper |
A lower bound on the distortion of embedding planar metrics into Euclidean space
Discrete & Computational Geometry | 2003-03-17 | Paper |
Communication-processor tradeoffs in a limited resources PRAM
Algorithmica | 2002-12-01 | Paper |
Testing Membership in Languages that Have Small Width Branching Programs
SIAM Journal on Computing | 2002-09-29 | Paper |
Regular languages are testable with a constant number of queries
SIAM Journal on Computing | 2001-03-19 | Paper |
| scientific article; zbMATH DE number 1256775 (Why is no real title available?) | 2000-05-22 | Paper |
Self-Simulation for the Passive Optical Star
Journal of Algorithms | 2000-03-16 | Paper |
Optimal Search in Trees
SIAM Journal on Computing | 1999-10-28 | Paper |
Geometric approach for optimal routing on a mesh with buses
Journal of Computer and System Sciences | 1997-08-03 | Paper |
Randomized Single-Target Hot-Potato Routing
Journal of Algorithms | 1997-07-06 | Paper |
Lower Bounds on Formula Size of Boolean Functions Using Hypergraph Entropy
SIAM Journal on Discrete Mathematics | 1996-07-02 | Paper |
Decision trees with Boolean threshold queries
Journal of Computer and System Sciences | 1996-03-19 | Paper |
Search Problems in the Decision Tree Model
SIAM Journal on Discrete Mathematics | 1995-08-06 | Paper |
Non-deterministic communication complexity with few witnesses
Journal of Computer and System Sciences | 1994-11-06 | Paper |
Combinatorial characterization of read-once formulae
Discrete Mathematics | 1993-10-24 | Paper |
| scientific article; zbMATH DE number 176867 (Why is no real title available?) | 1993-05-18 | Paper |
On read-once threshold formulae and their randomized decision tree complexity
Theoretical Computer Science | 1993-05-16 | Paper |
Private vs. common random bits in communication complexity
Information Processing Letters | 1992-06-27 | Paper |
On grid intersection graphs
Discrete Mathematics | 1992-06-25 | Paper |
Approximation algorithms for covering a graph by vertex-disjoint paths of maximum total weight
Networks | 1990-01-01 | Paper |
