According to our database
1,
Asaf Shapira
authored at least 71 papers
between 2003 and 2024.
Collaborative distances:
2024
A Tight Bound for Testing Partition Properties.
Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024
2023
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
2022
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
2021
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
2020
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
2019
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
2018
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
2017
Removal lemmas with polynomial bounds.
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017
2016
A short proof of Gowers' lower bound for the regularity lemma.
Comb., 2016
2015
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
2014
Forcing $k$-repetitions in Degree Sequences.
Electron. J. Comb., 2014
2013
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
2012
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
A Note on the Balanced ST-Connectivity
CoRR, 2012
2011
All-pairs shortest paths with a sublinear additive error.
ACM Trans. Algorithms, 2011
A note on maximizing the spread of influence in social networks.
Inf. Process. Lett., 2011
Sublinear Time Algorithms.
Electron. Colloquium Comput. Complex., 2011
Testing Odd-Cycle-Freeness in Boolean Functions.
Electron. Colloquium Comput. Complex., 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
2010
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
2009
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
2008
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
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
2007
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
2006
Graph propert testing and related problems
PhD thesis, 2006
An Elementary Construction of Constant-Degree Expanders.
Electron. Colloquium Comput. Complex., 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
2005
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
2004
Testing subgraphs in directed graphs.
J. Comput. Syst. Sci., 2004
2003
