Eldar Fischer

Amit Levi

CoRR, March, 2025

Testing vs Estimation for Index-Invariant Properties in the Huge Object Model.

[BibT_eX]

[DOI]

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

2024

A basic lower bound for property testing.

[BibT_eX]

[DOI]

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

Improved Bounds for High-Dimensional Equivalence and Product Testing Using Subcube Queries.

[BibT_eX]

[DOI]

Amit Levi

Proceedings of the Approximation, 2024

Support Testing in the Huge Object Model.

[BibT_eX]

[DOI]

Amit Levi

Proceedings of the Approximation, 2024

Refining the Adaptivity Notion in the Huge Object Model.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2024

2023

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

[BibT_eX]

[DOI]

Proceedings of the Thirty Sixth Annual Conference on Learning Theory, 2023

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

Longest paths in 2-edge-connected cubic graphs.

[BibT_eX]

[DOI]

CoRR, 2019

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

Earthmover Resilience and Testing in Ordered Structures.

[BibT_eX]

[DOI]

Omri Ben-Eliezer

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

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

[BibT_eX]

[DOI]

Yadu Vasudev

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Testing Hereditary Properties of Ordered Graphs and Matrices.

[BibT_eX]

[DOI]

Omri Ben-Eliezer

Proceedings of the 58th IEEE Annual Symposium on Foundations of Computer Science, 2017

2016

Testing Read-Once Formula Satisfaction.

[BibT_eX]

[DOI]

ACM Trans. Comput. Theory, 2016

Fast Distributed Algorithms for Testing Graph Properties.

[BibT_eX]

[DOI]

Proceedings of the Distributed Computing - 30th International Symposium, 2016

2015

Trading Query Complexity for Sample-Based Testing and Multi-testing Scalability.

[BibT_eX]

[DOI]

Yadu Vasudev

Proceedings of the IEEE 56th Annual Symposium on Foundations of Computer Science, 2015

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

Every locally characterized affine-invariant property is testable.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing Conference, 2013

Testing Low Complexity Affine-Invariant Properties.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Shachar Lovett

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

On the power of conditional samples in distribution testing.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Theoretical Computer Science, 2013

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

Query Complexity Lower Bounds for Reconstruction of Codes.

[BibT_eX]

[DOI]

Sourav Chakraborty

Arie Matsliah

Proceedings of the Innovations in Computer Science, 2011

Testing monotonicity of distributions over general partial orders.

[BibT_eX]

[DOI]

Proceedings of the Innovations in Computer Science, 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

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

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

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

On the Query Complexity of Testing Orientations for Being Eulerian.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2008

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

Testing Convexity Properties of Tree Colorings.

[BibT_eX]

[DOI]

Orly Yahalom

Proceedings of the STACS 2007, 2007

Approximate Hypergraph Partitioning and Applications.

[BibT_eX]

[DOI]

Arie Matsliah

Asaf Shapira

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 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

A combinatorial characterization of the testable graph properties: it's all about regularity.

[BibT_eX]

[DOI]

Proceedings of the 38th Annual ACM Symposium on Theory of Computing, 2006

Testing graph isomorphism.

[BibT_eX]

[DOI]

Arie Matsliah

Proceedings of the Seventeenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2006

Approximate Satisfiability and Equivalence.

[BibT_eX]

[DOI]

Frédéric Magniez

Michel de Rougemont

Proceedings of the 21th IEEE Symposium on Logic in Computer Science (LICS 2006), 2006

2005

Testing versus estimation of graph properties.

[BibT_eX]

[DOI]

Proceedings of the 37th Annual ACM Symposium on Theory of Computing, 2005

Tolerant Versus Intolerant Testing for Boolean Properties.

[BibT_eX]

[DOI]

Lance Fortnow

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 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

Property and Equivalence Testing on Strings

[BibT_eX]

[DOI]

Frédéric Magniez

Michel de Rougemont

Electron. Colloquium Comput. Complex., 2004

The difficulty of testing for isomorphism against a graph that is given in advance.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

2003

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

[BibT_eX]

[DOI]

J. Comb. Theory 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

Testing Juntas.

[BibT_eX]

[DOI]

Proceedings of the 43rd Symposium on Foundations of Computer Science, 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 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

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

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

[BibT_eX]

[DOI]

Proceedings of the Thirty-First Annual ACM Symposium on Theory of Computing, 1999

Efficient Testing of Large Graphs.

[BibT_eX]

[DOI]

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1996

2-factors in dense graphs.

[BibT_eX]

[DOI]