![](https://dblp.dagstuhl.de/img/logo.ua.320x120.png)
![](https://dblp.dagstuhl.de/img/dropdown.dark.16x16.png)
![](https://dblp.dagstuhl.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
![search dblp](https://dblp.dagstuhl.de/img/search.dark.16x16.png)
default search action
Asaf Shapira
Person information
Refine list
![note](https://dblp.dagstuhl.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [c32]Asaf Shapira, Henrique Stagni:
A Tight Bound for Testing Partition Properties. SODA 2024: 4305-4320 - 2023
- [j52]Lior Gishboliner
, Asaf Shapira:
On Rödl's Theorem for Cographs. Electron. J. Comb. 30(4) (2023) - [j51]David Conlon, Lior Gishboliner
, Yevgeny Levanzov, Asaf Shapira:
A new bound for the Brown-Erdős-Sós problem. J. Comb. Theory B 158(Part): 1-35 (2023) - [j50]Lior Gishboliner
, Yevgeny Levanzov
, Asaf Shapira
, Raphael Yuster
:
Counting Homomorphic Cycles in Degenerate Graphs. ACM Trans. Algorithms 19(1): 2:1-2:22 (2023) - [c31]Lior Gishboliner
, Nick Kushnir, Asaf Shapira:
Testing Versus Estimation of Graph Properties, Revisited. APPROX/RANDOM 2023: 46:1-46:18 - [i29]Lior Gishboliner
, Nick Kushnir, Asaf Shapira:
Testing versus estimation of graph properties, revisited. CoRR abs/2305.05487 (2023) - [i28]Lior Gishboliner
, Yevgeny Levanzov, Asaf Shapira:
Trimming forests is hard (unless they are made of stars). CoRR abs/2310.11277 (2023) - 2022
- [j49]Asaf Shapira:
Every Orientation of a $4$-Chromatic Graph has a Non-Bipartite Acyclic Subgraph. Electron. J. Comb. 29(1) (2022) - [j48]Suman K. Bera
, Lior Gishboliner
, Yevgeny Levanzov, C. Seshadhri, Asaf Shapira:
Counting Subgraphs in Degenerate Graphs. J. ACM 69(3): 23:1-23:21 (2022) - [c30]Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster:
Counting Homomorphic Cycles in Degenerate Graphs. SODA 2022: 417-430 - 2021
- [j47]Matija Bucic
, Eoin Long, Asaf Shapira, Benny Sudakov:
Tournament Quasirandomness from Local Counting. Comb. 41(2): 175-208 (2021) - [j46]Michal Amir, Asaf Shapira, Mykhaylo Tyomkyn
:
Two Erdős-Hajnal-type theorems in hypergraphs. J. Comb. Theory B 146: 417-438 (2021) - [j45]Lior Gishboliner
, Asaf Shapira, Henrique Stagni:
Testing linear inequalities of subgraph statistics. Random Struct. Algorithms 58(3): 468-479 (2021) - [j44]Asaf Shapira, Mykhaylo Tyomkyn
:
Quasirandom Graphs and the Pantograph Equation. Am. Math. Mon. 128(7): 630-639 (2021) - [j43]Asaf Cohen Antonir, Asaf Shapira:
On Erdős's Method for Bounding the Partition Function. Am. Math. Mon. 128(8): 744-747 (2021) - 2020
- [j42]Shachar Sapir, Asaf Shapira:
The Induced Removal Lemma in Sparse Graphs. Comb. Probab. Comput. 29(1): 153-162 (2020) - [j41]Asaf Ferber, Asaf Shapira:
A quantitative Lovász criterion for Property B. Comb. Probab. Comput. 29(6): 956-960 (2020) - [c29]Lior Gishboliner, Asaf Shapira, Henrique Stagni:
Testing Linear Inequalities of Subgraph Statistics. ITCS 2020: 43:1-43:9 - [i27]Lior Gishboliner, Asaf Shapira, Henrique Stagni:
Testing linear inequalities of subgraph statistics. CoRR abs/2007.10390 (2020) - [i26]Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira:
Counting Subgraphs in Degenerate Graphs. CoRR abs/2010.05998 (2020) - [i25]Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster:
Counting Homomorphic Cycles in Degenerate Graphs. CoRR abs/2011.05957 (2020) - [i24]Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira:
Counting Subgraphs in Degenerate Graphs. Electron. Colloquium Comput. Complex. TR20 (2020) - [i23]Lior Gishboliner, Asaf Shapira, Henrique Stagni:
Testing linear inequalities of subgraph statistics. Electron. Colloquium Comput. Complex. TR20 (2020)
2010 – 2019
- 2019
- [j40]Lior Gishboliner
, Asaf Shapira:
Efficient Removal Without Efficient Regularity. Comb. 39(3): 639-658 (2019) - [j39]Jacob Fox, Lior Gishboliner
, Asaf Shapira, Raphael Yuster:
The removal lemma for tournaments. J. Comb. Theory B 136: 110-134 (2019) - [c28]Lior Gishboliner, Asaf Shapira:
Testing graphs against an unknown distribution. STOC 2019: 535-546 - [i22]Lior Gishboliner, Asaf Shapira:
Testing Graphs against an Unknown Distribution. CoRR abs/1905.09903 (2019) - [i21]Lior Gishboliner, Asaf Shapira:
Testing Graphs against an Unknown Distribution. Electron. Colloquium Comput. Complex. TR19 (2019) - 2018
- [j38]Guy Moshkovitz, Asaf Shapira:
Decomposing a graph into expanding subgraphs. Random Struct. Algorithms 52(1): 158-178 (2018) - [c27]Lior Gishboliner, Asaf Shapira:
Efficient Testing without Efficient Regularity. ITCS 2018: 54:1-54:14 - [c26]Lior Gishboliner, Asaf Shapira:
A generalized Turán problem and its applications. STOC 2018: 760-772 - [i20]Lior Gishboliner, Asaf Shapira:
A Generalized Turan Problem and its Applications. Electron. Colloquium Comput. Complex. TR18 (2018) - 2017
- [j37]Reut Levi, Guy Moshkovitz, Dana Ron
, Ronitt Rubinfeld, Asaf Shapira:
Constructing near spanning trees with few local inspections. Random Struct. Algorithms 50(2): 183-200 (2017) - [c25]Lior Gishboliner, Asaf Shapira:
Removal lemmas with polynomial bounds. STOC 2017: 510-522 - [i19]Lior Gishboliner, Asaf Shapira:
A Generalized Turán Problem and its Applications. CoRR abs/1712.00831 (2017) - 2016
- [j36]Guy Moshkovitz, Asaf Shapira:
A short proof of Gowers' lower bound for the regularity lemma. Comb. 36(2): 187-194 (2016) - [j35]Asaf Shapira, Raphael Yuster:
Unavoidable tournaments. J. Comb. Theory B 116: 191-207 (2016) - 2015
- [j34]Asaf Shapira, Benny Sudakov:
Small complete minors above the extremal edge density. Comb. 35(1): 75-94 (2015) - [j33]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): 407-437 (2015) - [j32]Guy Moshkovitz, Asaf Shapira:
Exact bounds for some hypergraph saturation problems. J. Comb. Theory B 111: 242-248 (2015) - [j31]Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira:
A unified framework for testing linear-invariant properties. Random Struct. Algorithms 46(2): 232-260 (2015) - [c24]Guy Moshkovitz, Asaf Shapira:
Decomposing a Graph Into Expanding Subgraphs. SODA 2015: 1283-1295 - [i18]Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira:
Constructing Near Spanning Trees with Few Local Inspections. CoRR abs/1502.00413 (2015) - [i17]Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira:
Constructing Near Spanning Trees with Few Local Inspections. Electron. Colloquium Comput. Complex. TR15 (2015) - 2014
- [j30]Yair Caro, Asaf Shapira, Raphael Yuster:
Forcing $k$-repetitions in Degree Sequences. Electron. J. Comb. 21(1): 1 (2014) - [j29]Artur Czumaj, Oded Goldreich
, Dana Ron
, C. Seshadhri, Asaf Shapira, Christian Sohler
:
Finding cycles and trees in sublinear time. Random Struct. Algorithms 45(2): 139-184 (2014) - 2013
- [j28]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): 859-873 (2013) - [j27]Subrahmanyam Kalyanasundaram
, Asaf Shapira:
A Note on Even Cycles and Quasirandom Tournaments. J. Graph Theory 73(3): 260-266 (2013) - [i16]Lior Gishboliner, Asaf Shapira:
Deterministic vs Non-deterministic Graph Property Testing. Electron. Colloquium Comput. Complex. TR13 (2013) - 2012
- [j26]Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira:
Testing Odd-Cycle-Freeness in Boolean Functions. Comb. Probab. Comput. 21(6): 835-855 (2012) - [j25]Asaf Shapira, Raphael Yuster:
The quasi-randomness of hypergraph cut properties. Random Struct. Algorithms 40(1): 105-131 (2012) - [j24]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): 15-29 (2012) - [c23]Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira:
Testing odd-cycle-freeness in Boolean functions. SODA 2012: 1140-1149 - [i15]Shiva Kintali, Asaf Shapira:
A Note on the Balanced ST-Connectivity. CoRR abs/1204.0816 (2012) - [i14]Asaf Shapira, Benny Sudakov:
Small Complete Minors Above the Extremal Edge Density. CoRR abs/1208.3568 (2012) - [i13]Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
:
Finding Cycles and Trees in Sublinear Time. Electron. Colloquium Comput. Complex. TR12 (2012) - 2011
- [j23]Asaf Shapira, Raphael Yuster, Uri Zwick:
All-Pairs Bottleneck Paths in Vertex Weighted Graphs. Algorithmica 59(4): 621-633 (2011) - [j22]Eyal Even-Dar, Asaf Shapira:
A note on maximizing the spread of influence in social networks. Inf. Process. Lett. 111(4): 184-187 (2011) - [j21]Ronitt Rubinfeld, Asaf Shapira:
Sublinear Time Algorithms. SIAM J. Discret. Math. 25(4): 1562-1588 (2011) - [j20]Liam Roditty, Asaf Shapira:
All-pairs shortest paths with a sublinear additive error. ACM Trans. Algorithms 7(4): 45:1-45:12 (2011) - [c22]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: 495-506 - [c21]Kevin P. Costello
, Asaf Shapira, Prasad Tetali:
Randomized greedy: new variants of some classic approximation algorithms. SODA 2011: 647-655 - [i12]Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira:
Testing Odd-Cycle-Freeness in Boolean Functions. CoRR abs/1105.1325 (2011) - [i11]Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira:
Testing Odd-Cycle-Freeness in Boolean Functions. Electron. Colloquium Comput. Complex. TR11 (2011) - [i10]Ronitt Rubinfeld, Asaf Shapira:
Sublinear Time Algorithms. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j19]Asaf Nachmias, Asaf Shapira:
Testing the expansion of a graph. Inf. Comput. 208(4): 309-314 (2010) - [j18]Asaf Shapira, Raphael Yuster:
On the density of a graph and its blowup. J. Comb. Theory B 100(6): 704-719 (2010) - [j17]Asaf Shapira, Raphael Yuster:
The effect of induced subgraphs on quasi-randomness. Random Struct. Algorithms 36(1): 90-109 (2010) - [j16]Eldar Fischer, Arie Matsliah, Asaf Shapira:
Approximate Hypergraph Partitioning and Applications. SIAM J. Comput. 39(7): 3155-3185 (2010) - [c20]Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira:
A Unified Framework for Testing Linear-Invariant Properties. FOCS 2010: 478-487 - [p1]Asaf Shapira:
Green's Conjecture and Testing Linear Invariant Properties. Property Testing 2010: 355-358 - [i9]Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler:
Finding Cycles and Trees in Sublinear Time. CoRR abs/1007.4230 (2010) - [i8]Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira:
A Unified Framework for Testing Linear-Invariant Properties. CoRR abs/1010.5016 (2010) - [i7]Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira:
A Unified Framework for Testing Linear-Invariant Properties. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j15]Asaf Shapira, Raphael Yuster:
Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma. Electron. J. Comb. 16(1) (2009) - [j14]Artur Czumaj, Asaf Shapira, Christian Sohler
:
Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. SIAM J. Comput. 38(6): 2499-2510 (2009) - [j13]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): 143-167 (2009) - [j12]Noga Alon, Asaf Shapira, Uri Stav:
Can a Graph Have Distinct Regular Partitions? SIAM J. Discret. Math. 23(1): 278-287 (2009) - [c19]Asaf Shapira:
Green's conjecture and testing linear-invariant properties. STOC 2009: 159-166 - 2008
- [j11]Oded Lachish
, Ilan Newman, Asaf Shapira:
Space Complexity Vs. Query Complexity. Comput. Complex. 17(1): 70-93 (2008) - [j10]Noga Alon, Asaf Shapira:
A separation theorem in property testing. Comb. 28(3): 261-281 (2008) - [j9]Asaf Shapira:
Quasi-randomness and the distribution of copies of a fixed graph. Comb. 28(6): 735-745 (2008) - [j8]Noga Alon, Oded Schwartz, Asaf Shapira:
An Elementary Construction of Constant-Degree Expanders. Comb. Probab. Comput. 17(3): 319-327 (2008) - [j7]Noga Alon, Asaf Shapira:
A Characterization of the (Natural) Graph Properties Testable with One-Sided Error. SIAM J. Comput. 37(6): 1703-1727 (2008) - [j6]Noga Alon, Asaf Shapira:
Every Monotone Graph Property Is Testable. SIAM J. Comput. 38(2): 505-522 (2008) - [c18]Liam Roditty, Asaf Shapira:
All-Pairs Shortest Paths with a Sublinear Additive Error. ICALP (1) 2008: 622-633 - [c17]Asaf Shapira, Raphael Yuster:
The effect of induced subgraphs on quasi-randomness. SODA 2008: 789-798 - [c16]Itai Benjamini, Oded Schramm, Asaf Shapira:
Every minor-closed property of sparse graphs is testable. STOC 2008: 393-402 - [i6]Itai Benjamini, Oded Schramm, Asaf Shapira:
Every Minor-Closed Property of Sparse Graphs is Testable. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [c15]Noga Alon, Asaf Shapira, Uri Stav:
Can a Graph Have Distinct Regular Partitions? COCOON 2007: 428-438 - [c14]Eldar Fischer, Arie Matsliah, Asaf Shapira:
Approximate Hypergraph Partitioning and Applications. FOCS 2007: 579-589 - [c13]Noga Alon, Oded Schwartz, Asaf Shapira:
An elementary construction of constant-degree expanders. SODA 2007: 454-458 - [c12]Asaf Shapira, Raphael Yuster, Uri Zwick:
All-pairs bottleneck paths in vertex weighted graphs. SODA 2007: 978-985 - [c11]Eyal Even-Dar, Asaf Shapira:
A Note on Maximizing the Spread of Influence in Social Networks. WINE 2007: 281-286 - [i5]Artur Czumaj, Asaf Shapira, Christian Sohler
:
Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs. Electron. Colloquium Comput. Complex. TR07 (2007) - [i4]Asaf Nachmias, Asaf Shapira:
Testing the Expansion of a Graph. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [b1]Asaf Shapira:
Graph propert testing and related problems. Tel Aviv University, Israel, 2006 - [j5]Noga Alon, Asaf Shapira:
On An Extremal Hypergraph Problem Of Brown, Erdös And Sós. Comb. 26(6): 627-645 (2006) - [j4]Noga Alon, Asaf Shapira:
A Characterization of Easily Testable Induced Subgraphs. Comb. Probab. Comput. 15(6): 791-805 (2006) - [c10]Oded Lachish
, Ilan Newman, Asaf Shapira:
Space Complexity vs. Query Complexity. APPROX-RANDOM 2006: 426-437 - [c9]Noga Alon, Asaf Shapira, Benny Sudakov:
Additive Approximation for Edge-Deletion Problems (Abstract). ICALP (1) 2006: 1-2 - [c8]Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira:
A combinatorial characterization of the testable graph properties: it's all about regularity. STOC 2006: 251-260 - [i3]Noga Alon, Oded Schwartz, Asaf Shapira:
An Elementary Construction of Constant-Degree Expanders. Electron. Colloquium Comput. Complex. TR06 (2006) - [i2]Oded Lachish, Ilan Newman, Asaf Shapira:
Space Complexity vs. Query Complexity. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j3]Noga Alon, Asaf Shapira:
Linear Equations, Arithmetic Progressions and Hypergraph Property Testing. Theory Comput. 1(1): 177-216 (2005) - [c7]Noga Alon, Asaf Shapira, Benny Sudakov:
Additive Approximation for Edge-Deletion Problems. FOCS 2005: 419-428 - [c6]Noga Alon, Asaf Shapira:
A Characterization of the (natural) Graph Properties Testable with One-Sided Error. FOCS 2005: 429-438 - [c5]Noga Alon, Asaf Shapira:
Linear equations, arithmetic progressions and hypergraph property testing. SODA 2005: 708-717 - [c4]Noga Alon, Asaf Shapira:
Every monotone graph property is testable. STOC 2005: 128-137 - [i1]Asaf Shapira, Noga Alon:
Homomorphisms in Graph Property Testing - A Survey. Electron. Colloquium Comput. Complex. TR05 (2005) - 2004
- [j2]Noga Alon, Asaf Shapira:
Testing subgraphs in directed graphs. J. Comput. Syst. Sci. 69(3): 354-382 (2004) - [c3]Noga Alon, Asaf Shapira:
A characterization of easily testable induced subgraphs. SODA 2004: 942-951 - 2003
- [j1]Noga Alon, Asaf Shapira:
Testing satisfiability. J. Algorithms 47(2): 87-103 (2003) - [c2]Noga Alon, Asaf Shapira:
Testing subgraphs in directed graphs. STOC 2003: 700-709 - 2002
- [c1]Noga Alon, Asaf Shapira:
Testing satisfiability. SODA 2002: 645-654
Coauthor Index
![](https://dblp.dagstuhl.de/img/cog.dark.24x24.png)
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from ,
, and
to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and
to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-08-05 20:21 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint