Asaf Shapira

ORCID

Publication Activity (10 Years)

Years Active: 2002-2024
Publications (10 Years): 37

Top Venues

CoRR

Electron. Colloquium Comput. Complex.

Random Struct. Algorithms

J. Comb. Theory, Ser. B

Publications

Asaf Shapira, Henrique Stagni
A Tight Bound for Testing Partition Properties. SODA (2024)
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
Trimming forests is hard (unless they are made of stars). CoRR (2023)
David Conlon, Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
A new bound for the Brown-Erdős-Sós problem. J. Comb. Theory, Ser. B 158 (Part) (2023)
Lior Gishboliner, Nick Kushnir, Asaf Shapira
Testing versus estimation of graph properties, revisited. CoRR (2023)
Lior Gishboliner, Nick Kushnir, Asaf Shapira
Testing Versus Estimation of Graph Properties, Revisited. APPROX/RANDOM (2023)
Lior Gishboliner, Asaf Shapira
On Rödl's Theorem for Cographs. Electron. J. Comb. 30 (4) (2023)
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster
Counting Homomorphic Cycles in Degenerate Graphs. ACM Trans. Algorithms 19 (1) (2023)
Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, Asaf Shapira
Counting Subgraphs in Degenerate Graphs. J. ACM 69 (3) (2022)
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster
Counting Homomorphic Cycles in Degenerate Graphs. SODA (2022)
Asaf Shapira
Every Orientation of a $4$-Chromatic Graph has a Non-Bipartite Acyclic Subgraph. Electron. J. Comb. 29 (1) (2022)
Lior Gishboliner, Asaf Shapira, Henrique Stagni
Testing linear inequalities of subgraph statistics. Random Struct. Algorithms 58 (3) (2021)
Michal Amir, Asaf Shapira, Mykhaylo Tyomkyn
Two Erdős-Hajnal-type theorems in hypergraphs. J. Comb. Theory, Ser. B 146 (2021)
Asaf Cohen Antonir, Asaf Shapira
On Erdős's Method for Bounding the Partition Function. Am. Math. Mon. 128 (8) (2021)
Matija Bucic, Eoin Long, Asaf Shapira, Benny Sudakov
Tournament Quasirandomness from Local Counting. Comb. 41 (2) (2021)
Asaf Shapira, Mykhaylo Tyomkyn
Quasirandom Graphs and the Pantograph Equation. Am. Math. Mon. 128 (7) (2021)
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster
Counting Homomorphic Cycles in Degenerate Graphs. CoRR (2020)
Asaf Ferber, Asaf Shapira
A quantitative Lovász criterion for Property B. Comb. Probab. Comput. 29 (6) (2020)
Lior Gishboliner, Asaf Shapira, Henrique Stagni
Testing linear inequalities of subgraph statistics. Electron. Colloquium Comput. Complex. 27 (2020)
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
Counting Subgraphs in Degenerate Graphs. CoRR (2020)
Lior Gishboliner, Asaf Shapira, Henrique Stagni
Testing linear inequalities of subgraph statistics. CoRR (2020)
Lior Gishboliner, Asaf Shapira, Henrique Stagni
Testing Linear Inequalities of Subgraph Statistics. ITCS (2020)
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
Counting Subgraphs in Degenerate Graphs. Electron. Colloquium Comput. Complex. 27 (2020)
Shachar Sapir, Asaf Shapira
The Induced Removal Lemma in Sparse Graphs. Comb. Probab. Comput. 29 (1) (2020)
Lior Gishboliner, Asaf Shapira
Efficient Removal Without Efficient Regularity. Comb. 39 (3) (2019)
Jacob Fox, Lior Gishboliner, Asaf Shapira, Raphael Yuster
The removal lemma for tournaments. J. Comb. Theory, Ser. B 136 (2019)
Lior Gishboliner, Asaf Shapira
Testing graphs against an unknown distribution. STOC (2019)
Lior Gishboliner, Asaf Shapira
Testing Graphs against an Unknown Distribution. CoRR (2019)
Lior Gishboliner, Asaf Shapira
Testing Graphs against an Unknown Distribution. Electron. Colloquium Comput. Complex. 26 (2019)
Lior Gishboliner, Asaf Shapira
A generalized Turán problem and its applications. STOC (2018)
Lior Gishboliner, Asaf Shapira
A Generalized Turan Problem and its Applications. Electron. Colloquium Comput. Complex. 25 (2018)
Guy Moshkovitz, Asaf Shapira
Decomposing a graph into expanding subgraphs. Random Struct. Algorithms 52 (1) (2018)
Lior Gishboliner, Asaf Shapira
Efficient Testing without Efficient Regularity. ITCS (2018)
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
Constructing near spanning trees with few local inspections. Random Struct. Algorithms 50 (2) (2017)
Lior Gishboliner, Asaf Shapira
Removal lemmas with polynomial bounds. STOC (2017)
Lior Gishboliner, Asaf Shapira
A Generalized Turán Problem and its Applications. CoRR (2017)
Asaf Shapira, Raphael Yuster
Unavoidable tournaments. J. Comb. Theory, Ser. B 116 (2016)
Guy Moshkovitz, Asaf Shapira
A short proof of Gowers' lower bound for the regularity lemma. Comb. 36 (2) (2016)
Asaf Shapira, Benny Sudakov
Small complete minors above the extremal edge density. Comb. 35 (1) (2015)
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
Constructing Near Spanning Trees with Few Local Inspections. CoRR (2015)
Guy Moshkovitz, Asaf Shapira
Exact bounds for some hypergraph saturation problems. J. Comb. Theory, Ser. B 111 (2015)
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
A unified framework for testing linear-invariant properties. Random Struct. Algorithms 46 (2) (2015)
Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
Constructing Near Spanning Trees with Few Local Inspections. Electron. Colloquium Comput. Complex. 22 (2015)
Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtech Rödl, Asaf Shapira
An Optimal Algorithm for Finding Frieze-Kannan Regular Partitions. Comb. Probab. Comput. 24 (2) (2015)
Guy Moshkovitz, Asaf Shapira
Decomposing a Graph Into Expanding Subgraphs. SODA (2015)
Yair Caro, Asaf Shapira, Raphael Yuster
Forcing $k$-repetitions in Degree Sequences. Electron. J. Comb. 21 (1) (2014)
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
Finding cycles and trees in sublinear time. Random Struct. Algorithms 45 (2) (2014)
Hao Huang, Jie Ma, Asaf Shapira, Benny Sudakov, Raphael Yuster
Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs. Comb. Probab. Comput. 22 (6) (2013)
Subrahmanyam Kalyanasundaram, Asaf Shapira
A Note on Even Cycles and Quasirandom Tournaments. J. Graph Theory 73 (3) (2013)
Lior Gishboliner, Asaf Shapira
Deterministic vs Non-deterministic Graph Property Testing. Electron. Colloquium Comput. Complex. 20 (2013)
Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtech Rödl, Asaf Shapira
A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma. SIAM J. Discret. Math. 26 (1) (2012)
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
Finding Cycles and Trees in Sublinear Time. Electron. Colloquium Comput. Complex. 19 (2012)
Asaf Shapira, Raphael Yuster
The quasi-randomness of hypergraph cut properties. Random Struct. Algorithms 40 (1) (2012)
Asaf Shapira, Benny Sudakov
Small Complete Minors Above the Extremal Edge Density CoRR (2012)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing odd-cycle-freeness in Boolean functions. SODA (2012)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing Odd-Cycle-Freeness in Boolean Functions. Comb. Probab. Comput. 21 (6) (2012)
Shiva Kintali, Asaf Shapira
A Note on the Balanced ST-Connectivity CoRR (2012)
Kevin P. Costello, Asaf Shapira, Prasad Tetali
Randomized greedy: new variants of some classic approximation algorithms. SODA (2011)
Ronitt Rubinfeld, Asaf Shapira
Sublinear Time Algorithms. SIAM J. Discret. Math. 25 (4) (2011)
Eyal Even-Dar, Asaf Shapira
A note on maximizing the spread of influence in social networks. Inf. Process. Lett. 111 (4) (2011)
Asaf Shapira, Raphael Yuster, Uri Zwick
All-Pairs Bottleneck Paths in Vertex Weighted Graphs. Algorithmica 59 (4) (2011)
Liam Roditty, Asaf Shapira
All-pairs shortest paths with a sublinear additive error. ACM Trans. Algorithms 7 (4) (2011)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing Odd-Cycle-Freeness in Boolean Functions CoRR (2011)
Ronitt Rubinfeld, Asaf Shapira
Sublinear Time Algorithms. Electron. Colloquium Comput. Complex. 18 (2011)
Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtech Rödl, Asaf Shapira
A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma. APPROX-RANDOM (2011)
Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
Testing Odd-Cycle-Freeness in Boolean Functions. Electron. Colloquium Comput. Complex. 18 (2011)
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
A Unified Framework for Testing Linear-Invariant Properties. Electron. Colloquium Comput. Complex. 17 (2010)
Eldar Fischer, Arie Matsliah, Asaf Shapira
Approximate Hypergraph Partitioning and Applications. SIAM J. Comput. 39 (7) (2010)
Asaf Shapira, Raphael Yuster
On the density of a graph and its blowup. J. Comb. Theory, Ser. B 100 (6) (2010)
Asaf Shapira, Raphael Yuster
The effect of induced subgraphs on quasi-randomness. Random Struct. Algorithms 36 (1) (2010)
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
A Unified Framework for Testing Linear-Invariant Properties. FOCS (2010)
Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
A Unified Framework for Testing Linear-Invariant Properties CoRR (2010)
Asaf Nachmias, Asaf Shapira
Testing the expansion of a graph. Inf. Comput. 208 (4) (2010)
Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
Finding Cycles and Trees in Sublinear Time CoRR (2010)
Noga Alon, Asaf Shapira, Uri Stav
Can a Graph Have Distinct Regular Partitions? SIAM J. Discret. Math. 23 (1) (2009)
Artur Czumaj, Asaf Shapira, Christian Sohler
Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. SIAM J. Comput. 38 (6) (2009)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. SIAM J. Comput. 39 (1) (2009)
Asaf Shapira
Green's conjecture and testing linear-invariant properties. STOC (2009)
Asaf Shapira, Raphael Yuster
Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma. Electron. J. Comb. 16 (1) (2009)
Itai Benjamini, Oded Schramm, Asaf Shapira
Every Minor-Closed Property of Sparse Graphs is Testable. Electron. Colloquium Comput. Complex. 15 (010) (2008)
Asaf Shapira
Quasi-randomness and the distribution of copies of a fixed graph. Comb. 28 (6) (2008)
Itai Benjamini, Oded Schramm, Asaf Shapira
Every minor-closed property of sparse graphs is testable. STOC (2008)
Noga Alon, Oded Schwartz, Asaf Shapira
An Elementary Construction of Constant-Degree Expanders. Comb. Probab. Comput. 17 (3) (2008)
Noga Alon, Asaf Shapira
Every Monotone Graph Property Is Testable. SIAM J. Comput. 38 (2) (2008)
Oded Lachish, Ilan Newman, Asaf Shapira
Space Complexity Vs. Query Complexity. Comput. Complex. 17 (1) (2008)
Noga Alon, Asaf Shapira
A separation theorem in property testing. Comb. 28 (3) (2008)
Asaf Shapira, Raphael Yuster
The effect of induced subgraphs on quasi-randomness. SODA (2008)
Noga Alon, Asaf Shapira
A Characterization of the (Natural) Graph Properties Testable with One-Sided Error. SIAM J. Comput. 37 (6) (2008)
Liam Roditty, Asaf Shapira
All-Pairs Shortest Paths with a Sublinear Additive Error. ICALP (1) (2008)
Eyal Even-Dar, Asaf Shapira
A Note on Maximizing the Spread of Influence in Social Networks. WINE (2007)
Eldar Fischer, Arie Matsliah, Asaf Shapira
Approximate Hypergraph Partitioning and Applications. FOCS (2007)
Asaf Nachmias, Asaf Shapira
Testing the Expansion of a Graph. Electron. Colloquium Comput. Complex. 14 (118) (2007)
Artur Czumaj, Asaf Shapira, Christian Sohler
Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs. Electron. Colloquium Comput. Complex. 14 (083) (2007)
Noga Alon, Asaf Shapira, Uri Stav
Can a Graph Have Distinct Regular Partitions? COCOON (2007)
Noga Alon, Oded Schwartz, Asaf Shapira
An elementary construction of constant-degree expanders. SODA (2007)
Asaf Shapira, Raphael Yuster, Uri Zwick
All-pairs bottleneck paths in vertex weighted graphs. SODA (2007)
Oded Lachish, Ilan Newman, Asaf Shapira
Space Complexity vs. Query Complexity. Electron. Colloquium Comput. Complex. 13 (103) (2006)
Noga Alon, Asaf Shapira
A Characterization of Easily Testable Induced Subgraphs. Comb. Probab. Comput. 15 (6) (2006)
Noga Alon, Asaf Shapira, Benny Sudakov
Additive Approximation for Edge-Deletion Problems (Abstract). ICALP (1) (2006)
Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
A combinatorial characterization of the testable graph properties: it's all about regularity. STOC (2006)
Noga Alon, Oded Schwartz, Asaf Shapira
An Elementary Construction of Constant-Degree Expanders. Electron. Colloquium Comput. Complex. 13 (119) (2006)

Asaf Shapira.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Asaf Shapira