23 citations · 54 across the 45 of their papers we have counts for
64 papers
A Tight Erdős-Stone Bound for All Graph Densities
Asaf Shapira, Raphael Yuster
The Erdős--Stone Theorem asserts that if a graph has edge density then it contains a complete -partite graph with vertices in each part, where $b=b_n(r,δ) \gg…
Graph k-Coloring in Average Sublinear Time
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2
Graph -coloring is one of the classic NP-complete problems. Previous work has studied its average time complexity, defined to be the average runtime of computing a -coloring…
An Elementary Analysis of the Prime Partition Function
Asaf Cohen Antonir, Asaf Shapira
Let denote the number of ways to write as a sum of primes. In this paper, we show that While sharper estimates are…
On Ramsey Properties of k-Majority Tournaments
Asaf Shapira, Raphael Yuster
A central objective in Ramsey theory is determining whether restricted families of discrete structures necessarily contain substantially larger homogeneous substructures, compared…
Polynomial Property Testing
Lior Gishboliner, Asaf Shapira
Property testers are fast, randomized "election polling"-type algorithms that determine if an input (e.g., graph or hypergraph) has a certain property or is -far from…
Regularity for hypergraphs with bounded VC dimension
Lior Gishboliner, Asaf Shapira, Yuval Wigderson
While Szemerédi's graph regularity lemma is an indispensable tool for studying extremal problems in graph theory, using it comes with a hefty price, since a worst-case graph may on…