20 Search Results for "Kaufman, Tali"

Document
DOI: 10.4230/LIPIcs.ITCS.2024.54
NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes

Authors: Louis Golowich and Tali Kaufman

Published in: LIPIcs, Volume 287, 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)

Abstract
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 against a linear number of levels of the Sum-of-Squares (SoS) hierarchy (Hopkins and Lin, FOCS'22). In this work, we obtain improvements to both of these results using qLDPC codes of low rate: - Whereas Anshu et al. only obtained NLTS Hamiltonians from qLDPC codes of linear dimension, we show the stronger result that qLDPC codes of arbitrarily small positive dimension yield NLTS Hamiltonians. - The SoS lower bounds of Hopkins and Lin are only weakly explicit because they require running Gaussian elimination to find a nontrivial codeword, which takes polynomial time. We resolve this shortcoming by introducing a new method of planting a strongly explicit nontrivial codeword in linear-distance qLDPC codes, which in turn yields strongly explicit SoS lower bounds. Our "planted" qLDPC codes may be of independent interest, as they provide a new way of ensuring a qLDPC code has positive dimension without resorting to parity check counting, and therefore provide more flexibility in the code construction.
Cite as

Louis Golowich and Tali Kaufman. NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 287, pp. 54:1-54:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{golowich_et_al:LIPIcs.ITCS.2024.54,
  author =	{Golowich, Louis and Kaufman, Tali},
  title =	{{NLTS Hamiltonians and Strongly-Explicit SoS Lower Bounds from Low-Rate Quantum LDPC Codes}},
  booktitle =	{15th Innovations in Theoretical Computer Science Conference (ITCS 2024)},
  pages =	{54:1--54:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-309-6},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{287},
  editor =	{Guruswami, Venkatesan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2024.54},
  URN =		{urn:nbn:de:0030-drops-195829},
  doi =		{10.4230/LIPIcs.ITCS.2024.54},
  annote =	{Keywords: NLTS Hamiltonian, Quantum PCP, Sum-of-squares lower bound, Quantum LDPC code}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2023.49
Fine Grained Analysis of High Dimensional Random Walks

Authors: Roy Gotlib and Tali Kaufman

Published in: LIPIcs, Volume 275, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)

Abstract
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 a variety of fields in the theory of computer science from agreement testing to sampling, coding theory and more. In this paper we present a state of the art result in a line of works analyzing the convergence of high dimensional random walks [Tali Kaufman and David Mass, 2017; Irit Dinur and Tali Kaufman, 2017; Tali Kaufman and Izhar Oppenheim, 2018; Vedat Levi Alev and Lap Chi Lau, 2020], by presenting a structured version of the result of [Vedat Levi Alev and Lap Chi Lau, 2020]. While previous works examined the expansion in the viewpoint of the worst possible eigenvalue, in this work we relate the expansion of a function to the entire spectrum of the random walk operator using the structure of the function; We call such a theorem a Fine Grained High Order Random Walk Theorem. In sufficiently structured cases the fine grained result that we present here can be much better than the worst case while in the worst case our result is equivalent to [Vedat Levi Alev and Lap Chi Lau, 2020]. In order to prove the Fine Grained High Order Random Walk Theorem we introduce a way to bootstrap the expansion of random walks on the vertices of a complex into a fine grained understanding of higher order random walks, provided that the expansion is good enough. In addition, our single bootstrapping theorem can simultaneously yield our Fine Grained High Order Random Walk Theorem as well as the well known Trickling down Theorem. Prior to this work, High order Random walks theorems and Tricking down Theorem have been obtained from different proof methods.
Cite as

Roy Gotlib and Tali Kaufman. Fine Grained Analysis of High Dimensional Random Walks. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 275, pp. 49:1-49:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gotlib_et_al:LIPIcs.APPROX/RANDOM.2023.49,
  author =	{Gotlib, Roy and Kaufman, Tali},
  title =	{{Fine Grained Analysis of High Dimensional Random Walks}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2023)},
  pages =	{49:1--49:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-296-9},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{275},
  editor =	{Megow, Nicole and Smith, Adam},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2023.49},
  URN =		{urn:nbn:de:0030-drops-188740},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2023.49},
  annote =	{Keywords: High Dimensional Expanders, High Dimensional Random Walks, Local Spectral Expansion, Local to Global, Trickling Down}
}
Document
DOI: 10.4230/LIPIcs.CCC.2023.10
An Improved Trickle down Theorem for Partite Complexes

Authors: Dorna Abdolazimi and Shayan Oveis Gharan

Published in: LIPIcs, Volume 264, 38th Computational Complexity Conference (CCC 2023)

Abstract
We prove a strengthening of the trickle down theorem for partite complexes. Given a (d+1)-partite d-dimensional simplicial complex, we show that if "on average" the links of faces of co-dimension 2 are (1-δ)/d-(one-sided) spectral expanders, then the link of any face of co-dimension k is an O((1-δ)/(kδ))-(one-sided) spectral expander, for all 3 ≤ k ≤ d+1. For an application, using our theorem as a black-box, we show that links of faces of co-dimension k in recent constructions of bounded degree high dimensional expanders have spectral expansion at most O(1/k) fraction of the spectral expansion of the links of the worst faces of co-dimension 2.
Cite as

Dorna Abdolazimi and Shayan Oveis Gharan. An Improved Trickle down Theorem for Partite Complexes. In 38th Computational Complexity Conference (CCC 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 264, pp. 10:1-10:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{abdolazimi_et_al:LIPIcs.CCC.2023.10,
  author =	{Abdolazimi, Dorna and Oveis Gharan, Shayan},
  title =	{{An Improved Trickle down Theorem for Partite Complexes}},
  booktitle =	{38th Computational Complexity Conference (CCC 2023)},
  pages =	{10:1--10:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-282-2},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{264},
  editor =	{Ta-Shma, Amnon},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2023.10},
  URN =		{urn:nbn:de:0030-drops-182807},
  doi =		{10.4230/LIPIcs.CCC.2023.10},
  annote =	{Keywords: Simplicial complexes, High dimensional expanders, Trickle down theorem, Bounded degree high dimensional expanders, Locally testable codes, Random walks}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.61
List Agreement Expansion from Coboundary Expansion

Authors: Roy Gotlib and Tali Kaufman

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
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 assignments agree with some global assignment over the entire set. One natural generalization of this concept is the case where, instead of a single assignment to each local view, the tester is given access to l different assignments for every subset. The tester is then tasked with testing whether there exist l global functions that agree with all of the assignments of all of the local views. In this work we present sufficient condition for a set system to exhibit this generalized definition of list agreement expansion. This is, to our knowledge, the first work to consider this natural generalization of agreement testing. Despite initially appearing very similar to agreement expansion in definition, proving that a set system exhibits list agreement expansion seem to require a different set of techniques. This is due to the fact that the natural extension of agreement testing (i.e. that there exists a pairing of the lists such that each pair agrees with each other) does not suffice when testing for list agreement as list agreement crucially relies on a global structure. It follows that if a local assignments satisfy list agreement they must not only agree locally but also exhibit some additional structure. In order to test for the existence of this additional structure we use the connection between covering spaces of a high dimensional complex and its coboundaries. Specifically, we use this connection as a form of "decoupling". Moreover, we show that any set system that exhibits list agreement expansion also supports direct sum testing. This is the first scheme for direct sum testing that works regardless of the parity of the sizes of the local sets. Prior to our work the schemes for direct sum testing were based on the parity of the sizes of the local tests.
Cite as

Roy Gotlib and Tali Kaufman. List Agreement Expansion from Coboundary Expansion. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 61:1-61:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{gotlib_et_al:LIPIcs.ITCS.2023.61,
  author =	{Gotlib, Roy and Kaufman, Tali},
  title =	{{List Agreement Expansion from Coboundary Expansion}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{61:1--61:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.61},
  URN =		{urn:nbn:de:0030-drops-175647},
  doi =		{10.4230/LIPIcs.ITCS.2023.61},
  annote =	{Keywords: High dimensional Expanders, Property Testing, Agreement Testing}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2023.78
Garland’s Technique for Posets and High Dimensional Grassmannian Expanders

Authors: Tali Kaufman and Ran J. Tessler

Published in: LIPIcs, Volume 251, 14th Innovations in Theoretical Computer Science Conference (ITCS 2023)

Abstract
Local to global machinery plays an important role in the study of simplicial complexes, since the seminal work of Garland [Garland, 1973] to our days. In this work we develop a local to global machinery for general posets. We show that the high dimensional expansion notions and many recent expansion results have a generalization to posets. Examples are fast convergence of high dimensional random walks generalizing [Kaufman et al., 2020], [Alev and Lau, 2020], an equivalence with a global random walk definition, generalizing [Dikstein et al., 2018] and a trickling down theorem, generalizing [Oppenheim, 2018]. In particular, we show that some posets, such as the Grassmannian poset, exhibit qualitatively stronger trickling down effect than simplicial complexes. Using these methods, and the novel idea of posetification to Ramanujan complexes [Lubotzky et al., 2005a], [Lubotzky et al., 2005b], we construct a constant degree expanding Grassmannian poset, and analyze its expansion. This it the first construction of such object, whose existence was conjectured in [Dikstein et al., 2018].
Cite as

Tali Kaufman and Ran J. Tessler. Garland’s Technique for Posets and High Dimensional Grassmannian Expanders. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 251, pp. 78:1-78:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.ITCS.2023.78,
  author =	{Kaufman, Tali and Tessler, Ran J.},
  title =	{{Garland’s Technique for Posets and High Dimensional Grassmannian Expanders}},
  booktitle =	{14th Innovations in Theoretical Computer Science Conference (ITCS 2023)},
  pages =	{78:1--78:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-263-1},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{251},
  editor =	{Tauman Kalai, Yael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2023.78},
  URN =		{urn:nbn:de:0030-drops-175819},
  doi =		{10.4230/LIPIcs.ITCS.2023.78},
  annote =	{Keywords: High dimensional Expanders, Posets, Grassmannian, Garland Method}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.3
Double Balanced Sets in High Dimensional Expanders

Authors: Tali Kaufman and David Mass

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
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 work we ask the natural question whether pseudorandom sets are relevant in domains where Fourier Analysis methods cannot be applied, e.g., one-sided local spectral expanders. We take the first step in the path of answering this question. We put forward a new definition for pseudorandom sets, which we call "double balanced sets". We demonstrate the strength of our new definition by showing that small double balanced sets in one-sided local spectral expanders have very strong expansion properties, such as unique-neighbor-like expansion. We further show that cohomologies in cosystolic expanders are double balanced, and use the newly derived strong expansion properties of double balanced sets in order to obtain an exponential improvement over the current state of the art lower bound on their minimal distance.
Cite as

Tali Kaufman and David Mass. Double Balanced Sets in High Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 3:1-3:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2022.3,
  author =	{Kaufman, Tali and Mass, David},
  title =	{{Double Balanced Sets in High Dimensional Expanders}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{3:1--3:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.3},
  URN =		{urn:nbn:de:0030-drops-171257},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.3},
  annote =	{Keywords: High dimensional expanders, Double balanced sets, Pseudorandom functions}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.5
High Dimensional Expansion Implies Amplified Local Testability

Authors: Tali Kaufman and Izhar Oppenheim

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
In this work, we define a notion of local testability of codes that is strictly stronger than the basic one (studied e.g., by recent works on high rate LTCs), and we term it amplified local testability. Amplified local testability is a notion close to the result of optimal testing for Reed-Muller codes achieved by Bhattacharyya et al. We present a scheme to get amplified locally testable codes from high dimensional expanders. We show that single orbit Affine invariant codes, and in particular Reed-Muller codes, can be described via our scheme, and hence are amplified locally testable. This gives the strongest currently known testability result of single orbit affine invariant codes, strengthening the celebrated result of Kaufman and Sudan.
Cite as

Tali Kaufman and Izhar Oppenheim. High Dimensional Expansion Implies Amplified Local Testability. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 5:1-5:10, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2022.5,
  author =	{Kaufman, Tali and Oppenheim, Izhar},
  title =	{{High Dimensional Expansion Implies Amplified Local Testability}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{5:1--5:10},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.5},
  URN =		{urn:nbn:de:0030-drops-171276},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.5},
  annote =	{Keywords: Locally testable codes, High dimensional expanders, Amplified testing}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2022.16
Eigenstripping, Spectral Decay, and Edge-Expansion on Posets

Authors: Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang

Published in: LIPIcs, Volume 245, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)

Abstract
Fast mixing of random walks on hypergraphs (simplicial complexes) has recently led to myriad breakthroughs throughout theoretical computer science. Many important applications, however, (e.g. to LTCs, 2-2 games) rely on a more general class of underlying structures called posets, and crucially take advantage of non-simplicial structure. These works make it clear that the global expansion properties of posets depend strongly on their underlying architecture (e.g. simplicial, cubical, linear algebraic), but the overall phenomenon remains poorly understood. In this work, we quantify the advantage of different poset architectures in both a spectral and combinatorial sense, highlighting how regularity controls the spectral decay and edge-expansion of corresponding random walks. We show that the spectra of walks on expanding posets (Dikstein, Dinur, Filmus, Harsha APPROX-RANDOM 2018) concentrate in strips around a small number of approximate eigenvalues controlled by the regularity of the underlying poset. This gives a simple condition to identify poset architectures (e.g. the Grassmann) that exhibit strong (even exponential) decay of eigenvalues, versus architectures like hypergraphs whose eigenvalues decay linearly - a crucial distinction in applications to hardness of approximation and agreement testing such as the recent proof of the 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). We show these results lead to a tight characterization of edge-expansion on expanding posets in the 𝓁₂-regime (generalizing recent work of Bafna, Hopkins, Kaufman, and Lovett (SODA 2022)), and pay special attention to the case of the Grassmann where we show our results are tight for a natural set of sparsifications of the Grassmann graphs. We note for clarity that our results do not recover the characterization of expansion used in the proof of the 2-2 Games Conjecture which relies on 𝓁_∞ rather than 𝓁₂-structure.
Cite as

Jason Gaitonde, Max Hopkins, Tali Kaufman, Shachar Lovett, and Ruizhe Zhang. Eigenstripping, Spectral Decay, and Edge-Expansion on Posets. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 16:1-16:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{gaitonde_et_al:LIPIcs.APPROX/RANDOM.2022.16,
  author =	{Gaitonde, Jason and Hopkins, Max and Kaufman, Tali and Lovett, Shachar and Zhang, Ruizhe},
  title =	{{Eigenstripping, Spectral Decay, and Edge-Expansion on Posets}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022)},
  pages =	{16:1--16:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-249-5},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{245},
  editor =	{Chakrabarti, Amit and Swamy, Chaitanya},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2022.16},
  URN =		{urn:nbn:de:0030-drops-171381},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2022.16},
  annote =	{Keywords: High-dimensional expanders, posets, eposets}
}
Document
DOI: 10.4230/LIPIcs.CCC.2022.14
The Plane Test Is a Local Tester for Multiplicity Codes

Authors: Dan Karliner, Roie Salama, and Amnon Ta-Shma

Published in: LIPIcs, Volume 234, 37th Computational Complexity Conference (CCC 2022)

Abstract
Multiplicity codes are a generalization of RS and RM codes where for each evaluation point we output the evaluation of a low-degree polynomial and all of its directional derivatives up to order s. Multi-variate multiplicity codes are locally decodable with the natural local decoding algorithm that reads values on a random line and corrects to the closest uni-variate multiplicity code. However, it was not known whether multiplicity codes are locally testable, and this question has been posed since the introduction of these codes with no progress up to date. In fact, it has been also open whether multiplicity codes can be characterized by local constraints, i.e., if there exists a probabilistic algorithm that queries few symbols of a word c, accepts every c in the code with probability 1, and rejects every c not in the code with nonzero probability. We begin by giving a simple example showing the line test does not give local characterization when d > q. Surprisingly, we then show the plane test is a local characterization when s < q and d < qs-1 for prime q. In addition, we show the s-dimensional test is a local tester for multiplicity codes, when s < q. Combining the two results, we show our main result that the plane test is a local tester for multiplicity codes of degree d < qs-1, with constant rejection probability for constant q, s. Our technique is new. We represent the given input as a possibly very high-degree polynomial, and we show that for some choice of plane, the restriction of the polynomial to the plane is a high-degree bi-variate polynomial. The argument has to work modulo the appropriate kernels, and for that we use Grobner theory, the Combinatorial Nullstellensatz theorem and its generalization to multiplicities. Even given that, the argument is delicate and requires choosing a non-standard monomial order for the argument to work.
Cite as

Dan Karliner, Roie Salama, and Amnon Ta-Shma. The Plane Test Is a Local Tester for Multiplicity Codes. In 37th Computational Complexity Conference (CCC 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 234, pp. 14:1-14:33, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{karliner_et_al:LIPIcs.CCC.2022.14,
  author =	{Karliner, Dan and Salama, Roie and Ta-Shma, Amnon},
  title =	{{The Plane Test Is a Local Tester for Multiplicity Codes}},
  booktitle =	{37th Computational Complexity Conference (CCC 2022)},
  pages =	{14:1--14:33},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-241-9},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{234},
  editor =	{Lovett, Shachar},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.CCC.2022.14},
  URN =		{urn:nbn:de:0030-drops-165761},
  doi =		{10.4230/LIPIcs.CCC.2022.14},
  annote =	{Keywords: local testing, multiplicity codes, Reed Muller codes}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2021.56
Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion

Authors: Tali Kaufman and David Mass

Published in: LIPIcs, Volume 212, 32nd International Symposium on Algorithms and Computation (ISAAC 2021)

Abstract
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 high dimensional expansion notion is cosystolic expansion, which has found applications in the construction of efficiently decodable quantum codes and in proving lower bounds for CSPs. Cosystolic expansion is considered with systems of equations over a group where the variables and equations correspond to faces of the complex. Previous works that studied cosystolic expansion were tailored to the specific group 𝔽₂. In particular, Kaufman, Kazhdan and Lubotzky (FOCS 2014), and Evra and Kaufman (STOC 2016) in their breakthrough works, who solved a famous open question of Gromov, have studied a notion which we term "parity" expansion for small sets. They showed that small sets of k-faces have proportionally many (k+1)-faces that contain an odd number of k-faces from the set. Parity expansion for small sets could then be used to imply cosystolic expansion only over 𝔽₂. In this work we introduce a stronger unique-neighbor-like expansion for small sets. We show that small sets of k-faces have proportionally many (k+1)-faces that contain exactly one k-face from the set. This notion is fundamentally stronger than parity expansion and cannot be implied by previous works. We then show, utilizing the new unique-neighbor-like expansion notion introduced in this work, that cosystolic expansion can be made group-independent, i.e., unique-neighbor-like expansion for small sets implies cosystolic expansion over any group.
Cite as

Tali Kaufman and David Mass. Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion. In 32nd International Symposium on Algorithms and Computation (ISAAC 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 212, pp. 56:1-56:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.ISAAC.2021.56,
  author =	{Kaufman, Tali and Mass, David},
  title =	{{Unique-Neighbor-Like Expansion and Group-Independent Cosystolic Expansion}},
  booktitle =	{32nd International Symposium on Algorithms and Computation (ISAAC 2021)},
  pages =	{56:1--56:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-214-3},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{212},
  editor =	{Ahn, Hee-Kap and Sadakane, Kunihiko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2021.56},
  URN =		{urn:nbn:de:0030-drops-154898},
  doi =		{10.4230/LIPIcs.ISAAC.2021.56},
  annote =	{Keywords: High dimensional expanders, Unique-neighbor-like expansion, Cosystolic expansion}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.84
Coboundary and Cosystolic Expansion from Strong Symmetry

Authors: Tali Kaufman and Izhar Oppenheim

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
Coboundary and cosystolic expansion are notions of expansion that generalize the Cheeger constant or edge expansion of a graph to higher dimensions. The classical Cheeger inequality implies that for graphs edge expansion is equivalent to spectral expansion. In higher dimensions this is not the case: a simplicial complex can be spectrally expanding but not have high dimensional edge-expansion. The phenomenon of high dimensional edge expansion in higher dimensions is much more involved than spectral expansion, and is far from being understood. In particular, prior to this work, the only known bounded degree cosystolic expanders were derived from the theory of buildings that is far from being elementary. In this work we study high dimensional complexes which are strongly symmetric. Namely, there is a group that acts transitively on top dimensional cells of the simplicial complex [e.g., for graphs it corresponds to a group that acts transitively on the edges]. Using the strong symmetry, we develop a new machinery to prove coboundary and cosystolic expansion. It was an open question whether the recent elementary construction of bounded degree spectral high dimensional expanders based on coset complexes give rise to bounded degree cosystolic expanders. In this work we answer this question affirmatively. We show that these complexes give rise to bounded degree cosystolic expanders in dimension two, and that their links are (two-dimensional) coboundary expanders. We do so by exploiting the strong symmetry properties of the links of these complexes using a new machinery developed in this work. Previous works have shown a way to bound the co-boundary expansion using strong symmetry in the special situation of "building like" complexes. Our new machinery shows how to get coboundary expansion for general strongly symmetric coset complexes, which are not necessarily "building like", via studying the (Dehn function of the) presentation of the symmetry group of these complexes.
Cite as

Tali Kaufman and Izhar Oppenheim. Coboundary and Cosystolic Expansion from Strong Symmetry. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 84:1-84:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.ICALP.2021.84,
  author =	{Kaufman, Tali and Oppenheim, Izhar},
  title =	{{Coboundary and Cosystolic Expansion from Strong Symmetry}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{84:1--84:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.84},
  URN =		{urn:nbn:de:0030-drops-141539},
  doi =		{10.4230/LIPIcs.ICALP.2021.84},
  annote =	{Keywords: High dimensional expanders, Cosystolic expansion, Coboundary expansion}
}
Document
DOI: 10.4230/LIPIcs.FUN.2021.7
1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete

Authors: Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff

Published in: LIPIcs, Volume 157, 10th International Conference on Fun with Algorithms (FUN 2021) (2020)

Abstract
Consider n²-1 unit-square blocks in an n × n square board, where each block is labeled as movable horizontally (only), movable vertically (only), or immovable - a variation of Rush Hour with only 1 × 1 cars and fixed blocks. We prove that it is PSPACE-complete to decide whether a given block can reach the left edge of the board, by reduction from Nondeterministic Constraint Logic via 2-color oriented Subway Shuffle. By contrast, polynomial-time algorithms are known for deciding whether a given block can be moved by one space, or when each block either is immovable or can move both horizontally and vertically. Our result answers a 15-year-old open problem by Tromp and Cilibrasi, and strengthens previous PSPACE-completeness results for Rush Hour with vertical 1 × 2 and horizontal 2 × 1 movable blocks and 4-color Subway Shuffle.
Cite as

Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, and Avi Zeff. 1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete. In 10th International Conference on Fun with Algorithms (FUN 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 157, pp. 7:1-7:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{brunner_et_al:LIPIcs.FUN.2021.7,
  author =	{Brunner, Josh and Chung, Lily and Demaine, Erik D. and Hendrickson, Dylan and Hesterberg, Adam and Suhl, Adam and Zeff, Avi},
  title =	{{1 X 1 Rush Hour with Fixed Blocks Is PSPACE-Complete}},
  booktitle =	{10th International Conference on Fun with Algorithms (FUN 2021)},
  pages =	{7:1--7:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-145-0},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{157},
  editor =	{Farach-Colton, Martin and Prencipe, Giuseppe and Uehara, Ryuhei},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FUN.2021.7},
  URN =		{urn:nbn:de:0030-drops-127681},
  doi =		{10.4230/LIPIcs.FUN.2021.7},
  annote =	{Keywords: puzzles, sliding blocks, PSPACE-hardness}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX/RANDOM.2020.25
Chernoff Bound for High-Dimensional Expanders

Authors: Tali Kaufman and Ella Sharakanski

Published in: LIPIcs, Volume 176, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)

Abstract
We generalize the expander Chernoff bound to high-dimensional expanders. The expander Chernoff bound is an essential property of expanders, first proved by Gillman [Gillman, 1993]. Given a graph G and a function f on the vertices, it states that the probability of f’s mean sampled via a random walk on G to deviate from its actual mean, has a bound that depends on the spectral gap of the walk and decreases exponentially as the walk’s length increases. We are interested in obtaining an analog Chernoff bound for high order walks on high-dimensional expanders. A naive generalization of the expander Chernoff bound from expander graphs to high-dimensional expanders gives a very poor bound due to obstructions that occur in high-dimensional expanders and are not present in (one-dimensional) expander graphs. Because of these obstructions, the spectral gap of high-order random walks is inherently small. A natural question that arises is how to get a meaningful Chernoff bound for high-dimensional expanders. In this paper, we manage to get a strong Chernoff bound for high-dimensional expanders by looking beyond the spectral gap. First, we prove an expander Chernoff bound that depends on a notion that we call the "shrinkage of a function" instead of the spectral gap. In one-dimensional expanders, the shrinkage of any function with zero-mean is bounded by λ(M). Therefore, the spectral gap is just the one-dimensional manifestation of the shrinkage. Next, we show that in good high-dimensional expanders, the shrinkage of functions that "do not come from below" is good. A function does not come from below if from any local point of view (called "link") its mean is zero. Finally, we prove a high-dimensional Chernoff bound that captures the expansion of the complex. When the function on the faces has a small variance and does not "come from below", our bound is better than the naive high-dimensional expander Chernoff bound.
Cite as

Tali Kaufman and Ella Sharakanski. Chernoff Bound for High-Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 176, pp. 25:1-25:22, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.APPROX/RANDOM.2020.25,
  author =	{Kaufman, Tali and Sharakanski, Ella},
  title =	{{Chernoff Bound for High-Dimensional Expanders}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2020)},
  pages =	{25:1--25:22},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-164-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{176},
  editor =	{Byrka, Jaros{\l}aw and Meka, Raghu},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2020.25},
  URN =		{urn:nbn:de:0030-drops-126287},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2020.25},
  annote =	{Keywords: High Dimensional Expanders, Random Walks, Tail Bounds}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2020.74
Local-To-Global Agreement Expansion via the Variance Method

Authors: Tali Kaufman and David Mass

Published in: LIPIcs, Volume 151, 11th Innovations in Theoretical Computer Science Conference (ITCS 2020)

Abstract
Agreement expansion is concerned with set systems for which local assignments to the sets with almost perfect pairwise consistency (i.e., most overlapping pairs of sets agree on their intersections) implies the existence of a global assignment to the ground set (from which the sets are defined) that agrees with most of the local assignments. It is currently known that if a set system forms a two-sided or a partite high dimensional expander then agreement expansion is implied. However, it was not known whether agreement expansion can be implied for one-sided high dimensional expanders. In this work we show that agreement expansion can be deduced for one-sided high dimensional expanders assuming that all the vertices' links (i.e., the neighborhoods of the vertices) are agreement expanders. Thus, for one-sided high dimensional expander, an agreement expansion of the large complicated complex can be deduced from agreement expansion of its small simple links. Using our result, we settle the open question whether the well studied Ramanujan complexes are agreement expanders. These complexes are neither partite nor two-sided high dimensional expanders. However, they are one-sided high dimensional expanders for which their links are partite and hence are agreement expanders. Thus, our result implies that Ramanujan complexes are agreement expanders, answering affirmatively the aforementioned open question. The local-to-global agreement expansion that we prove is based on the variance method that we develop. We show that for a high dimensional expander, if we define a function on its top faces and consider its local averages over the links then the variance of these local averages is much smaller than the global variance of the original function. This decreasing in the variance enables us to construct one global agreement function that ties together all local agreement functions.
Cite as

Tali Kaufman and David Mass. Local-To-Global Agreement Expansion via the Variance Method. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 74:1-74:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{kaufman_et_al:LIPIcs.ITCS.2020.74,
  author =	{Kaufman, Tali and Mass, David},
  title =	{{Local-To-Global Agreement Expansion via the Variance Method}},
  booktitle =	{11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
  pages =	{74:1--74:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-134-4},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{151},
  editor =	{Vidick, Thomas},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2020.74},
  URN =		{urn:nbn:de:0030-drops-117597},
  doi =		{10.4230/LIPIcs.ITCS.2020.74},
  annote =	{Keywords: Agreement testing, High dimensional expanders, Local-to-global, Variance method}
}
Document
RANDOM
DOI: 10.4230/LIPIcs.APPROX-RANDOM.2019.50
Testing Odd Direct Sums Using High Dimensional Expanders

Authors: Roy Gotlib and Tali Kaufman

Published in: LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)

Abstract
In this work, using methods from high dimensional expansion, we show that the property of k-direct-sum is testable for odd values of k . Previous work of [Kaufman and Lubotzky, 2014] could inherently deal only with the case that k is even, using a reduction to linearity testing. Interestingly, our work is the first to combine the topological notion of high dimensional expansion (called co-systolic expansion) with the combinatorial/spectral notion of high dimensional expansion (called colorful expansion) to obtain the result. The classical k-direct-sum problem applies to the complete complex; Namely it considers a function defined over all k-subsets of some n sized universe. Our result here applies to any collection of k-subsets of an n-universe, assuming this collection of subsets forms a high dimensional expander.
Cite as

Roy Gotlib and Tali Kaufman. Testing Odd Direct Sums Using High Dimensional Expanders. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 145, pp. 50:1-50:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{gotlib_et_al:LIPIcs.APPROX-RANDOM.2019.50,
  author =	{Gotlib, Roy and Kaufman, Tali},
  title =	{{Testing Odd Direct Sums Using High Dimensional Expanders}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019)},
  pages =	{50:1--50:20},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-125-2},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{145},
  editor =	{Achlioptas, Dimitris and V\'{e}gh, L\'{a}szl\'{o} A.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.50},
  URN =		{urn:nbn:de:0030-drops-112651},
  doi =		{10.4230/LIPIcs.APPROX-RANDOM.2019.50},
  annote =	{Keywords: High Dimensional Expanders, Property Testing, Direct Sum}
}
  • Refine by Author
  • 17 Kaufman, Tali
  • 4 Mass, David
  • 3 Gotlib, Roy
  • 3 Oppenheim, Izhar
  • 1 Abdolazimi, Dorna
  • Show More...

  • Refine by Classification
  • 5 Theory of computation → Expander graphs and randomness extractors
  • 4 Theory of computation → Computational complexity and cryptography
  • 4 Theory of computation → Random walks and Markov chains
  • 3 Theory of computation → Error-correcting codes
  • 3 Theory of computation → Randomness, geometry and discrete structures
  • Show More...

  • Refine by Keyword
  • 7 High dimensional expanders
  • 4 High Dimensional Expanders
  • 2 Agreement testing
  • 2 Cosystolic expansion
  • 2 High dimensional Expanders
  • Show More...

  • Refine by Type
  • 20 document

  • Refine by Publication Year
  • 4 2022
  • 4 2023
  • 3 2020
  • 2 2019
  • 2 2021
  • Show More...

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact