From the 1 of 11 linked papers with an AI index.
11 papers
Graph k-Coloring in Average Sublinear Time
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2
The paper presents an algorithm that colors k‑colorable graphs in expected O(nk) time, breaking the long‑standing quadratic average‑case barrier and achieving linear time for const…
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 ar…
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…
Is it easy to regularize a hypergraph with easy links?
Lior Gishboliner, Asaf Shapira, Yuval Wigderson
A partition of a (hyper)graph is -homogenous if the edge densities between almost all clusters are either at most or at least . Suppose a…
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 o…