Asaf Shapira's list of publications
- L. Gishboliner, Y. Levanzov and A. Shapira
Trimming Forests is Hard (Unless They Are Made of Stars)
Submitted
- L. Gishboliner and A. Shapira
On Rodl's Theorem for Cographs
Electronic Journal of Combinatorics, to appear
- L. Gishboliner, N. Kushnir and A. Shapira
Testing versus Estimation of Graph Properties,
Revisited
Random Structures and Algorithms, to appear
Proc. of RANDOM 2023, 1-18
- A. Shapira and H. Stagni
A Tight Bound for Testing Partition
Properties
Proc. of SODA 2024, to appear
- A. Shapira and M. Tyomkyn
A New Approach for the Brown-Erdős-Sós
Problem
Israel Journal of Mathematics, to appear
- L. Gishboliner, A. Shapira and Y. Wigderson
An Efficiednt Asymmetric Removal Lemma
and its Limitations
Submitted
- A. Cohen Antonir and A. Shapira
Bounding the Number of Odd Paths in Planar Graphs via Convex Optimization
Journal of Graph Theory, to appear
- A. Cohen Antonir and A. Shapira
An Elementary Proof of a Theorem of Hardy and
Ramanujan
The Ramanujan Journal, to appear
- A. Shapira and L. Gishboliner
Hypergraph Removal with Polynomial Bounds
Submitted
- A. Shapira
Every Orientation of a 4-Chromatic Graph Has a Non-bipartite Acyclic
Subgraph
Electronic Journal of Combinatorics 29 (2022), P1.2
- A. Shapira and M. Tyomkyn
Weakly Saturated Hypergraphs and a Conjecture of
Tuza
Proc. of the American Math Society 151 (2023), 2795-2805
- A. Cohen Antonir and A. Shapira
Exact Limit Theorems for Restricted Integer
Partitions
Advances in Mathematics 407 (2022), 108554
- A. Cohen Antonir and A. Shapira
On Erdős's Method for Bounding the Partition
Function
American Mathematical Monthly 128 (2021), 744-747
- A. Shapira and M. Tyomkyn
Quasirandom Graphs and the Pantograph
Equation
American Mathematical Monthly 128 (2021), 630-639
- L. Gishboliner, Y. Levanzov, A. Shapira and R. Yuster
Counting Homomorphic Cycles in Degenerate
Graphs
Proc. of SODA 2022, 417-430
ACM Transactions on Algorithms 19 (2023), 1-22
- L. Gishboliner and A. Shapira
Constructing Dense Grid-Free Linear 3-Graphs
Proc. of the American Math Society 150 (2022), 69-74
- S. K. Bera, L. Gishboliner, Y. Levanzov, C. Seshadhri and A.
Shapira
Counting Subgraphs in Degenerate Graphs
Journal of the ACM 69 (2022), 1-21
- D. Conlon, L. Gishboliner, Y. Levanzov and A. Shapira
A New Bound for the Brown-Erdős-Sós
Problem
Journal of Combinatorial Theory Ser. B 158 (2023), 1-35
- L. Gishboliner, A. Shapira and H. Stagni
Testing Linear Inequalities of Subgraph
Statistics
Random Structures and Algorithms 58 (2021), 468-479
Proc. of ITCS 2020, 1-9
- A. Shapira and M. Tyomkyn
A Ramsey Variant of the Brown-Erdős-Sós
Conjecture
Bulletin of the London Math Society 53 (2021), 1453-1469
- S. Sapir and A. Shapira
The Induced Removal Lemma in Sparse
Graphs
Combinatorics, Probability and Computing 29 (2020), 153-162.
- M. Bucic, E. Long, A. Shapira and B. Sudakov
Tournament Quasirandomness from Local
Counting
Combinatorica 41 (2021), 175-208
- A. Ferber and A. Shapira
A Quantitative Lovász Criterion for Property
B
Combinatorics, Probability and Computing 29 (2020), 956-960
- L. Gishboliner and A. Shapira
Testing Graphs Against an Unknown Distribution
Israel Journal of Mathematics 245 (2021), 787-837
Proc. of STOC 2019, 535-546
- M. Amir, A. Shapira and M. Tyomkyn
Two Erdős-Hajnal-type Theorems in
Hypergraphs
Journal of Combinatorial Theory Ser. B 146 (2021), 417-438
- G. Moshkovitz and A. Shapira
A Tight Bound for Hypergraph Regularity
Geometric and Functional Analysis (GAFA) 29 (2019), 1531-1578
See here
for a proof of the special case for 3-uniform hypergraphs.
- L. Gishboliner and A. Shapira
A Generalized Turan Problem and its
Applications
International Math Research Notices (IMRN) 2020, 3417-3452
Proc of STOC 2018, 760-772
- J. Fox, L. Gishboliner, A. Shapira and R. Yuster
The Removal Lemma for Tournaments
Journal of Combinatorial Theory Ser. B 136 (2019), 110-134
- L. Gishboliner and A. Shapira
Efficient Removal without Efficient Regularity
Combinatorica 39 (2019), 639-658
Proc of ITCS 2018, 1-15
- L. Gishboliner and A. Shapira
Removal Lemmas with Polynomial Bounds
International Math Research Notices (IMRN) 2021, 14409-14444
Proc of STOC 2017, 510-522
- G. Moshkovitz and A. Shapira
A Sparse Regular Approximation Lemma
Transactions of the American Math Society 371 (2019), 6779-6814
- R. Levi, G. Moshkovitz, D. Ron, R. Rubinfeld and A. Shapira
Constructing Near Spanning Trees with Few
Local
Inspections
Random Structures and Algorithms 50 (2017), 183-200
- G. Moshkovitz and A. Shapira
Decomposing a Graph into Expanding Subgraphs
Random Structures and Algorithms 52 (2018), 158-178
Proc of SODA 2015, 1283-1295
- A. Shapira and R. Yuster
A Tournament Approach to Pattern Avoiding
Matrices
Israel Journal of Mathematics 217 (2017), 477-505
- A. Shapira and R. Yuster
Unavoidable Tournaments
Journal of Combinatorial Theory, Ser B 116 (2016), 191-207
- K. Hosseini, S. Lovett, G. Moshkovitz and A. Shapira
An Improved Lower Bound for Arithmetic
Regularity
Mathematical Proceedings of the Cambridge Philosophical Society 161 (2016), 193-197
- G. Moshkovitz and A. Shapira
Exact Bounds for Some Hypergraph Saturation
Problems
Journal of Combinatorial Theory Ser. B 111 (2015), 242-248
- G. Moshkovitz and A. Shapira
Ramsey-Theory, Integer Partitions and a New
Proof of The Erdős-Szekeres Theorem
Advances in Mathematics 262 (2014), 1107-1129
- G. Moshkovitz and A. Shapira
A Short Proof of Gowers' Lower Bound for the
Regularity Lemma
Combinatorica 36 (2016), 187-194
- L. Gishboliner and A. Shapira
Deterministic vs Non-deterministic Graph Property
Testing
Israel Journal of Mathematics 204 (2014), 397-416
- A. Shapira and B. Sudakov
Small Complete Minors Above the Extremal Edge
Density
Combinatorica 35 (2015), 75-94
- Y. Caro, A. Shapira and R. Yuster
Forcing k-Repetitions in Degree Sequences
Electronic Journal of Combinatorics 21 (2014), P24
- H. Huang, J. Ma, A. Shapira, B. Sudakov and R. Yuster
Large Feedback Arc Sets, High Minimum
Degree Subgraphs, and Long Cycles in Eulerian Gigraphs
Combinatorics, Probability and Computing 22 (2013), 859-873
- D. Delamonica, S. Kalyanasundaram, D. Martin, V. Rodl and A.
Shapira
An Optimal Algorithm for Computing Frieze-Kannan
Regular Partitions
Combinatorics, Probability and Computing 24 (2015), 407-437
- S. Kalyanasundaram and A. Shapira
A Wowzer-type Lower Bound for the Strong
Regularity-Lemma
Proc. of the London Math Society 106 (2013), 621-649
- S. Kalyanasundaram and A. Shapira
A Note on Even Cycles and Quasi-Random
Tournaments
Journal of Graph Theory 73 (2013), 260-266
- D. Delamonica, S. Kalyanasundaram, D. Martin, V. Rodl and A.
Shapira
A Deterministic Algorithm for the Frieze-Kannan
Rerularity
Lemma
Proc of RANDOM 2011, 495-506
SIAM Journal on Discrete Math 26 (2012), 15-29
- A. Bhattacharyya, E. Grigorescu, P. Raghavendra and A.
Shapira
Testing Odd-Cycle Freeness in Boolean Functions
Proc. of SODA 2012, 1140-1149
Combinatorics, Probability and Computing 21 (2012), 835-855
- A. Czumaj, O. Goldreich, D. Ron, C. Seshadhri, A. Shapira and C.
Sohler
Finding Cycles and Trees in Sublinear Time
Random Structures and Algorithms, 45 (2014), 139-184
- Ronitt Rubinfeld and Asaf Shapira
Sublinear Time Algorithms
SIAM Journal on Discrete Math 25 (2011), 1562-1588
- K. Costello, A. Shapira and P. Tetali
On Randomizing Two Derandomized Greedy
Algorithms
Proc. of SODA 2011, 647-655
Journal of Combinatorics Vol. 1 (2010), 265-283
- A. Bhattacharyya, E. Grigorescu and A. Shapira
A Unified Framework for Testing Linear-Invariant
Properties
Proc. of FOCS 2010, 478-487
Random Structures and Algorithms 46 (2015), 232-260
- Asaf Shapira and Raphael Yuster
The Quasi-Randomness of Hypergraph Cut Properties
Random Structures and Algorithms 40 (2012), 105-131
- Asaf Shapira and Robin Thomas
Color-Critical Graphs Have Logarithmic
Circumference
Advances in Mathematics 227 (2011), 2309-2326
- Asaf Shapira and Raphael Yuster
On the Density of a Graph and its Blowup
Journal of Combinatorial Theory Ser. B 100 (2010), 704-719
- Asaf Shapira and Raphael Yuster
Multigraphs (Only) Satisfy a Weak Triangle
Removal Lemma
Electronic Journal of Combinatorics 16 (2009), N11
- Asaf Shapira
A Proof of Green's Conjecture Regarding the Removal Properties
of Sets of Linear Equations
Proc. of STOC 2009, 159-166
Journal of the London Math Society 81 (2010), 355-373
- Asaf Nachmias and Asaf Shapira
Testing the Expansion of a Graph
Information and Computation 208 (2010), 309-314
- Itai Benjamini, Oded Schramm and Asaf Shapira
Every Minor-Closed Property of Sparse Graphs is
Testable
Proc. of STOC 2008, 393-402
Advances in Mathematics 223 (2010), 2200-2218
- Liam Roditty and Asaf Shapira
All-Pairs Shortest Paths with a Sublinear Additive
Error
Proc. of ICALP 2008, 622-633
ACM Transactions on Algorithms 7 (2011)
- Asaf Shapira
Quasi-Randomness and the Distribution of Copies of a
Fixed Graphs
Combinatorica 28 (2008), 735-745
- Asaf Shapira and Raphael Yuster
The Effect of Induced Subgraphs on
Quasi-Randomness
Proc. of SODA 2008, 789-798
Random Structures and Algorithms 36 (2010), 90-109
- Artur Czumaj, Asaf Shapira and Christian Sohler
Testing Hereditary Properties of Non-Expanding
Bounded-Degree Graphs
SIAM Journal on Computing 38 (2009), 2499-2510
- Eyal Even-Dar and Asaf Shapira
A Note on Maximizing the Spread of Influence in
Social Networks
Proc. of WINE 2007, 281-286
Information Processing Letters 111 (2011), 184-187
- Eldar Fischer, Arie Matsliach and Asaf Shapira
Approximate Hypergraph Partitioning and
Applications
Proc. of FOCS 2007, 579-589
SIAM Journal on Computing 39 (2010), 3155-3185
- Asaf Shapira, Raphael Yuster and Uri Zwick
All-Pairs Bottleneck Paths in Vertex Weighted
Graphs
Proc. of SODA 2007, 978-985
Algorithmica 59 (2011), 621-633
- Noga Alon, Oded Schwartz and Asaf Shapira
An Elementary Construction of Constant-Degree
Expanders
Proc. of SODA 2007, 454-458
Combinatorics, Probability and Computing 17 (2008), 319-327
- Noga Alon, Asaf Shapira and Uri Stav
Can a Graph Have Distinct Regular Partitions?
Proc. of COCOON 2007, 428-438
SIAM Journal on Discrete Mathematics 23 (2009), 278-287
- Oded Lachish, Ilan Newman and Asaf Shapira
Space Complexity vs. Query Complexity
Proc. of RANDOM 2006, 426-437
Computational Complexity (Special Issue of RANDOM'06) 17 (2008), 70-93
- Noga Alon, Eldar Fischer, Ilan Newman and Asaf Shapira
A Combinatorial Characterization of the Testable
Graph Properties: It's All About Regularity
Proc. of STOC 2006, 251-260
SIAM Journal on Computing (Special Issue of STOC'06) 39 (2009), 143-167
- Noga Alon and Asaf Shapira
Homomorphisms in Graph Property Testing
Topics in Discrete Mathematics, Springer, Berlin, 2006, 281-313
- Noga Alon and Asaf Shapira
A Characterization of the (natural) Graph Properties
Testable with One-Sided Error
Proc. of FOCS 2005, 429-438
SIAM Journal on Computing (Special Issue of FOCS'05) 37 (2008),
1703-1727
- Noga Alon, Asaf Shapira and Benny Sudakov
Additive Approximation for Edge-Deletion Problems
Proc. of FOCS 2005, 419-428
Annals of Mathematics 170 (2009), 371-411
- Noga Alon and Asaf Shapira
A Separation Theorem in Property Testing
Combinatorica 28 (2008), 261-281
- Noga Alon and Asaf Shapira
Every Monotone Graph Property is Testable
Proc. of STOC 2005, 128-137
SIAM Journal on Computing (Special Issue of STOC'05) 38 (2008), 505-522
- Asaf Shapira
Behrend-Type Constructions for Sets of Linear
Equations
Acta Arithmetica 122 (2006), 17-33
- Noga Alon and Asaf Shapira
On an Extremal Hypergraph Problem of
Brown, Erdős and Sós
Combinatorica 26 (2006), 627-645
- Noga Alon and Asaf Shapira
Linear Equations, Arithmetic Progressions and
Hypergraph Property Testing
Proc. of SODA 2005, 708-717
Theory of Computing Vol 1 (2005), 177-216
- Noga Alon and Asaf Shapira
A Characterization of Easily Testable Induced Subgraphs
Proc. of SODA 2004, 935-944
Combinatorics, Probability and Computing 15 (2006), 791-805
- Noga Alon and Asaf Shapira
Testing Subgraphs in Directed Graphs
Proc. of STOC 2003, 700-709
Journal of Computer and System Sciences (Special Issue of STOC'03) 69
(2004),
354-382
- Noga Alon and Asaf Shapira
Testing Satisfiability
Proc. of SODA 2002, 645-654
Journal of Algorithms 47 (2003), 87-103