Asaf Shapira's list of publications
- G. Moshkovitz and A. Shapira
Ramsey-Theory, Integer Partitions and a New
Proof of The Erdes-Szekeres Theorem
Submitted
- 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
Submitted
- D. Delamonica, S. Kalyanasundaram, D. Martin, V. Rodl and A.
Shapira
An Optimal Algorithm for Computing Frieze-Kannan
Regular Partitions
Submitted
- S. Kalyanasundaram and A. Shapira
A Wowzer-type Lower Bound for the Strong
Regularity-Lemma
Proc. of the London Math Soc, to appear
- S. Kalyanasundaram and A. Shapira
A Note on Even Cycles and Quasi-Random
Tournaments
Journal of Graph Theory, to appear
- 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, to appear
- A. Czumaj, O. Goldreich, D. Ron, C. Seshadhri, A. Shapira and C.
Sohler
Finding Cycles and Trees in Sublinear Time
Random Structures and Algorithms, to appear
- 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
- 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), to appear
- 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, Erdos and Sos
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