Asaf Shapira

Orcid: 0000-0001-9902-0164

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

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

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

On csauthors.net:

Bibliography

2024
A generalisation of Varnavides's theorem.
Comb. Probab. Comput., 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
Unavoidable tournaments.
J. Comb. Theory B, 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
Testing satisfiability.
J. Algorithms, 2003


  Loading...