Eldar Fischer

CoRR, 2024

Extensions and Limits of the Specker-Blatter Theorem.

[BibT_eX]

[DOI]

Proceedings of the 32nd EACSL Annual Conference on Computer Science Logic, 2024

2023

Support Testing in the Huge Object Model.

[BibT_eX]

[DOI]

Tomer Adar

Amit Levi

CoRR, 2023

Refining the Adaptivity Notion in the Huge Object Model.

[BibT_eX]

[DOI]

Tomer Adar

CoRR, 2023

2022

Testing of Index-Invariant Properties in the Huge Object Model.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

Exploring the Gap Between Tolerant and Non-Tolerant Distribution Testing.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2022

2021

Ordered Graph Limits and Their Applications.

[BibT_eX]

[DOI]

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

2020

Hard Properties with (Very) Short PCPPs and Their Applications.

[BibT_eX]

[DOI]

Proceedings of the 11th Innovations in Theoretical Computer Science Conference, 2020

2019

Fast distributed algorithms for testing graph properties.

[BibT_eX]

[DOI]

Distributed Comput., 2019

Longest paths in 2-edge-connected cubic graphs.

[BibT_eX]

[DOI]

CoRR, 2019

Improving and Extending the Testing of Distributions for Shape-Restricted Properties.

[BibT_eX]

[DOI]

Yadu Vasudev

Algorithmica, 2019

2018

Earthmover Resilience and Testing in Ordered Structures.

[BibT_eX]

[DOI]

Omri Ben-Eliezer

Electron. Colloquium Comput. Complex., 2018

Limits of Ordered Graphs and Images.

[BibT_eX]

[DOI]

CoRR, 2018

Improved bounds for testing Dyck languages.

[BibT_eX]

[DOI]

Frédéric Magniez

Tatiana Starikovskaya

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Testing hereditary properties of ordered graphs and matrices.

[BibT_eX]

[DOI]

Omri Ben-Eliezer

Electron. Colloquium Comput. Complex., 2017

2016

Testing Read-Once Formula Satisfaction.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2016

2015

Trading query complexity for sample-based testing and multi-testing scalability}.

[BibT_eX]

[DOI]

Yadu Vasudev

Electron. Colloquium Comput. Complex., 2015

2014

Query Complexity Lower Bounds for Reconstruction of Codes.

[BibT_eX]

[DOI]

Sourav Chakraborty

Arie Matsliah

Theory Comput., 2014

Partial tests, universal tests and decomposability.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2014

2013

Some properties are not even partially testable.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

2012

On the query complexity of testing orientations for being Eulerian.

[BibT_eX]

[DOI]

ACM Trans. Algorithms, 2012

On the Power of Conditional Samples in Distribution Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Testing Low Complexity Affine-Invariant Properties.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Shachar Lovett

Electron. Colloquium Comput. Complex., 2012

Every locally characterized affine-invariant property is testable.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

Testing Formula Satisfaction.

[BibT_eX]

[DOI]

Proceedings of the Algorithm Theory - SWAT 2012, 2012

Junto-Symmetric Functions, Hypergraph Isomorphism and Crunching.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Hardness and algorithms for rainbow connection.

[BibT_eX]

[DOI]

J. Comb. Optim., 2011

PCP Characterizations of NP: Toward a Polynomially-Small Error-Probability.

[BibT_eX]

[DOI]

Comput. Complex., 2011

Testing Convexity Properties of Tree Colorings.

[BibT_eX]

[DOI]

Orly Yahalom

Algorithmica, 2011

Detecting and exploiting near-sortedness for efficient relational query evaluation.

[BibT_eX]

[DOI]

Proceedings of the Database Theory, 2011

Inflatable Graph Properties and Natural Property Tests.

[BibT_eX]

[DOI]

Eyal Rozenberg

Proceedings of the Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, 2011

2010

Approximate Hypergraph Partitioning and Applications.

[BibT_eX]

[DOI]

Arie Matsliah

Asaf Shapira

SIAM J. Comput., 2010

Approximate Satisfiability and Equivalence.

[BibT_eX]

[DOI]

Frédéric Magniez

Michel de Rougemont

SIAM J. Comput., 2010

Testing monotonicity of distributions over general partial orders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2010

Two-phase algorithms for the parametric shortest path problem

[BibT_eX]

[DOI]

Raphael Yuster

CoRR, 2010

Two-phase Algorithms for the Parametric Shortest Path Problem.

[BibT_eX]

[DOI]

Proceedings of the 27th International Symposium on Theoretical Aspects of Computer Science, 2010

New Results on Quantum Property Testing.

[BibT_eX]

[DOI]

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2010

2009

A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Hardness and Algorithms for Rainbow Connectivity.

[BibT_eX]

[DOI]

Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, 2009

Application of logic to combinatorial sequences and their recurrence relations.

[BibT_eX]

Tomer Kotek

Proceedings of the Model Theoretic Methods in Finite Combinatorics, 2009

2008

Testing Graph Isomorphism.

[BibT_eX]

[DOI]

Arie Matsliah

SIAM J. Comput., 2008

Counting truth assignments of formulas of bounded tree-width or clique-width.

[BibT_eX]

[DOI]

Elena V. Ravve

Discret. Appl. Math., 2008

Linear Recurrence Relations for Graph Polynomials.

[BibT_eX]

[DOI]

Proceedings of the Pillars of Computer Science, 2008

2007

Testing versus Estimation of Graph Properties.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Efficient Testing of Bipartite Graphs for Forbidden Induced Subgraphs.

[BibT_eX]

[DOI]

SIAM J. Comput., 2007

Testing of matrix-poset properties.

[BibT_eX]

[DOI]

Comb., 2007

Lower bounds for testing forbidden induced substructures in bipartite-graph-like combinatorial objects.

[BibT_eX]

[DOI]

Eyal Rozenberg

Proceedings of the Approximation, 2007

Testing <i>st</i> -Connectivity.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2007

2006

Tolerant Versus Intolerant Testing for Boolean Properties.

[BibT_eX]

[DOI]

Lance Fortnow

Theory Comput., 2006

2005

The Difficulty of Testing for Isomorphism against a Graph That Is Given in Advance.

[BibT_eX]

[DOI]

SIAM J. Comput., 2005

2004

Functions that have read-twice constant width branching programs are not necessarily testable.

[BibT_eX]

[DOI]

Jirí Sgall

Random Struct. Algorithms, 2004

On spectra of sentences of monadic second order logic with counting.

[BibT_eX]

[DOI]

J. Symb. Log., 2004

Testing juntas.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2004

Property and Equivalence Testing on Strings

[BibT_eX]

[DOI]

Frédéric Magniez

Michel de Rougemont

Electron. Colloquium Comput. Complex., 2004

2003

The Specker-Blatter theorem does not hold for quaternary relations.

[BibT_eX]

[DOI]

J. Comb. Theory, Ser. A, 2003

The Specker-Blatter Theorem Revisited.

[BibT_eX]

[DOI]

Proceedings of the Computing and Combinatorics, 9th Annual International Conference, 2003

2002

Monotonicity testing over general poset domains.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Functions that have Read-Twice Constant Width Branching Programs are not Necessarily Testable.

[BibT_eX]

[DOI]

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Parent-Identifying Codes.

[BibT_eX]

[DOI]

Mario Szegedy

J. Comb. Theory, Ser. A, 2001

On the strength of comparisons in property testing

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2001

The Art of Uninformed Decisions.

[BibT_eX]

Bull. EATCS, 2001

Testing of matrix properties.

[BibT_eX]

[DOI]

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

Testing graphs for colorable properties.

[BibT_eX]

[DOI]

Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, 2001

Testing Random Variables for Independence and Identity.

[BibT_eX]

[DOI]

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

2000

Testing graphs for colorability properties

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2000

Efficient Testing of Large Graphs.

[BibT_eX]

[DOI]

Comb., 2000

1999

Variants of the Hajnal-Szemerédi Theorem.

[BibT_eX]

[DOI]

J. Graph Theory, 1999

Cycle factors in dense graphs.

[BibT_eX]

[DOI]

Discret. Math., 1999

Induced Complete h-partite Graphs in Dense Clique-less Graphs.

[BibT_eX]

[DOI]

Electron. J. Comb., 1999

Refining the Graph Density Condition for the Existence of Almost K-factors.

[BibT_eX]

Ars Comb., 1999

1998

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 1998

1996

2-factors in dense graphs.

[BibT_eX]

[DOI]