# Asaf Shapira

According to our database

Collaborative distances:

^{1}, Asaf Shapira authored at least 54 papers between 2002 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### On csauthors.net:

## Bibliography

2018

A Generalized Turan Problem and its Applications.

Electronic Colloquium on Computational Complexity (ECCC), 2018

A generalized Turán problem and its applications.

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

Efficient Testing without Efficient Regularity.

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

2017

Constructing near spanning trees with few local inspections.

Random Struct. Algorithms, 2017

Removal lemmas with polynomial bounds.

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

2016

Unavoidable tournaments.

J. Comb. Theory, Ser. B, 2016

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

Combinatorica, 2016

2015

Exact bounds for some hypergraph saturation problems.

J. Comb. Theory, Ser. B, 2015

Constructing Near Spanning Trees with Few Local Inspections.

Electronic Colloquium on Computational Complexity (ECCC), 2015

An Optimal Algorithm for Finding Frieze-Kannan Regular Partitions.

Combinatorics, Probability & Computing, 2015

Small complete minors above the extremal edge density.

Combinatorica, 2015

Decomposing a Graph Into Expanding Subgraphs.

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

2014

Finding cycles and trees in sublinear time.

Random Struct. Algorithms, 2014

Forcing $k$-repetitions in Degree Sequences.

Electr. J. Comb., 2014

2013

A Note on Even Cycles and Quasirandom Tournaments.

Journal of Graph Theory, 2013

Deterministic vs Non-deterministic Graph Property Testing.

Electronic Colloquium on Computational Complexity (ECCC), 2013

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

Combinatorics, Probability & Computing, 2013

2012

The quasi-randomness of hypergraph cut properties.

Random Struct. Algorithms, 2012

Finding Cycles and Trees in Sublinear Time.

Electronic Colloquium on Computational Complexity (ECCC), 2012

Testing odd-cycle-freeness in Boolean functions.

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

2011

Sublinear Time Algorithms.

SIAM J. Discrete Math., 2011

Sublinear Time Algorithms.

Electronic Colloquium on Computational Complexity (ECCC), 2011

Randomized greedy: new variants of some classic approximation algorithms.

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

A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma.

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

2010

On the density of a graph and its blowup.

J. Comb. Theory, Ser. B, 2010

Testing the expansion of a graph.

Inf. Comput., 2010

A Unified Framework for Testing Linear-Invariant Properties.

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

2009

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs.

SIAM J. Comput., 2009

Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma.

Electr. J. Comb., 2009

Green's conjecture and testing linear-invariant properties.

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

2008

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

Combinatorica, 2008

A separation theorem in property testing.

Combinatorica, 2008

Every minor-closed property of sparse graphs is testable.

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

The effect of induced subgraphs on quasi-randomness.

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

All-Pairs Shortest Paths with a Sublinear Additive Error.

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

2007

Testing the Expansion of a Graph.

Electronic Colloquium on Computational Complexity (ECCC), 2007

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

Electronic Colloquium on Computational Complexity (ECCC), 2007

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

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

All-pairs bottleneck paths in vertex weighted graphs.

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

An elementary construction of constant-degree expanders.

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

Approximate Hypergraph Partitioning and Applications.

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

Can a Graph Have Distinct Regular Partitions?

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

2006

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

Combinatorica, 2006

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

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

Additive Approximation for Edge-Deletion Problems (Abstract).

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

Space Complexity vs. Query Complexity.

Proceedings of the Approximation, 2006

2005

Homomorphisms in Graph Property Testing - A Survey

Electronic Colloquium on Computational Complexity (ECCC), 2005

Every monotone graph property is testable.

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

Linear equations, arithmetic progressions and hypergraph property testing.

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

Additive Approximation for Edge-Deletion Problems.

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

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

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

2004

A characterization of easily testable induced subgraphs.

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

2003

Testing subgraphs in directed graphs.

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

2002

Testing satisfiability.

Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2002