23 citations · 54 across the 45 of their papers we have counts for
6 papers · 1 filter
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…
A Fast Coloring Oracle for Average Case Hypergraphs
Cassandra Marcussen, Edward Pyne, Ronitt Rubinfeld +2
Hypergraph -colorability is one of the classical NP-hard problems. Person and Schacht [SODA'09] designed a deterministic algorithm whose expected running time is polynomial over…
When does a tree activate the random graph?
Asaf Cohen Antonir, Yuval Peled, Asaf Shapira +2
Let and be two graphs. A spanning subgraph of is called weakly -saturated if one can add to the edges of in some order, so that whenever a ne…
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…
Hardness of Hypergraph Edge Modification Problems
Lior Gishboliner, Yevgeny Levanzov, Asaf Shapira
For a fixed graph , let denote the size of the largest -free subgraph of . Computing or estimating for various pairs is one of the central proble…