23 citations · 98 across the 30 of their papers we have counts for
13 papers · 1 filter
Improved Small Set Expansion in High Dimensional Expanders
Tali Kaufman, David Mass
Small set high dimensional expansion over general sheaves has recently became central to several major breakthroughs. These include the construction of classical locally testable a…
List Decoding Quotient Reed-Muller Codes
Omri Gotlib, Tali Kaufman, Shachar Lovett
Reed-Muller codes consist of evaluations of -variate polynomials over a finite field with degree at most . Much like every linear code, Reed-Muller codes can be…
Double Balanced Sets in High Dimensional Expanders
Tali Kaufman, David Mass
Recent works have shown that expansion of pseudorandom sets is of great importance. However, all current works on pseudorandom sets are limited only to product (or approximate prod…
Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion
Tali Kaufman, David Mass
In recent years, high dimensional expanders have been found to have a variety of applications in theoretical computer science, such as efficient CSPs approximations, improved sampl…
List Agreement Expansion from Coboundary Expansion
Roy Gotlib, Tali Kaufman
One of the key components in PCP constructions are agreement tests. In agreement test the tester is given access to subsets of fixed size of some set, each equipped with an assignm…
Improved Optimal Testing Results from Global Hypercontractivity
Tali Kaufman, Dor Minzer
The problem of testing low-degree polynomials has received significant attention over the years due to its importance in theoretical computer science, and in particular in complexi…