Asaf Shapira - RankMe

124 papers A* 23A 4Misc 1Journal 89Unranked 5

Year	Rank	Type	Title / Venue / Authors
2025	A	`conf`	A Fast Coloring Oracle for Average Case Hypergraphs. APPROX/RANDOM Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber
2025	J	`jnl`	A Fast Coloring Oracle for Average Case Hypergraphs. CoRR Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld, Asaf Shapira, Shlomo Tauber
2025	J	`jnl`	Hardness of Hypergraph Edge Modification Problems. CoRR Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
2025	J	`jnl`	Polynomial Property Testing. CoRR Lior Gishboliner, Asaf Shapira
2025	J	`jnl`	Polynomial property testing. Comput. Sci. Rev. Lior Gishboliner, Asaf Shapira
2024	A*	`conf`	A Tight Bound for Testing Partition Properties. SODA Asaf Shapira, Henrique Stagni
2024	J	`jnl`	A generalisation of Varnavides's theorem. Comb. Probab. Comput. Asaf Shapira
2024	J	`jnl`	Bounding the number of odd paths in planar graphs via convex optimization. J. Graph Theory Asaf Cohen Antonir, Asaf Shapira
2024	J	`jnl`	Testing versus estimation of graph properties, revisited. Random Struct. Algorithms Asaf Shapira, Nick Kushnir, Lior Gishboliner
2024	J	`jnl`	Trimming Forests Is Hard (Unless They Are Made of Stars). SIAM J. Discret. Math. Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
2023	J	`jnl`	A new bound for the Brown-Erdős-Sós problem. J. Comb. Theory B David Conlon, Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
2023	J	`jnl`	Counting Homomorphic Cycles in Degenerate Graphs. ACM Trans. Algorithms Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster
2023	J	`jnl`	On Rödl's Theorem for Cographs. Electron. J. Comb. Lior Gishboliner, Asaf Shapira
2023	A	`conf`	Testing Versus Estimation of Graph Properties, Revisited. APPROX/RANDOM Lior Gishboliner, Nick Kushnir, Asaf Shapira
2023	J	`jnl`	Testing versus estimation of graph properties, revisited. CoRR Lior Gishboliner, Nick Kushnir, Asaf Shapira
2023	J	`jnl`	Trimming forests is hard (unless they are made of stars). CoRR Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
2022	A*	`conf`	Counting Homomorphic Cycles in Degenerate Graphs. SODA Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster
2022	J	`jnl`	Counting Subgraphs in Degenerate Graphs. J. ACM Suman K. Bera, Lior Gishboliner, Yevgeny Levanzov, C. Seshadhri, Asaf Shapira
2022	J	`jnl`	Every Orientation of a $4$-Chromatic Graph has a Non-Bipartite Acyclic Subgraph. Electron. J. Comb. Asaf Shapira
2021	J	`jnl`	On Erdős's Method for Bounding the Partition Function. Am. Math. Mon. Asaf Cohen Antonir, Asaf Shapira
2021	J	`jnl`	Quasirandom Graphs and the Pantograph Equation. Am. Math. Mon. Asaf Shapira, Mykhaylo Tyomkyn
2021	J	`jnl`	Testing linear inequalities of subgraph statistics. Random Struct. Algorithms Lior Gishboliner, Asaf Shapira, Henrique Stagni
2021	J	`jnl`	Tournament Quasirandomness from Local Counting. Comb. Matija Bucic, Eoin Long, Asaf Shapira, Benny Sudakov
2021	J	`jnl`	Two Erdős-Hajnal-type theorems in hypergraphs. J. Comb. Theory B Michal Amir, Asaf Shapira, Mykhaylo Tyomkyn
2020	J	`jnl`	A quantitative Lovász criterion for Property B. Comb. Probab. Comput. Asaf Ferber, Asaf Shapira
2020	J	`jnl`	Counting Homomorphic Cycles in Degenerate Graphs. CoRR Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira, Raphael Yuster
2020	J	`jnl`	Counting Subgraphs in Degenerate Graphs. CoRR Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
2020	J	`jnl`	Counting Subgraphs in Degenerate Graphs. Electron. Colloquium Comput. Complex. Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
2020	A	`conf`	Testing Linear Inequalities of Subgraph Statistics. ITCS Lior Gishboliner, Asaf Shapira, Henrique Stagni
2020	J	`jnl`	Testing linear inequalities of subgraph statistics. CoRR Lior Gishboliner, Asaf Shapira, Henrique Stagni
2020	J	`jnl`	Testing linear inequalities of subgraph statistics. Electron. Colloquium Comput. Complex. Lior Gishboliner, Asaf Shapira, Henrique Stagni
2020	J	`jnl`	The Induced Removal Lemma in Sparse Graphs. Comb. Probab. Comput. Shachar Sapir, Asaf Shapira
2019	J	`jnl`	Efficient Removal Without Efficient Regularity. Comb. Lior Gishboliner, Asaf Shapira
2019	J	`jnl`	Testing Graphs against an Unknown Distribution. CoRR Lior Gishboliner, Asaf Shapira
2019	J	`jnl`	Testing Graphs against an Unknown Distribution. Electron. Colloquium Comput. Complex. Lior Gishboliner, Asaf Shapira
2019	A*	`conf`	Testing graphs against an unknown distribution. STOC Lior Gishboliner, Asaf Shapira
2019	J	`jnl`	The removal lemma for tournaments. J. Comb. Theory B Jacob Fox, Lior Gishboliner, Asaf Shapira, Raphael Yuster
2018	J	`jnl`	A Generalized Turan Problem and its Applications. Electron. Colloquium Comput. Complex. Lior Gishboliner, Asaf Shapira
2018	A*	`conf`	A generalized Turán problem and its applications. STOC Lior Gishboliner, Asaf Shapira
2018	J	`jnl`	Decomposing a graph into expanding subgraphs. Random Struct. Algorithms Guy Moshkovitz, Asaf Shapira
2018	A	`conf`	Efficient Testing without Efficient Regularity. ITCS Lior Gishboliner, Asaf Shapira
2017	J	`jnl`	A Generalized Turán Problem and its Applications. CoRR Lior Gishboliner, Asaf Shapira
2017	J	`jnl`	Constructing near spanning trees with few local inspections. Random Struct. Algorithms Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2017	A*	`conf`	Removal lemmas with polynomial bounds. STOC Lior Gishboliner, Asaf Shapira
2016	J	`jnl`	A short proof of Gowers' lower bound for the regularity lemma. Comb. Guy Moshkovitz, Asaf Shapira
2016	J	`jnl`	Unavoidable tournaments. J. Comb. Theory B Asaf Shapira, Raphael Yuster
2015	J	`jnl`	A unified framework for testing linear-invariant properties. Random Struct. Algorithms Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
2015	J	`jnl`	An Optimal Algorithm for Finding Frieze-Kannan Regular Partitions. Comb. Probab. Comput. Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtech Rödl, Asaf Shapira
2015	J	`jnl`	Constructing Near Spanning Trees with Few Local Inspections. CoRR Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2015	J	`jnl`	Constructing Near Spanning Trees with Few Local Inspections. Electron. Colloquium Comput. Complex. Reut Levi, Guy Moshkovitz, Dana Ron, Ronitt Rubinfeld, Asaf Shapira
2015	A*	`conf`	Decomposing a Graph Into Expanding Subgraphs. SODA Guy Moshkovitz, Asaf Shapira
2015	J	`jnl`	Exact bounds for some hypergraph saturation problems. J. Comb. Theory B Guy Moshkovitz, Asaf Shapira
2015	J	`jnl`	Small complete minors above the extremal edge density. Comb. Asaf Shapira, Benny Sudakov
2014	J	`jnl`	Finding cycles and trees in sublinear time. Random Struct. Algorithms Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2014	J	`jnl`	Forcing $k$-repetitions in Degree Sequences. Electron. J. Comb. Yair Caro, Asaf Shapira, Raphael Yuster
2013	J	`jnl`	A Note on Even Cycles and Quasirandom Tournaments. J. Graph Theory Subrahmanyam Kalyanasundaram, Asaf Shapira
2013	J	`jnl`	Deterministic vs Non-deterministic Graph Property Testing. Electron. Colloquium Comput. Complex. Lior Gishboliner, Asaf Shapira
2013	J	`jnl`	Large Feedback Arc Sets, High Minimum Degree Subgraphs, and Long Cycles in Eulerian Digraphs. Comb. Probab. Comput. Hao Huang, Jie Ma, Asaf Shapira, Benny Sudakov, Raphael Yuster
2012	J	`jnl`	A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma. SIAM J. Discret. Math. Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtech Rödl, Asaf Shapira
2012	J	`jnl`	A Note on the Balanced ST-Connectivity CoRR Shiva Kintali, Asaf Shapira
2012	J	`jnl`	Finding Cycles and Trees in Sublinear Time. Electron. Colloquium Comput. Complex. Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2012	J	`jnl`	Small Complete Minors Above the Extremal Edge Density CoRR Asaf Shapira, Benny Sudakov
2012	J	`jnl`	Testing Odd-Cycle-Freeness in Boolean Functions. Comb. Probab. Comput. Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
2012	A*	`conf`	Testing odd-cycle-freeness in Boolean functions. SODA Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
2012	J	`jnl`	The quasi-randomness of hypergraph cut properties. Random Struct. Algorithms Asaf Shapira, Raphael Yuster
2011	—	`conf`	A Deterministic Algorithm for the Frieze-Kannan Regularity Lemma. APPROX-RANDOM Domingos Dellamonica Jr., Subrahmanyam Kalyanasundaram, Daniel M. Martin, Vojtech Rödl, Asaf Shapira
2011	J	`jnl`	A note on maximizing the spread of influence in social networks. Inf. Process. Lett. Eyal Even-Dar, Asaf Shapira
2011	J	`jnl`	All-Pairs Bottleneck Paths in Vertex Weighted Graphs. Algorithmica Asaf Shapira, Raphael Yuster, Uri Zwick
2011	J	`jnl`	All-pairs shortest paths with a sublinear additive error. ACM Trans. Algorithms Liam Roditty, Asaf Shapira
2011	A*	`conf`	Randomized greedy: new variants of some classic approximation algorithms. SODA Kevin P. Costello, Asaf Shapira, Prasad Tetali
2011	J	`jnl`	Sublinear Time Algorithms. Electron. Colloquium Comput. Complex. Ronitt Rubinfeld, Asaf Shapira
2011	J	`jnl`	Sublinear Time Algorithms. SIAM J. Discret. Math. Ronitt Rubinfeld, Asaf Shapira
2011	J	`jnl`	Testing Odd-Cycle-Freeness in Boolean Functions CoRR Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
2011	J	`jnl`	Testing Odd-Cycle-Freeness in Boolean Functions. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Elena Grigorescu, Prasad Raghavendra, Asaf Shapira
2010	J	`jnl`	A Unified Framework for Testing Linear-Invariant Properties CoRR Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
2010	A*	`conf`	A Unified Framework for Testing Linear-Invariant Properties. FOCS Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
2010	J	`jnl`	A Unified Framework for Testing Linear-Invariant Properties. Electron. Colloquium Comput. Complex. Arnab Bhattacharyya, Elena Grigorescu, Asaf Shapira
2010	J	`jnl`	Approximate Hypergraph Partitioning and Applications. SIAM J. Comput. Eldar Fischer, Arie Matsliah, Asaf Shapira
2010	J	`jnl`	Finding Cycles and Trees in Sublinear Time CoRR Artur Czumaj, Oded Goldreich, Dana Ron, C. Seshadhri, Asaf Shapira, Christian Sohler
2010	—	`ch.`	Green's Conjecture and Testing Linear Invariant Properties. Property Testing Asaf Shapira
2010	J	`jnl`	On the density of a graph and its blowup. J. Comb. Theory B Asaf Shapira, Raphael Yuster
2010	J	`jnl`	Testing the expansion of a graph. Inf. Comput. Asaf Nachmias, Asaf Shapira
2010	J	`jnl`	The effect of induced subgraphs on quasi-randomness. Random Struct. Algorithms Asaf Shapira, Raphael Yuster
2009	J	`jnl`	A Combinatorial Characterization of the Testable Graph Properties: It's All About Regularity. SIAM J. Comput. Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
2009	J	`jnl`	Can a Graph Have Distinct Regular Partitions? SIAM J. Discret. Math. Noga Alon, Asaf Shapira, Uri Stav
2009	A*	`conf`	Green's conjecture and testing linear-invariant properties. STOC Asaf Shapira
2009	J	`jnl`	Multigraphs (Only) Satisfy a Weak Triangle Removal Lemma. Electron. J. Comb. Asaf Shapira, Raphael Yuster
2009	J	`jnl`	Testing Hereditary Properties of Nonexpanding Bounded-Degree Graphs. SIAM J. Comput. Artur Czumaj, Asaf Shapira, Christian Sohler
2008	J	`jnl`	A Characterization of the (Natural) Graph Properties Testable with One-Sided Error. SIAM J. Comput. Noga Alon, Asaf Shapira
2008	J	`jnl`	A separation theorem in property testing. Comb. Noga Alon, Asaf Shapira
2008	—	`conf`	All-Pairs Shortest Paths with a Sublinear Additive Error. ICALP (1) Liam Roditty, Asaf Shapira
2008	J	`jnl`	An Elementary Construction of Constant-Degree Expanders. Comb. Probab. Comput. Noga Alon, Oded Schwartz, Asaf Shapira
2008	J	`jnl`	Every Minor-Closed Property of Sparse Graphs is Testable. Electron. Colloquium Comput. Complex. Itai Benjamini, Oded Schramm, Asaf Shapira
2008	J	`jnl`	Every Monotone Graph Property Is Testable. SIAM J. Comput. Noga Alon, Asaf Shapira
2008	A*	`conf`	Every minor-closed property of sparse graphs is testable. STOC Itai Benjamini, Oded Schramm, Asaf Shapira
2008	J	`jnl`	Quasi-randomness and the distribution of copies of a fixed graph. Comb. Asaf Shapira
2008	J	`jnl`	Space Complexity Vs. Query Complexity. Comput. Complex. Oded Lachish, Ilan Newman, Asaf Shapira
2008	A*	`conf`	The effect of induced subgraphs on quasi-randomness. SODA Asaf Shapira, Raphael Yuster
2007	—	`conf`	A Note on Maximizing the Spread of Influence in Social Networks. WINE Eyal Even-Dar, Asaf Shapira
2007	A*	`conf`	All-pairs bottleneck paths in vertex weighted graphs. SODA Asaf Shapira, Raphael Yuster, Uri Zwick
2007	A*	`conf`	An elementary construction of constant-degree expanders. SODA Noga Alon, Oded Schwartz, Asaf Shapira
2007	A*	`conf`	Approximate Hypergraph Partitioning and Applications. FOCS Eldar Fischer, Arie Matsliah, Asaf Shapira
2007	Misc	`conf`	Can a Graph Have Distinct Regular Partitions? COCOON Noga Alon, Asaf Shapira, Uri Stav
2007	J	`jnl`	Testing Hereditary Properties of Non-Expanding Bounded-Degree Graphs. Electron. Colloquium Comput. Complex. Artur Czumaj, Asaf Shapira, Christian Sohler
2007	J	`jnl`	Testing the Expansion of a Graph. Electron. Colloquium Comput. Complex. Asaf Nachmias, Asaf Shapira
2006	J	`jnl`	A Characterization of Easily Testable Induced Subgraphs. Comb. Probab. Comput. Noga Alon, Asaf Shapira
2006	A*	`conf`	A combinatorial characterization of the testable graph properties: it's all about regularity. STOC Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira
2006	—	`conf`	Additive Approximation for Edge-Deletion Problems (Abstract). ICALP (1) Noga Alon, Asaf Shapira, Benny Sudakov
2006	J	`jnl`	An Elementary Construction of Constant-Degree Expanders. Electron. Colloquium Comput. Complex. Noga Alon, Oded Schwartz, Asaf Shapira
2006	—	`—`	Graph propert testing and related problems Asaf Shapira
2006	J	`jnl`	On An Extremal Hypergraph Problem Of Brown, Erdös And Sós. Comb. Noga Alon, Asaf Shapira
2006	—	`conf`	Space Complexity vs. Query Complexity. APPROX-RANDOM Oded Lachish, Ilan Newman, Asaf Shapira
2006	J	`jnl`	Space Complexity vs. Query Complexity. Electron. Colloquium Comput. Complex. Oded Lachish, Ilan Newman, Asaf Shapira
2005	A*	`conf`	A Characterization of the (natural) Graph Properties Testable with One-Sided Error. FOCS Noga Alon, Asaf Shapira
2005	A*	`conf`	Additive Approximation for Edge-Deletion Problems. FOCS Noga Alon, Asaf Shapira, Benny Sudakov
2005	A*	`conf`	Every monotone graph property is testable. STOC Noga Alon, Asaf Shapira
2005	J	`jnl`	Homomorphisms in Graph Property Testing - A Survey Electron. Colloquium Comput. Complex. Asaf Shapira, Noga Alon
2005	J	`jnl`	Linear Equations, Arithmetic Progressions and Hypergraph Property Testing. Theory Comput. Noga Alon, Asaf Shapira
2005	A*	`conf`	Linear equations, arithmetic progressions and hypergraph property testing. SODA Noga Alon, Asaf Shapira
2004	A*	`conf`	A characterization of easily testable induced subgraphs. SODA Noga Alon, Asaf Shapira
2004	J	`jnl`	Testing subgraphs in directed graphs. J. Comput. Syst. Sci. Noga Alon, Asaf Shapira
2003	J	`jnl`	Testing satisfiability. J. Algorithms Noga Alon, Asaf Shapira
2003	A*	`conf`	Testing subgraphs in directed graphs. STOC Noga Alon, Asaf Shapira
2002	A*	`conf`	Testing satisfiability. SODA Noga Alon, Asaf Shapira