Asaf Shapira

Yevgeny Levanzov

CoRR, February, 2025

Polynomial property testing.

[BibT_eX]

[DOI]

Comput. Sci. Rev., 2025

A Fast Coloring Oracle for Average Case Hypergraphs.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2025

2024

Trimming Forests Is Hard (Unless They Are Made of Stars).

[BibT_eX]

[DOI]

Yevgeny Levanzov

SIAM J. Discret. Math., 2024

Bounding the number of odd paths in planar graphs via convex optimization.

[BibT_eX]

[DOI]

Asaf Cohen Antonir

J. Graph Theory, 2024

A generalisation of Varnavides's theorem.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2024

A Tight Bound for Testing Partition Properties.

[BibT_eX]

[DOI]

Henrique Stagni

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

2023

A new bound for the Brown-Erdős-Sós problem.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2023

On Rödl's Theorem for Cographs.

[BibT_eX]

[DOI]

Electron. J. Comb., 2023

Testing Versus Estimation of Graph Properties, Revisited.

[BibT_eX]

[DOI]

Nick Kushnir

Proceedings of the Approximation, 2023

2022

Counting Subgraphs in Degenerate Graphs.

[BibT_eX]

[DOI]

J. ACM, 2022

Every Orientation of a $4$-Chromatic Graph has a Non-Bipartite Acyclic Subgraph.

[BibT_eX]

[DOI]

Electron. J. Comb., 2022

Counting Homomorphic Cycles in Degenerate Graphs.

[BibT_eX]

[DOI]

Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, 2022

2021

Quasirandom Graphs and the Pantograph Equation.

[BibT_eX]

[DOI]

Mykhaylo Tyomkyn

Am. Math. Mon., 2021

On Erdős's Method for Bounding the Partition Function.

[BibT_eX]

[DOI]

Asaf Cohen Antonir

Am. Math. Mon., 2021

Two Erdős-Hajnal-type theorems in hypergraphs.

[BibT_eX]

[DOI]

Michal Amir

Mykhaylo Tyomkyn

J. Comb. Theory B, 2021

Tournament Quasirandomness from Local Counting.

[BibT_eX]

[DOI]

Comb., 2021

2020

Counting Subgraphs in Degenerate Graphs.

[BibT_eX]

[DOI]

Yevgeny Levanzov

Electron. Colloquium Comput. Complex., 2020

The Induced Removal Lemma in Sparse Graphs.

[BibT_eX]

[DOI]

Shachar Sapir

Comb. Probab. Comput., 2020

A quantitative Lovász criterion for Property B.

[BibT_eX]

[DOI]

Asaf Ferber

Comb. Probab. Comput., 2020

Testing Linear Inequalities of Subgraph Statistics.

[BibT_eX]

[DOI]

Henrique Stagni

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

2019

The removal lemma for tournaments.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2019

Efficient Removal Without Efficient Regularity.

[BibT_eX]

[DOI]

Comb., 2019

Testing graphs against an unknown distribution.

[BibT_eX]

[DOI]

Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, 2019

2018

A generalized Turán problem and its applications.

[BibT_eX]

[DOI]

Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, 2018

Efficient Testing without Efficient Regularity.

[BibT_eX]

[DOI]

Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

2017

Removal lemmas with polynomial bounds.

[BibT_eX]

[DOI]

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

2016

Unavoidable tournaments.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2016

A short proof of Gowers' lower bound for the regularity lemma.

[BibT_eX]

[DOI]

Guy Moshkovitz

Comb., 2016

2015

Exact bounds for some hypergraph saturation problems.

[BibT_eX]

[DOI]

Guy Moshkovitz

Subrahmanyam Kalyanasundaram

J. Comb. Theory B, 2015

Constructing Near Spanning Trees with Few Local Inspections.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

An Optimal Algorithm for Finding Frieze-Kannan Regular Partitions.

[BibT_eX]

[DOI]

Domingos Dellamonica Jr.

Daniel M. Martin

Vojtech Rödl

Comb. Probab. Comput., 2015

Small complete minors above the extremal edge density.

[BibT_eX]

[DOI]

Benny Sudakov

Comb., 2015

Decomposing a Graph Into Expanding Subgraphs.

[BibT_eX]

[DOI]

Guy Moshkovitz

Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, 2015

2014

Forcing $k$-repetitions in Degree Sequences.

[BibT_eX]

[DOI]

Yair Caro

Subrahmanyam Kalyanasundaram

Electron. J. Comb., 2014

2013

A Note on Even Cycles and Quasirandom Tournaments.

[BibT_eX]

[DOI]

J. Graph Theory, 2013

Deterministic vs Non-deterministic Graph Property Testing.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2013

Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs.

[BibT_eX]

[DOI]

Comb. Probab. Comput., 2013

2012

The quasi-randomness of hypergraph cut properties.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2012

Finding Cycles and Trees in Sublinear Time.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2012

A Note on the Balanced ST-Connectivity

[BibT_eX]

[DOI]

Shiva Kintali

CoRR, 2012

Testing odd-cycle-freeness in Boolean functions.

[BibT_eX]

[DOI]

Proceedings of the Twenty-Third Annual ACM-SIAM Symposium on Discrete Algorithms, 2012

2011

Sublinear Time Algorithms.

[BibT_eX]

[DOI]

Ronitt Rubinfeld

Electron. Colloquium Comput. Complex., 2011

Randomized greedy: new variants of some classic approximation algorithms.

[BibT_eX]

[DOI]

Kevin P. Costello

Subrahmanyam Kalyanasundaram

Prasad Tetali

Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma.

[BibT_eX]

[DOI]

Domingos Dellamonica Jr.

Daniel M. Martin

Vojtech Rödl

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

2010

On the density of a graph and its blowup.

[BibT_eX]

[DOI]

J. Comb. Theory B, 2010

Green's Conjecture and Testing Linear Invariant Properties.

[BibT_eX]

[DOI]

Proceedings of the Property Testing - Current Research and Surveys, 2010

A Unified Framework for Testing Linear-Invariant Properties.

[BibT_eX]

[DOI]

Arnab Bhattacharyya

Elena Grigorescu

Proceedings of the 51th Annual IEEE Symposium on Foundations of Computer Science, 2010

2009

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Artur Czumaj

Christian Sohler

SIAM J. Comput., 2009

Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma.

[BibT_eX]

[DOI]

Electron. J. Comb., 2009

Green's conjecture and testing linear-invariant properties.

[BibT_eX]

[DOI]

Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

2008

Quasi-randomness and the distribution of copies of a fixed graph.

[BibT_eX]

[DOI]

Comb., 2008

A separation theorem in property testing.

[BibT_eX]

[DOI]

Comb., 2008

Every minor-closed property of sparse graphs is testable.

[BibT_eX]

[DOI]

Itai Benjamini

Oded Schramm

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The effect of induced subgraphs on quasi-randomness.

[BibT_eX]

[DOI]

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

All-Pairs Shortest Paths with a Sublinear Additive Error.

[BibT_eX]

[DOI]

Liam Roditty

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Testing the Expansion of a Graph.

[BibT_eX]

[DOI]

Asaf Nachmias

Electron. Colloquium Comput. Complex., 2007

Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs.

[BibT_eX]

[DOI]

Artur Czumaj

Christian Sohler

Electron. Colloquium Comput. Complex., 2007

A Note on Maximizing the Spread of Influence in Social Networks.

[BibT_eX]

[DOI]

Eyal Even-Dar

Proceedings of the Internet and Network Economics, Third International Workshop, 2007

All-pairs bottleneck paths in vertex weighted graphs.

[BibT_eX]

[DOI]

Uri Zwick

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

An elementary construction of constant-degree expanders.

[BibT_eX]

[DOI]

Oded Schwartz

Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2007

Approximate Hypergraph Partitioning and Applications.

[BibT_eX]

[DOI]

Eldar Fischer

Arie Matsliah

Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, 2007

Can a Graph Have Distinct Regular Partitions?

[BibT_eX]

[DOI]

Uri Stav

Proceedings of the Computing and Combinatorics, 13th Annual International Conference, 2007

2006

Graph propert testing and related problems

[BibT_eX]

[DOI]

PhD thesis, 2006

On An Extremal Hypergraph Problem Of Brown, Erdös And Sós.

[BibT_eX]

[DOI]

Comb., 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

Additive Approximation for Edge-Deletion Problems (Abstract).

[BibT_eX]

[DOI]

Benny Sudakov

Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Space Complexity vs. Query Complexity.

[BibT_eX]

[DOI]

Oded Lachish

Ilan Newman

Proceedings of the Approximation, 2006

2005

Homomorphisms in Graph Property Testing - A Survey

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2005

Every monotone graph property is testable.

[BibT_eX]

[DOI]

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

Linear equations, arithmetic progressions and hypergraph property testing.

[BibT_eX]

[DOI]

Proceedings of the Sixteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2005

Additive Approximation for Edge-Deletion Problems.

[BibT_eX]

[DOI]

Benny Sudakov

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

A Characterization of the (natural) Graph Properties Testable with One-Sided Error.

[BibT_eX]

[DOI]

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science, 2005

2004

A characterization of easily testable induced subgraphs.

[BibT_eX]

[DOI]

Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2004

2003

Testing subgraphs in directed graphs.

[BibT_eX]

[DOI]

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2002

Testing satisfiability.

[BibT_eX]

[DOI]