Asaf Shapira

Orcid: 0000-0001-9902-0164

According to our database1, Asaf Shapira authored at least 71 papers between 2003 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.



In proceedings 
PhD thesis 




A Tight Bound for Testing Partition Properties.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Counting Homomorphic Cycles in Degenerate Graphs.
ACM Trans. Algorithms, January, 2023

A new bound for the Brown-Erdős-Sós problem.
J. Comb. Theory B, 2023

Trimming forests is hard (unless they are made of stars).
CoRR, 2023

On Rödl's Theorem for Cographs.
Electron. J. Comb., 2023

Testing Versus Estimation of Graph Properties, Revisited.
Proceedings of the Approximation, 2023

Counting Subgraphs in Degenerate Graphs.
J. ACM, 2022

Every Orientation of a $4$-Chromatic Graph has a Non-Bipartite Acyclic Subgraph.
Electron. J. Comb., 2022

Quasirandom Graphs and the Pantograph Equation.
Am. Math. Mon., 2021

On Erdős's Method for Bounding the Partition Function.
Am. Math. Mon., 2021

Two Erdős-Hajnal-type theorems in hypergraphs.
J. Comb. Theory B, 2021

Tournament Quasirandomness from Local Counting.
Comb., 2021

Testing linear inequalities of subgraph statistics.
Electron. Colloquium Comput. Complex., 2020

Counting Subgraphs in Degenerate Graphs.
Electron. Colloquium Comput. Complex., 2020

The Induced Removal Lemma in Sparse Graphs.
Comb. Probab. Comput., 2020

A quantitative Lovász criterion for Property B.
Comb. Probab. Comput., 2020

The removal lemma for tournaments.
J. Comb. Theory B, 2019

Testing Graphs against an Unknown Distribution.
Electron. Colloquium Comput. Complex., 2019

Efficient Removal Without Efficient Regularity.
Comb., 2019

Decomposing a graph into expanding subgraphs.
Random Struct. Algorithms, 2018

A Generalized Turan Problem and its Applications.
Electron. Colloquium Comput. Complex., 2018

Efficient Testing without Efficient Regularity.
Proceedings of the 9th Innovations in Theoretical Computer Science Conference, 2018

Removal lemmas with polynomial bounds.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

Unavoidable tournaments.
J. Comb. Theory B, 2016

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

Exact bounds for some hypergraph saturation problems.
J. Comb. Theory B, 2015

Constructing Near Spanning Trees with Few Local Inspections.
Electron. Colloquium Comput. Complex., 2015

An Optimal Algorithm for Finding Frieze-Kannan Regular Partitions.
Comb. Probab. Comput., 2015

Small complete minors above the extremal edge density.
Comb., 2015

Forcing $k$-repetitions in Degree Sequences.
Electron. J. Comb., 2014

A Note on Even Cycles and Quasirandom Tournaments.
J. Graph Theory, 2013

Deterministic vs Non-deterministic Graph Property Testing.
Electron. Colloquium Comput. Complex., 2013

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

A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma.
SIAM J. Discret. Math., 2012

The quasi-randomness of hypergraph cut properties.
Random Struct. Algorithms, 2012

Finding Cycles and Trees in Sublinear Time.
Electron. Colloquium Comput. Complex., 2012

Testing Odd-Cycle-Freeness in Boolean Functions.
Comb. Probab. Comput., 2012

A Note on the Balanced ST-Connectivity
CoRR, 2012

All-pairs shortest paths with a sublinear additive error.
ACM Trans. Algorithms, 2011

Sublinear Time Algorithms.
SIAM J. Discret. Math., 2011

A note on maximizing the spread of influence in social networks.
Inf. Process. Lett., 2011

All-Pairs Bottleneck Paths in Vertex Weighted Graphs.
Algorithmica, 2011

Randomized greedy: new variants of some classic approximation algorithms.
Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, 2011

Approximate Hypergraph Partitioning and Applications.
SIAM J. Comput., 2010

The effect of induced subgraphs on quasi-randomness.
Random Struct. Algorithms, 2010

On the density of a graph and its blowup.
J. Comb. Theory B, 2010

A Unified Framework for Testing Linear-Invariant Properties.
Electron. Colloquium Comput. Complex., 2010

Green's Conjecture and Testing Linear Invariant Properties.
Proceedings of the Property Testing - Current Research and Surveys, 2010

Can a Graph Have Distinct Regular Partitions?
SIAM J. Discret. Math., 2009

Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs.
SIAM J. Comput., 2009

A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity.
SIAM J. Comput., 2009

Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma.
Electron. J. Comb., 2009

Green's conjecture and testing linear-invariant properties.
Proceedings of the 41st Annual ACM Symposium on Theory of Computing, 2009

Every Monotone Graph Property Is Testable.
SIAM J. Comput., 2008

A Characterization of the (Natural) Graph Properties Testable with One-Sided Error.
SIAM J. Comput., 2008

Every Minor-Closed Property of Sparse Graphs is Testable.
Electron. Colloquium Comput. Complex., 2008

An Elementary Construction of Constant-Degree Expanders.
Comb. Probab. Comput., 2008

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

A separation theorem in property testing.
Comb., 2008

Space Complexity Vs. Query Complexity.
Comput. Complex., 2008

Testing the Expansion of a Graph.
Electron. Colloquium Comput. Complex., 2007

Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs.
Electron. Colloquium Comput. Complex., 2007

Graph propert testing and related problems
PhD thesis, 2006

A Characterization of Easily Testable Induced Subgraphs.
Comb. Probab. Comput., 2006

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

Additive Approximation for Edge-Deletion Problems (Abstract).
Proceedings of the Automata, Languages and Programming, 33rd International Colloquium, 2006

Linear Equations, Arithmetic Progressions and Hypergraph Property Testing.
Theory Comput., 2005

Homomorphisms in Graph Property Testing - A Survey
Electron. Colloquium Comput. Complex., 2005

Additive Approximation for Edge-Deletion Problems.
Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Testing subgraphs in directed graphs.
J. Comput. Syst. Sci., 2004

Testing satisfiability.
J. Algorithms, 2003