Zobrazeno 1 - 10
of 163
pro vyhledávání: '"Kaufman, Tali"'
Coboundary expansion is a high dimensional generalization of the Cheeger constant to simplicial complexes. Originally, this notion was motivated by the fact that it implies topological expansion, but nowadays a significant part of the motivation stem
Externí odkaz:
http://arxiv.org/abs/2411.02819
Autor:
First, Uriya A., Kaufman, Tali
We study sheaves on posets, showing that cosystolic expansion of such sheaves can be derived from local expansion conditions of the sheaf and the poset (typically a high dimensional expander). When the poset at hand is a cell complex, a sheaf on it m
Externí odkaz:
http://arxiv.org/abs/2403.19388
Autor:
Golowich, Louis, Kaufman, Tali
Recent constructions of the first asymptotically good quantum LDPC (qLDPC) codes led to two breakthroughs in complexity theory: the NLTS (No Low-Energy Trivial States) theorem (Anshu, Breuckmann, and Nirkhe, STOC'23), and explicit lower bounds agains
Externí odkaz:
http://arxiv.org/abs/2311.09503
Autor:
Gotlib, Roy, Kaufman, Tali
"No Where to go but in" is a well known statement of Osho. Osho meant to say that the answers to all our questions should be obtained by looking into ourselves. In a paraphrase to Osho's statement we say "No Where to go but high". This meant to demon
Externí odkaz:
http://arxiv.org/abs/2304.10106
Autor:
Kaufman, Tali, Mass, David
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 product) spaces, where Fourier Analysis methods could be applied. In this
Externí odkaz:
http://arxiv.org/abs/2211.09485
Autor:
Kaufman, Tali, Mass, David
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 sampling and list-decoding algorithms, and more. Within that, an important
Externí odkaz:
http://arxiv.org/abs/2211.09482
Autor:
Gotlib, Roy, Kaufman, Tali
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 assignment. The tester is then tasked with testing whether these local assign
Externí odkaz:
http://arxiv.org/abs/2210.15714
Autor:
Gotlib, Roy, Kaufman, Tali
One of the most important properties of high dimensional expanders is that high dimensional random walks converge rapidly. This property has proven to be extremely useful in variety of fields in the theory of computer science from agreement testing t
Externí odkaz:
http://arxiv.org/abs/2208.03241
Autor:
First, Uriya A., Kaufman, Tali
We expose a strong connection between good $2$-query locally testable codes (LTCs) and high dimensional expanders. Here, an LTC is called good if it has constant rate and linear distance. Our emphasis in this work is on LTCs testable with only $2$ qu
Externí odkaz:
http://arxiv.org/abs/2208.01778
Autor:
First, Uriya A., Kaufman, Tali
The Cheeger constant of a graph, or equivalently its coboundary expansion, quantifies the expansion of the graph. This notion assumes an implicit choice of a coefficient group, namely, $\mathbb{F}_2$. In this paper, we study Cheeger-type inequalities
Externí odkaz:
http://arxiv.org/abs/2208.01776