Arrow Research search

Author name cluster

Irit Dinur

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

30 papers
2 author rows

Possible papers

30

FOCS Conference 2024 Conference Paper

Expansion of High-Dimensional Cubical Complexes: with Application to Quantum Locally Testable Codes

  • Irit Dinur
  • Ting-Chun Lin
  • Thomas Vidick

We introduce a high-dimensional cubical complex, for any dimension $t \in \mathbb{N}$, and apply it to the design of quantum locally testable codes. Our complex is a natural generalization of the constructions by Panteleev and Kalachev and by Dinur et. al of a square complex (case $t=2$ ), which have been applied to the design of classical locally testable codes (LTC) and quantum low-density parity check codes (qLDPC) respectively. We turn the geometric (cubical) complex into a chain complex by relying on constant-sized local codes $h_{1}, \ldots, h_{t}$ as gadgets. A recent result of Panteleev and Kalachev on existence of tuples of codes that are product expanding enables us to prove lower bounds on the cycle and co-cycle expansion of our chain complex. For $t=4$ our construction gives a new family of “almost-good” quantum LTCs - with constant relative rate, inverse-polylogarithmic relative distance and soundness, and constant-size parity checks. Both the distance of the quantum code and its local testability are proven directly from the cycle and co-cycle expansion of our chain complex.

Details

FOCS Conference 2024 Conference Paper

Low Acceptance Agreement Tests via Bounded-Degree Symplectic HDXs

  • Yotam Dikstein
  • Irit Dinur
  • Alexander Lubotzky

We solve the derandomized direct product testing question in the low acceptance regime, by constructing new high dimensional expanders that have no small connected covers. We show that our complexes have swap cocycle expansion, which allows us to deduce the agreement theorem by relying on previous work. Derandomized direct product testing, also known as agreement testing, is the following problem. Let $X$ be a family of k-element subsets of $[N]$ and let $\{f_{s}: s\rightarrow\Sigma\vert s\in X\}$ be an ensemble of local functions, each defined over a subset $s\subset\lceil N$. Suppose that we run the following so-called agreement test: choose a random pair of sets $s_{1}, s_{2}\in X$ that intersect on $\sqrt{k}$ elements, and accept if $f_{s_{1}}, f_{s_{2}}$ agree on the elements in $s_{1}\cap s_{2}$. We denote the success probability of this test by Agree $\{f_{s}\})$ Given that Agree $(\{f_{s}\})=\varepsilon > 0$ is there a global function $G: [N]\rightarrow\Sigma$ such that $f_{s}=G\vert _{s}$ for a non-negligible fraction of $s\in X\? $ We construct a family $X$ of k-subsets of $[N]$ such that $\vert X\vert =O(N)$, and such that it satisfies the low acceptance agreement theorem. Namely, $\text{Agree}\left(\left\{f_s\right\}\right)>\varepsilon \Longrightarrow \exists G: [N] \rightarrow \Sigma, \quad \underset{s}{\mathbb{P}}\left[\left. f_s \stackrel{0. 99}{\approx} G\right\vert_s\right] \geqslant \text{poly}(\varepsilon)$. A key idea is to replace the well-studied LSV complexes by symplectic high dimensional expanders (HDXs). The family $X$ is just the k-faces of the new symplectic HDXs. The latter serve our needs better since their fundamental group satisfies the congruence subgroup property, which implies that they lack small covers. We also give a polynomial-time algorithm to construct this family of sym-plectic HDXs.

Details

FOCS Conference 2022 Conference Paper

A Characterization of Multiclass Learnability

  • Nataly Brukhim
  • Daniel Carmon
  • Irit Dinur
  • Shay Moran
  • Amir Yehudayoff

A seminal result in learning theory characterizes the PAC learnability of binary classes through the Vapnik-Chervonenkis dimension. Extending this characterization to the general multiclass setting has been open since the pioneering works on multiclass PAC learning in the late 1980s. This work resolves this problem: we characterize multiclass PAC learnability through the DS dimension, a combinatorial dimension defined by Daniely and Shalev-Shwartz, (2014). The classical characterization of the binary case boils down to empirical risk minimization. In contrast, our characterization of the multiclass case involves a variety of algorithmic ideas; these include a natural setting we call list PAC learning. In the list learning setting, instead of predicting a single outcome for a given unseen input, the goal is to provide a short menu of predictions. Our second main result concerns the Natarajan dimension, which has been a central candidate for characterizing multiclass learnability. This dimension was introduced by Natarajan (1988) as a barrier for PAC learning. He furthered showed that it is the only barrier, provided that the number of labels is bounded. Whether the Natarajan dimension characterizes PAC learnability in general has been posed as an open question in several papers since. This work provides a negative answer: we construct a non-learnable class with Natarajan dimension 1. For the construction, we identify a fundamental connection between concept classes and topology (i. e. , colorful simplicial complexes). We crucially rely on a deep and involved construction of hyperbolic pseudo-manifolds by Januszkiewicz and Światkowski. It is interesting that hyperbolicity is directly related to learning problems that are difficult to solve although no obvious barriers exist. This is another demonstration of the fruitful links machine learning has with different areas in mathematics.

Details

FOCS Conference 2019 Conference Paper

Agreement Testing Theorems on Layered Set Systems

  • Yotam Dikstein
  • Irit Dinur

We introduce a framework of layered subsets, and give a sufficient condition for when a set system supports an agreement test. Agreement testing is a certain type of property testing that generalizes PCP tests such as the plane vs. plane test. Previous work has shown that high dimensional expansion is useful for agreement tests. We extend these results to more general families of subsets, beyond simplicial complexes. These include - Agreement tests for set systems whose sets are faces of high dimensional expanders. Our new tests apply to all dimensions of complexes both in case of two-sided expansion and in the case of one sided partite expansion. This improves and extends an earlier work of Dinur and Kaufman (FOCS 2017) and applies to matroids, and potentially many additional complexes. - Agreement tests for set systems whose sets are neighborhoods of vertices in a high dimensional expander. This family resembles the expander neighborhood family used in the gap-amplification proof of the PCP theorem. This set system is quite natural yet does not sit in a simplicial complex, and demonstrates some versatility in our proof technique. - Agreement tests on families of subspaces (also known as the Grassmann poset). This extends the classical low degree agreement tests beyond the setting of low degree polynomials. Our analysis relies on a new random walk on simplicial complexes which we call the “complement random walk” and which may be of independent interest. This random walk generalizes the non-lazy random walk on a graph to higher dimensions, and has significantly better expansion than previously-studied random walks on simplicial complexes.

Details

SODA Conference 2019 Conference Paper

Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract]

  • Irit Dinur
  • Yuval Filmus
  • Prahladh Harsha

We propose a new paradigm for studying the structure of Boolean functions on the biased Boolean hypercube, i. e. when the measure is µ p and p is potentially very small, e. g. as small as O (1/ n ). Our paradigm is based on the following simple fact: the p -biased hypercube is expressible as a convex combination of many small-dimensional copies of the uniform hypercube. To uncover structure for µ p, we invoke known structure theorems for µ 1/2, obtaining a structured approximation for each copy separately. We then sew these approximations together using a novel “agreement theorem”. This strategy allows us to lift structure theorems from µ 1/2 to µ p. We provide two applications of this paradigm: • Our main application is a structure theorem for functions that are nearly low degree in the Fourier sense. The structure we uncover in the biased hypercube is not at all the same as for the uniform hypercube, despite using the structure theorem for the uniform hypercube as a black box. Rather, new phenomena emerge: whereas nearly low degree functions on the uniform hypercube are close to juntas, when p becomes small, non-juntas arise as well. For example, the function max( y 1, · · ·, y ε / p ) (where y i ∊ {0, 1}) is nearly degree 1 despite not being close to any junta. • A second (technically simpler) application is a test for being low degree in the GF (2) sense, in the setting of the biased hypercube. In both cases, we use as a black box the corresponding result for p = 1/2. In the first case, it is the junta theorem of Kindler and Safra, and in the second case, the low degree testing theorem of Alon et al. [ IEEE Trans. Inform. Theory, 2005] and Bhattacharyya et al. [ Proc. 51st FOCS, 2010]. A key component of our proof is a new local-to-global agreement theorem for higher dimensions, which extends the work of Dinur and Steurer [ Proc. 29th CCC, 2014]. Whereas their result sews together vectors, our agreement theorem sews together labeled graphs and hypergraphs. The proof of our agreement theorem uses a novel pruning lemma for hypergraphs, which may be of independent interest. The pruning lemma trims a given hypergraph so that the number of hyperedges in a random induced subhypergraph has roughly a Poisson distribution, while maintaining the expected number of hyperedges.

Details

SODA Conference 2019 Conference Paper

List Decoding with Double Samplers

  • Irit Dinur
  • Prahladh Harsha
  • Tali Kaufman
  • Inbal Livni Navon
  • Amnon Ta-Shma

We develop the notion of double samplers, first introduced by Dinur and Kaufman [DK17], which are samplers with additional combinatorial properties, and whose existence we prove using high dimensional expanders. We show how double samplers give a generic way of amplifying distance in a way that enables efficient list-decoding. There are many error correcting code constructions that achieve large distance by starting with a base code C with moderate distance, and then amplifying the distance using a sampler, e. g. , the ABNNR code construction [ABN + 92] is such. We show that if the sampler is part of a larger double sampler then the construction has an efficient list-decoding algorithm and the list decoding algorithm is oblivious to the base code C (i. e. , it runs the unique decoder for C in a black box way). Our list-decoding algorithm works as follows: it uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context.

Details

STOC Conference 2018 Conference Paper

On non-optimally expanding sets in Grassmann graphs

  • Irit Dinur
  • Subhash Khot
  • Guy Kindler
  • Dor Minzer
  • Muli Safra

We study the structure of non-expanding sets in the Grassmann graph. We put forth a hypothesis stating that every small set whose expansion is smaller than 1−δ must be correlated with one of a specified list of sets which are isomorphic to smaller Grassmann graphs. We develop a framework of Fourier analysis for analyzing functions over the Grassmann graph, and prove that our hypothesis holds for all sets whose expansion is below 7/8. In the companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018], the authors show that a linearity agreement hypothesis implies an NP-hardness gap of 1/2− vs for unique games and other inapproximability results. In [Barak, Kothari and Steurer, ECCC TR18-077], the authors show that the hypothesis in this work implies the linearity agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018]. Combined with our main theorem here this proves a version of the linearity agreement hypothesis with certain specific parameters. Short of proving the entire hypothesis, this nevertheless suffices for getting new unconditional NP hardness gaps for label cover with 2-to-1 and unique constraints. Our Expansion Hypothesis has been subsequently proved in its full form [Khot, Minzer and Safra, ECCC TR18-006] thereby proving the agreement hypothesis of [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] and completing the proof of the 2-to-1 Games Conjecture (albeit with imperfect completeness).

Details

STOC Conference 2018 Conference Paper

Towards a proof of the 2-to-1 games conjecture?

  • Irit Dinur
  • Subhash Khot
  • Guy Kindler
  • Dor Minzer
  • Muli Safra

We present a polynomial time reduction from gap-3LIN to label cover with 2-to-1 constraints. In the “yes” case the fraction of satisfied constraints is at least 1 −ε, and in the “no” case we show that this fraction is at most ε, assuming a certain (new) combinatorial hypothesis on the Grassmann graph. In other words, we describe a combinatorial hypothesis that implies the 2-to-1 conjecture with imperfect completeness. The companion submitted paper [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] makes some progress towards proving this hypothesis. Our work builds on earlier work by a subset of the authors [Khot, Minzer and Safra, STOC 2017] where a slightly different hypothesis was used to obtain hardness of approximating vertex cover to within factor of √2−ε. The most important implication of this work is (assuming the hypothesis) an NP-hardness gap of 1/2−ε vs. ε for unique games . In addition, we derive optimal NP-hardness for approximating the max-cut-gain problem, NP-hardness of coloring an almost 4-colorable graph with any constant number of colors, and the same √2−ε NP-hardness for approximate vertex cover that was already obtained based on a slightly different hypothesis. Recent progress towards proving our hypothesis [Barak, Kothari and Steurer, ECCC TR18-077], [Dinur, Khot, Kindler, Minzer and Safra, STOC 2018] directly implies some new unconditional NP-hardness results. These include new points of NP-hardness for unique games and for 2-to-1 and 2-to-2 games. More recently, the full version of our hypothesis was proven [Khot, Minzer and Safra, ECCC TR18-006].

Details

FOCS Conference 2017 Conference Paper

High Dimensional Expanders Imply Agreement Expanders

  • Irit Dinur
  • Tali Kaufman

We show that high dimensional expanders imply derandomized direct product tests, with a number of subsets that is linear in the size of the universe. Direct product tests belong to a family of tests called agreement tests that are important components in PCP constructions and include, for example, low degree tests such as line vs. line and plane vs. plane. For a generic hypergraph, we introduce the notion of agreement expansion, which captures the usefulness of the hypergraph for an agreement test. We show that explicit bounded degree agreement expanders exist, based on Ramanujan complexes.

Details

STOC Conference 2014 Conference Paper

Analytical approach to parallel repetition

  • Irit Dinur
  • David Steurer

We propose an analytical framework for studying parallel repetition, a basic product operation for one-round twoplayer games. In this framework, we consider a relaxation of the value of projection games. We show that this relaxation is multiplicative with respect to parallel repetition and that it provides a good approximation to the game value. Based on this relaxation, we prove the following improved parallel repetition bound: For every projection game G with value at most ρ , the k -fold parallel repetition G ⊗ k has value at most [EQUATION] This statement implies a parallel repetition bound for projection games with low value ρ . Previously, it was not known whether parallel repetition decreases the value of such games. This result allows us to show that approximating set cover to within factor (1 --- ε ) ln n is NP-hard for every ε > 0, strengthening Feige's quasi-NP-hardness and also building on previous work by Moshkovitz and Raz. In this framework, we also show improved bounds for few parallel repetitions of projection games, showing that Raz's counterexample to strong parallel repetition is tight even for a small number of repetitions. Finally, we also give a short proof for the NP-hardness of label cover(1, δ ) for all δ > 0, starting from the basic PCP theorem.

Details

FOCS Conference 2013 Conference Paper

PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring

  • Irit Dinur
  • Venkatesan Guruswami

We develop new techniques to incorporate the recently proposed “short code” (a low-degree version of the long code) into the construction and analysis of PCPs in the classical “Label Cover + Fourier Analysis” framework. As a result, we obtain more size-efficient PCPs that yield improved hardness results for approximating CSPs and certain coloringtype problems. In particular, we show a hardness for a variant of hypergraph coloring (with hyperedges of size 6), with a gap between 2 and exp(2 Ω (√log log N)) number of colors where N is the number of vertices. This is the first hardness result to go beyond the O(log N) barrier for a coloring-type problem. Our hardness bound is a doubly exponential improvement over the previously known O(log log N)-coloring hardness for 2-colorable hypergraphs, and an exponential improvement over the (logN) Ω(1) -coloring hardness for O(1)-colorable hypergraphs. Stated in terms of “covering complexity, ” we show that for 6-ary Boolean CSPs, it is hard to decide if a given instance is perfectly satisfiable or if it requires more than 2Ω(√log log N) assignments for covering all of the constraints. While our methods do not yield a result for conventional hypergraph coloring due to some technical reasons, we also prove hardness of (log N) Ω(1) -coloring 2-colorable 6-uniform hypergraphs (this result relies just on the long code). A key algebraic result driving our analysis concerns a very low-soundness error testing method for Reed-Muller codes. We prove that if a function β: F 2 m → F 2 is 2 Ω(d) far in absolute distance from polynomials of degree m-d, then the probability that deg(βg) ≤ m-3d/4 for a random degree d/4 polynomial g is doubly exponentially small in d.

Details

FOCS Conference 2009 Conference Paper

Composition of Low-Error 2-Query PCPs Using Decodable PCPs

  • Irit Dinur
  • Prahladh Harsha

The main result of this paper is a generic composition theorem for low error two-query probabilistically checkable proofs (PCPs). Prior to this work, composition of PCPs was well-understood only in the constant error regime. Existing composition methods in the low error regime were non-modular (i. e. , very much tailored to the specific PCPs that were being composed), resulting in complicated constructions of PCPs. Furthermore, until recently, composition in the low error regime suffered from incurring an extra 'consistency' query, resulting in PCPs that are not 'two-query' and hence, much less useful for hardness-of-approximation reductions. In a recent breakthrough, Moshkovitz and Raz [In Proc. 49th IEEE Symp. on Foundations of Comp. Science (FOCS), 2008] constructed almost linear-sized low-error 2-query PCPs for every language in NP. Indeed, the main technical component of their construction is a novel composition of certain specific PCPs. We give a modular and simpler proof of their result by repeatedly applying the new composition theorem to known PCP components. To facilitate the new modular composition, we introduce a new variant of PCP, which we call a "decodable PCP (dPCP)". A dPCP is an encoding of an NP witness that is both locally checkable and locally decodable. The dPCP verifier in addition to verifying the validity of the given proof like a standard PCP verifier, also locally decodes the original NP witness. Our composition is generic in the sense that it works regardless of the way the component PCPs are constructed.

Details

FOCS Conference 2008 Conference Paper

Locally Testing Direct Product in the Low Error Range

  • Irit Dinur
  • Elazar Goldenberg

Given a function f: X rarr Sigma, its lscr-wise direct product is the function F = f lscr: X lscr rarr Sigma lscr defined by: F(x 1, .. ., x lscr ) = (f(x 1 ), .. ., f(x lscr )). We are interested in the local testability of the direct product encoding (mapping f rarr f lscr ). Namely, given an arbitrary function F: X lscr rarr Sigma lscr, we wish to determine how close it is to f lscr for some f: X rarr Sigma, by making two random queries into F. In this work we analyze the case of low acceptance probability of the test. We show that even if the test passes with small probability, epsiv>0, already F must have a non-trivial structure and in particular must agree with some f lscr on nearly epsiv of the domain. Moreover, we give a structural characterization of all functions F on which the test passes with probability epsiv. Our results can be viewed as a combinatorial analog of the low error dasialow degree testpsila, that is used in PCP constructions.

Details

STOC Conference 2006 Conference Paper

The PCP theorem by gap amplification

  • Irit Dinur

We present a new proof of the PCP theorem that is based on a combinatorial amplification lemma. The unsat value of a set of constraints C = (c 1 ,...,c n ), denoted UNSAT(C), is the smallest fraction of unsatisfied constraints, ranging over all possible assignments for the underlying variables.We describe a new combinatorial amplification transformation that doubles the unsat-value of a constraint-system, with only a linear blowup in the size of the system. The amplification step causes an increase in alphabet-size that is corrected by a PCP composition step. Iterative application of these two steps yields a proof for the PCP theorem.The amplification lemma relies on a new notion of "graph powering" that can be applied to systems of constraints. This powering amplifies the unsat-value of a constraint system provided that the underlying graph structure is an expander.We also apply the amplification lemma to construct PCPs and locally-testable codes whose length is linear up to a polylog factor, and whose correctness can be probabilistically verified by making a constant number of queries. Namely, we prove SAT ∈ PCP 1/2,1 [log 2 (n • poly log n),O(1)].

Details

FOCS Conference 2004 Conference Paper

Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem

  • Irit Dinur
  • Omer Reingold

In this work, we look back into the proof of the PCP theorem, with the goal of finding new proofs that are "more combinatorial" and arguably simpler. For that, we introduce the notion of an assignment tester, which is a strengthening of the standard PCP verifier, in the following sense. Given a statement and an alleged proof for it, while the PCP verifier checks correctness of the statement, the assignment-tester checks correctness of the statement and the proof. This notion enables composition that is truly modular, i. e. , one can compose two assignment-testers without any assumptions on how they are constructed. A related notion was independently introduced in (Ben-Sasson et. al. STOC 04). We provide a toolkit of (non-trivial) generic transformations on assignment testers. These transformations may be interesting in their own right, and allow us to present the following two main results: 1. The first is a new proof of the PCP theorem. This proof relies on a rather weak assignment tester given as a "black box". From this, we construct combinatorially the full PCP. An important component of this proof is a new combinatorial aggregation technique (i. e. , a new transformation that allows the verifier to read fewer, though possibly longer, "pieces" of the proof). An implementation of the black-box tester can be obtained from the algebraic proof techniques that already appear in L. Babai et al. , 1991 and U. Feige et al. , 1991. Obtaining a combinatorial implementation of this tester would give a purely combinatorial proof for the PCP theorem, which we view as an interesting open problem. 2. Our second construction is a "standalone" combinatorial construction showing NP /spl sube/ PCP (S. Arora et al. , 1998). This implies, for example, that approximating max-SAT is quasi-NP-hard. This construction relies on a transformation that makes an assignment tester "oblivious": so that the proof locations read are independent of the statement that is being proven. This eliminates, in a rather surprising manner, the need for aggregation in a crucial point in the proof.

Details

FOCS Conference 2002 Conference Paper

The Hardness of 3 - Uniform Hypergraph Coloring

  • Irit Dinur
  • Oded Regev 0001
  • Clifford D. Smyth

We prove that coloring a 3-uniform 2-colorable hypergraph with any constant number of colors is NP-hard. The best known algorithm (Krivelevich, Nathaniel, and Sudakov, 2001)colors such a graph using O(n/sup 1/5/) colors. Our result immediately implies that for any constants k > 2 and c/sub 2/ > c/sub 1/ > 1, coloring a k-uniform c/sub 1/-colorable hypergraph with c/sub 2/ colors is NP-hard; leaving completely open only the k = 2 graph case. We are the first to obtain a hardness result for approximately-coloring a 3-uniform hypergraph that is colorable with a constant number of colors. For k /spl ges/ 4 such a result has been shown by Guruswami et al. (2000), who also discussed the inherent difference between the k = 3 case and k /spl ges/ 4. Our proof presents a new connection between the Long-Code and the Kneser graph, and relies on the high chromatic numbers of the Kneser graph (Kneser, 1955; Lovasz, 1978) and the Schrijver graph (Schrijver, 1978). We prove a certain maximization variant of the Kneser conjecture, namely that any coloring of the Kneser graph by fewer colors than its chromatic number, has 'many' non-monochromatic edges.

Details