Arrow Research search

Author name cluster

Dor Minzer

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.

34 papers
1 author row

Possible papers

34

STOC Conference 2025 Conference Paper

Constant Degree Networks for Almost-Everywhere Reliable Transmission

  • Mitali Bafna
  • Dor Minzer

In the almost-everywhere reliable message transmission problem, introduced by [Dwork, Pippenger, Peleg, Upfal’86], the goal is to design a sparse communication network G that supports efficient, fault-tolerant protocols for interactions between all node pairs. By fault-tolerant, we mean that that even if an adversary corrupts a small fraction of vertices in G , then all but a small fraction of vertices can still communicate perfectly via the constructed protocols. Being successful to do so allows one to simulate, on a sparse graph, any fault-tolerant distributed computing task and secure multi-party computation protocols built for a complete network, with only minimal overhead in efficiency. Previous works on this problem achieved either constant-degree networks tolerating o (1) faults, constant-degree networks tolerating a constant fraction of faults via inefficient protocols (exponential work complexity), or poly-logarithmic degree networks tolerating a constant fraction of faults. We show a construction of constant-degree networks with efficient protocols (i.e., with polylogarithmic work complexity) that can tolerate a constant fraction of adversarial faults, thus solving the main open problem of Dwork et al. Our main contribution is a composition technique for communication networks, based on graph products. Our technique combines two networks tolerant to adversarial edge-faults to construct a network with a smaller degree while maintaining efficiency and fault-tolerance. We apply this composition result multiple times, using the polylogarithmic-degree edge-fault tolerant networks constructed in a recent work of [Bafna, Minzer, Vyas’24] (that are based on high-dimensional expanders) with itself, and then with the constant-degree networks (albeit with inefficient protocols) of [Upfal’92].

Details

FOCS Conference 2025 Conference Paper

Improved Round-by-round Soundness IOPs via Reed-Muller Codes

  • Dor Minzer
  • Kai Zhe Zheng

We give an IOPP (interactive oracle proof of proximity) for trivariate Reed-Muller codes that achieves the best known query complexity in some range of security parameters. Specifically, for degree d and security parameter $\lambda \leq \frac{\log ^{2} d}{\log \log d}$, our IOPP has $2^{-\lambda}$ round-byround soundness, $O(\lambda)$ queries, $O(\log \log d)$ rounds and $O(d)$ length. This improves upon the FRI [Ben-Sasson, Bentov, Horesh, Riabzev, ICALP 2018] and the STIR [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] IOPPs for Reed-Solomon codes, that have larger query and round complexity standing at $O(\lambda \log d)$ and $O(\log d+\lambda \log \log d)$ respectively. We use our IOPP to give an IOP for the NPcomplete language R1CS with the same parameters. Our construction is based on the line versus point test in the low-soundness regime. Compared to the axis parallel test (which is used in all prior works), the general affine lines test has improved soundness, which is the main source of our improved soundness. Using this test involves several complications, most significantly that projection to affine lines does not preserve individual degrees, and we show how to overcome these difficulties. En route, we extend some existing machinery to more general settings. Specifically, we give proximity generators for Reed-Muller codes, show a more systematic way of handling “side conditions” in IOP constructions, and generalize the compiling procedure of [Arnon, Chiesa, Fenzi, Yogev, Crypto 2024] to general codes.

Details

FOCS Conference 2025 Conference Paper

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut

  • Yumou Fei
  • Dor Minzer
  • Shuo Wang

In the Max-Cut problem in the streaming model, an algorithm is given the edges of an unknown graph $G=(V, E)$ in some fixed order, and its goal is to approximate the size of the largest cut in G. Improving upon an earlier result of Kapralov, Khanna and Sudan, it was shown by Kapralov and Krachun that for all $\varepsilon\gt 0$, no $o(n)$ memory streaming algorithm can achieve a $(1 / 2+\varepsilon)$-approximation for Max-Cut. Their result holds for single-pass streams, i. e. the setting in which the algorithm only views the stream once, and it was open whether multi-pass access may help. The state-of-the-art result along these lines, due to Assadi and N, rules out arbitrarily good approximation algorithms with constantly many passes and $n^{1-\delta}$ space for any $\delta\gt 0$. We improve upon this state-of-the-art result, showing that any non-trivial approximation algorithm for Max-Cut requires either polynomially many passes or polynomially large space. More specifically, we show that for all $\varepsilon\gt 0$, a k-pass streaming $(1 / 2+\varepsilon)$-approximation algorithm for Max-Cut requires $\Omega_{\varepsilon}\left(n^{1 / 3} / k\right)$ space. This result leads to a similar lower bound for the Maximum Directed Cut problem, showing the near optimality of the algorithm of [Saxena, Singer, Sudan, Velusamy, SODA 2025]. Our lower bounds proceed by showing a communication complexity lower bound for the Distributional Implicit Hidden Partition (DIHP) Problem, introduced by Kapralov and Krachun. While a naive application of the discrepancy method fails, we identify a property of protocols called “globalness”, and show that (1) any protocol for DIHP can be turned into a global protocol, (2) the discrepancy of a global protocol must be small. The second step is the more technically involved step in the argument, and therein we use global hypercontractive inequalities, and more specifically strong quantitative versions of the level- d inequality for global functions.

Details

FOCS Conference 2025 Conference Paper

On Inverse Theorems and Combinatorial Lines

  • Amey Bhangale
  • Subhash Khot
  • Yang P. Liu
  • Dor Minzer

The problem of studying k-wise correlations in product spaces, i. e. , correlations of the form ${\mathbb{E}_{\left( {{x_1}, \ldots, {x_k}} \right)\sim \mu \otimes n}}\left[ {{f_1}\left( {{x_1}} \right) \cdots f\left( {{x_k}} \right)} \right]$ where ${\text{ }}{f_i}: \sum\nolimits_i^n \to \mathbb{C}$ are all 1-bounded functions and µ is a distribution over Σ 1 × … × Σ k, appears in many different contexts throughout discrete mathematics. Examples include additive combinatorics, extremal combinatorics, hardness of approximation and probability. The goal in an inverse theorem is to characterize the type of functions f 1, …, f k that achieve non-trivial correlations, under minimal assumptions on the distribution µ. We give new inverse theorems for k-wise correlations for all k ⩾ 3. For k = 3, our inverse theorem works for any distribution µ which is pairwise-connected, which is essentially the minimal assumption required for a nontrivial inverse theorem to hold. For k > 3, our inverse theorem applies for distributions µ satisfying the stronger condition of not having any Abelian embeddings. This resolves a conjecture from [Bhangale-Khot-Minzer, STOC 2022]. We give applications of our inverse theorems to additive combinatorics, hardness of approximation, and property testing. First, we show that there exists c > 0 such that any set A ⊆ {0, 1, 2} n with density at least Ω((loglogloglogn) −c ) must contain a combinatorial line, i. e. , x, y, z ∈ {0, 1, 2} n, not all equal, such that x i = y i = z i or (x i, y i, z i ) = (0, 1, 2) for all i = 1, 2, …, n. In other words, we give "reasonable bounds" for the density Hales-Jewett theorem of length 3. This involves combining our inverse theorems with several additional insights, motivated by Shkredov’s proof of the corners theorem and Polymath’s combinatorial proof of the density Hales-Jewett theorem. Second, we show how to construct a dictatorship vs quasi-random test that has perfect completeness and soundness s + ε from integrality gap instances with similar parameters, provided that its local distributions have no Abelian embeddings. Third, we analyze the direct-sum tester of [Dinur-Golubev, RANDOM 2019] in the low-soundness regime.

Details

FOCS Conference 2024 Conference Paper

A Dense Model Theorem for the Boolean Slice

  • Gil Kalai
  • Noam Lifshitz
  • Dor Minzer
  • Tamar Ziegler

The (low soundness) linearity testing problem for the middle slice of the Boolean cube is as follows. Let $\varepsilon > 0$ and $f$ be a function on the middle slice on the Boolean cube, such that when choosing a uniformly random quadruple $(x, y, \ z, x\oplus y\oplus z)$ of vectors of $2n$ bits with exactly $n$ ones, the probability that $f(x\oplus y\oplus z)=f(x)\oplus f(y)\oplus f(z)$ is at least $1/2+\epsilon$. The linearity testing problem, posed by [6], asks whether there must be an actual linear function that agrees with $f$ on $1/2+\epsilon^{\prime}$ fraction of the inputs, where $\varepsilon^{\prime}=\in^{\prime}(\in) > 0$. We solve this problem, showing that $f$ must indeed be correlated with a linear function. To do so, we prove a dense model theorem for the middle slice of the Boolean hypercube for Gowers uniformity norms. Specifically, we show that for every $k\in \mathbb{N}$, the normalized indicator function of the middle slice of the Boolean hypercube $\{0, 1\}^{2n}$ is close in Gowers norm to the normalized indicator function of the union of all slices with weight $t=n(\text{mod}\ 2^{k-1})$. Using our techniques we also give a more general ‘low degree test’ and a biased rank theorem for the slice.

Details

SODA Conference 2024 Conference Paper

Adversarial Low Degree Testing

  • Dor Minzer
  • Kai Zhe Zheng

In the t -online-erasure model in property testing, an adversary is allowed to erase t values of a queried function for each query the tester makes. This model was recently formulated by Kalemaj, Raskhodnikova and Varma, who showed that the properties of linearity of functions as well as quadraticity can be tested in O t (1) many queries: O (log( t )) for linearity and 2 2 O(t) for quadraticity. They asked whether the more general property of low-degreeness can be tested in the online erasure model, whether better testers exist for quadraticity, and if similar results hold when “erasures” are replaced with “corruptions”. We show that, in the t -online-erasure model, for a prime power q, given query access to a function f: 𝔽 q n → 𝔽 q, one can distinguish in poly(log d + q ( t ) /δ) queries between the case that f is degree at most d, and the case that f is δ-far from any degree d function (with respect to the fractional hamming distance). This answers the aforementioned questions and brings the query complexity to nearly match the query complexity of low-degree testing in the classical property testing model. Our results are based on the observation that the property of low-degreeness admits a large and versatile family of query efficient testers. Our testers operates by querying a uniformly random, sufficiently large set of points in a large enough affine subspace, and finding a tester for low-degreeness that only utilizes queries from that set of points. We believe that this tester may find other applications to algorithms in the online-erasure model or other related models, and may be of independent interest. * The full version of the paper can be accessed at https: //arxiv. org/pdf/2308. 15441

Details

FOCS Conference 2024 Conference Paper

Constant Degree Direct Product Testers with Small Soundness

  • Mitali Bafna
  • Noam Lifshitz
  • Dor Minzer

Let $X$ be a d-dimensional simplicial complex. A function $F: X(k)\rightarrow\{0, 1\}^{k}$ is said to be a direct product function if there exists a function $f: x(1)\rightarrow\{0, 1\}$ such that $F(\sigma)=(f(\sigma_{1}), \ \ldots, \ f(\sigma_{k}))$ for each k-face $\sigma$, In an effort to simplify components of the PCP theorem, Goldreich and Safra [1] introduced the problem of direct product testing, which asks whether one can test if $F: X(k)\rightarrow\{0, 1\}^{k}$ - is correlated with a direct product function by querying $F$ on only 2 inputs. Dinur and Kaufman [2] conjectured that there exist bounded degree complexes with a direct product test in the small soundness regime. We resolve their conjecture by showing that for all $\delta > 0$, there exists a family of high-dimensional expanders with degree $O_{\delta}(1)$ and a 2-query direct product tester with soundness $\delta$ We use the characterization given by [3] and independently by [4], who showed that some form of non-Abelian coboundary expansion (which they called “Unique-Games coboundary expansion”) is a necessary and sufficient condition for a complex to admit such direct product testers. Our main technical contribution is a general technique for showing coboundary expansion of complexes with coefficients in a non-Abelian group. This allows us to prove that the high dimensional expanders constructed by [5] satisfy the conditions of [3], thus admitting a 2-query direct product tester with small soundness.

Details

STOC Conference 2024 Conference Paper

Near Optimal Alphabet-Soundness Tradeoff PCPs

  • Dor Minzer
  • Kai Zhe Zheng

We show that for all є>0, for sufficiently large prime power q, for all δ>0, it is NP-hard to distinguish whether a 2-Prover-1-Round projection game with alphabet size q has value at least 1-δ, or value at most 1/q^(1-є). This establishes a nearly optimal alphabet-to-soundness tradeoff for 2-query PCPs with alphabet size q, improving upon a result of [Chan 2016]. Our result has the following implications: 1) Near optimal hardness for Quadratic Programming: it is NP-hard to approximate the value of a given Boolean Quadratic Program within factor (logn)^(1 - o(1)) under quasi-polynomial time reductions. This result improves a result of [Khot-Safra 2013] and nearly matches the performance of the best known approximation algorithm [Megrestki 2001, Nemirovski-Roos-Terlaky 1999 Charikar-Wirth 2004] that achieves a factor of O(logn). 2) Bounded degree 2-CSP’s: under randomized reductions, for sufficiently large d>0, it is NP-hard to approximate the value of 2-CSPs in which each variable appears in at most d constraints within factor (1-o(1))d/2 improving upon a recent result of [Lee-Manurangsi 2023]. 3) Improved hardness results for connectivity problems: using results of [Laekhanukit 2014] and [Manurangsi 2019], we deduce improved hardness results for the Rooted k-Connectivity Problem, the Vertex-Connectivity Survivable Network Design Problem and the Vertex-Connectivity k-Route Cut Problem.

Details

SODA Conference 2023 Conference Paper

Approaching the Soundness Barrier: A Near Optimal Analysis of the Cube versus Cube Test

  • Dor Minzer
  • Kai Zheng

The Cube versus Cube test is a variant of the well-known Plane versus Plane test of Raz and Safra [10], in which to each 3-dimensional affine subspace C of 𝔽 n q, a polynomial of degree at most d, T ( C ), is assigned in a somewhat locally consistent manner: taking two cubes C 1, C 2 that intersect in a plane uniformly at random, the probability that T ( C 1 ) and T ( C 2 ) agree on C 1 ∩ C 2 is at least some ε. An element of interest is the soundness threshold of this test, i. e. the smallest value of ε, such that this amount of local consistency implies a global structure; namely, that there is a global degree d function g such that g| C = T (C) for at least Ω(ε) fraction of the cubes. We show that the cube versus cube low degree test has soundness poly( d )/ q. This result achieves the optimal dependence on q for soundness in low degree testing and improves upon previous soundness results of poly( d )/ q 1/2 due to Bhangale, Dinur and Navon [4].

Details

FOCS Conference 2023 Conference Paper

Optimal Testing of Generalized Reed-Muller Codes in Fewer Queries

  • Dor Minzer
  • Kai Zhe Zheng

A local tester for an error correcting code $C\subseteq\Sigma^{n}$ is a tester that makes Q oracle queries to a given word $w\in\bar{\Sigma}^{n}$ and decides to accept or reject the word w. An optimal local tester is a local tester that has the additional properties of completeness and optimal soundness. By completeness, we mean that the tester must accept with probability 1 if $w\in C$. By optimal soundness, we mean that if the tester accepts with probability at least $ 1-\varepsilon$ (where $\varepsilon$ is small), then it must be the case that w is $O(\varepsilon/Q)$-close to some codeword $c\in C$ in Hamming distance. We show that Generalized Reed-Muller codes admit optimal testers with $Q=(C_{p}q)^{\lceil\frac{d+1}{q-1}\rceil+O(1)}$ queries for $C_{p}=(2p-1)^{\frac{1}{p-1}}$. Here, for a prime power $q=p^{k}$, the Generalized Reed-Muller code, $\operatorname{RM}[n, q, d]$, consists of the evaluations of all n-variate degree d polynomials over $\mathbb{F}_{q}$. As $p, q$, and d go to infinity, Q matches the known lower bound of $q^{\frac{d+1}{q-1}}$ up to a multiplicative factor of 1. Previously, no tester achieving this query complexity was known, and the best known testers due to Haramaty, Shpilka and Sudan [21] (which is optimal) and due to Ron-Zewi and Sudan [33](which was not known to be optimal) both required $q^{\lceil\frac{d+1}{q-q/p}\rceil}$ queries. Our tester achieves query complexity which is polynomially better than by a power of $p/(p-1)$, which is nearly the best query complexity possible for generalized Reed-Muller codes. The tester we analyze is constructed using the same framework of Ron-Zewi and Sudan, and in fact our analysis shows that their tester is optimal as well. More generally, our methods allow us to prove that a wide class of testers, which follow the form of the Ron-Zewi and Sudan tester, are optimal. This result applies to testers for all affine-invariant codes (which are not necessarily generalized Reed-Muller codes).

Details

FOCS Conference 2023 Conference Paper

Parallel Repetition for the GHZ Game: Exponential Decay

  • Mark Braverman
  • Subhash Khot
  • Dor Minzer

We show that the value of the n-fold repeated GHZ game is at most $2^{-\Omega(n)}$, improving upon the polynomial bound established by Holmgren and Raz. Our result is established via a reduction to approximate subgroup type questions from additive combinatorics.

Details

FOCS Conference 2022 Conference Paper

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 complexity theory. The problem is specified by three parameters: field size q, degree d and proximity parameter δ, and the goal is to design a tester making as few as possible queries to a given function, which is able to distinguish between the case the given function has degree at most d, and the case the given function is δ-far from any degree d function. With respect to these parameters, we say that a tester is optimal if it makes $O(q^{t}+1/\delta)$ queries, where $t=t(d, q)$ is the testing dimension of d, q (defined as the minimum integer so that for all $g: \mathbb{F}_{q}^{n}\rightarrow\mathbb{F}_{q}$ of degree more than d, there is a subspace of dimension t on which their restriction has degree exceeding d). For the field of size q, such tester was first given by Bhattacharyya et al. for q = 2, and later by Haramaty et al. [7] for all prime powers q. In fact, they showed that the natural t-flat tester is an optimal tester for the Reed-Muller code, for an appropriate t. Here, the t-flat tester is the tester that picks a uniformly random affine subspace A of dimension t, and checks that $\operatorname{deg}(f|_{A})\leqslant d$. Their analysis proves that the dependency of the t-flat tester on δ and d is optimal, however the dependency on the field size, i. e. the hidden constant in the O, is a tower-type function in q. We improve the result of Haramaty et al. , showing that the dependency on the field size is polynomial. Our technique also applies in the more general setting of lifted affine invariant codes, and gives the same polynomial dependency on the field size. This answers a problem raised in [6]. Our approach significantly deviates from the strategy taken in earlier works [2], [7], [6], and is based on studying the structure of the collection of erroneous subspaces, i. e. subspaces A such that f|A has degree greater than d. Towards this end, we observe that these sets are poorly expanding in the affine version of the Grassmann graph and use that to establish structural results on them via global hypercontractivity. We then use this structure to perform local correction on f.

Details

FOCS Conference 2021 Conference Paper

An Invariance Principle for the Multi-slice, with Applications

  • Mark Braverman
  • Subhash Khot
  • Noam Lifshitz
  • Dor Minzer

Given an alphabet size $m\in\mathbb{N}$ thought of as a constant, and $\vec{k}=(k_{1}, \ldots, k_{m})$ whose entries sum of up $n$, the $\vec{k}$ -multi-slice is the set of vectors $x\in[m]^{n}$ in which each symbol $i\in[m]$ appears precisely $k_{i}$ times. We show an invariance principle for low-degree functions over the multi-slice, to functions over the product space ( $[m]^{n}, \mu^{n}$ ) in which $\mu(i)=k_{i}/n$. This answers a question raised by [21]. As applications of the invariance principle, we show: 1)An analogue of the “dictatorship test implies computational hardness” paradigm for problems with perfect completeness, for a certain class of dictatorship tests. Our computational hardness is proved assuming a recent strengthening of the Unique-Games Conjecture, called the Rich 2-to-1 Games Conjecture. Using this analogue, we show that assuming the Rich 2-to-1 Games Conjecture, (a) there is an $r$ -ary CSP $\mathcal{P}_{r}$ for which it is NP-hard to distinguish satisfiable instances of the CSP and instances that are at most $\frac{2r+1}{2^{r}}+o(1)$ satisfiable, and (b) hardness of distinguishing 3-colorable graphs, and graphs that do not contain an independent set of size $o(1)$. 2)A reduction of the problem of studying expectations of products of functions on the multi-slice to studying expectations of products of functions on correlated, product spaces. In particular, we are able to deduce analogues of the Gaussian bounds from [38] for the multi-slice. 3)In a companion paper, we show further applications of our invariance principle in extremal combinatorics, and more specifically to proving removal lemmas of a wide family of hypergraphs $H$ called $\zeta$ -forests, which is a natural extension of the well-studied case of matchings.

Details

STOC Conference 2020 Conference Paper

AND testing and robust judgement aggregation

  • Yuval Filmus
  • Noam Lifshitz
  • Dor Minzer
  • Elchanan Mossel

A function f ∶{0,1} n → {0,1} is called an approximate AND-homomorphism if choosing x , y ∈ n uniformly at random, we have that f ( x ∧ y ) = f ( x )∧ f ( y ) with probability at least 1−ε, where x ∧ y = ( x 1 ∧ y 1 ,…, x n ∧ y n ). We prove that if f ∶ {0,1} n → {0,1} is an approximate AND-homomorphism, then f is δ-close to either a constant function or an AND function, where δ(ε) → 0 as ε→ 0. This improves on a result of Nehama, who proved a similar statement in which δ depends on n . Our theorem implies a strong result on judgement aggregation in computational social choice. In the language of social choice, our result shows that if f is ε-close to satisfying judgement aggregation, then it is δ(ε)-close to an oligarchy (the name for the AND function in social choice theory). This improves on Nehama’s result, in which δ decays polynomially with n . Our result follows from a more general one, in which we characterize approximate solutions to the eigenvalue equation f = λ g , where is the downwards noise operator f ( x ) = y [ f ( x ∧ y )], f is [0,1]-valued, and g is {0,1}-valued. We identify all exact solutions to this equation, and show that any approximate solution in which f and λ g are close is close to an exact solution.

Details

FOCS Conference 2020 Conference Paper

Towards a Proof of the Fourier-Entropy Conjecture?

  • Esty Kelman
  • Guy Kindler
  • Noam Lifshitz
  • Dor Minzer
  • Muli Safra

The total influence of a function is a central notion in analysis of Boolean functions, and characterizing functions that have small total influence is one of the most fundamental questions associated with it. The KKL theorem and the Friedgut junta theorem give a strong characterization of such functions whenever the bound on the total influence is $o(\log n)$. However, both results become useless when the total influence of the function is $\omega(\log n)$. The only case in which this logarithmic barrier has been broken for an interesting class of functions was proved by Bourgain and Kalai, who focused on functions that are symmetric under large enough subgroups of $S_{n}$. In this paper, we build and improve on the techniques of the Bourgain-Kalai paper and establish new concentration results on the Fourier spectrum of Boolean functions with small total influence. Our results include: 1)A quantitative improvement of the Bourgain–Kalai result regarding the total influence of functions that are transitively symmetric. 2)A slightly weaker version of the Fourier–Entropy Conjecture of Friedgut and Kalai. Our result establishes new bounds on the Fourier entropy of a Boolean function $f$, as well as stronger bounds on the Fourier entropy of low-degree parts of $f$. In particular, it implies that the Fourier spectrum of a constant variance, Boolean function $f$ is concentrated on $2^{O(I[f]\log I[f])}$ characters, improving an earlier result of Friedgut. Removing the $\log I[f]$ factor would essentially resolve the Fourier–Entropy Conjecture, as well as settle a conjecture of Mansour regarding the Fourier spectrum of polynomial size DNF formulas. Our concentration result for the Fourier spectrum of functions with small total influence also has new implications in learning theory. More specifically, we conclude that the class of functions whose total influence is at most $K$ is agnostically learnable in time $2^{O(K\log K)}$ using membership queries. Thus, the class of functions with total influence $O(\log n/\log\log n)$ is agnostically learnable in $\text{poly}(n)$ time.

Details

FOCS Conference 2019 Conference Paper

Noise Sensitivity on the p -Biased Hypercube

  • Noam Lifshitz
  • Dor Minzer

The noise sensitivity of a Boolean function measures how susceptible the value of f on a typical input x to a slight perturbation of the bits of x: it is the probability f(x) and f(y) are different when x is a uniformly chosen n-bit Boolean string, and y is formed by flipping each bit of x with small probability ε. The noise sensitivity of a function is a key concept with applications to combinatorics, complexity theory, learning theory, percolation theory and more. In this paper, we investigate noise sensitivity on the p-biased hypercube, extending the theory for polynomially small p. Specifically, we give sufficient conditions for monotone functions with large groups of symmetries to be noise sensitive (which in some cases are also necessary). As an application, we show that the 2-SAT function is noise sensitive around its critical probability. En route, we study biased versions of the invariance principle for monotone functions and give p-biased versions of Bourgain's tail theorem and the Majority is Stablest theorem, showing that in this case the correct analog of ``small low degree influences'' is lack of correlation with constant width DNF formulas.

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

FOCS Conference 2018 Conference Paper

Pseudorandom Sets in Grassmann Graph Have Near-Perfect Expansion

  • Subhash Khot
  • Dor Minzer
  • Muli Safra

We prove that pseudorandom sets in the Grassmann graph have near-perfect expansion. This completes the last missing piece of the proof of the 2-to-2-Games Conjecture (albeit with imperfect completeness). The Grassmann graph has induced subgraphs that are themselves isomorphic to Grassmann graphs of lower orders. A set of vertices is called pseudorandom if its density within all such subgraphs (of constant order) is at most slightly higher than its density in the entire graph. We prove that pseudorandom sets have almost no edges within them. Namely, their edge-expansion is very close to 1.

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

STOC Conference 2017 Conference Paper

On independent sets, 2-to-2 games, and Grassmann graphs

  • Subhash Khot
  • Dor Minzer
  • Muli Safra

We present a candidate reduction from the 3-Lin problem to the 2-to-2 Games problem and present a combinatorial hypothesis about Grassmann graphs which, if correct, is sufficient to show the soundness of the reduction in a certain non-standard sense. A reduction that is sound in this non-standard sense implies that it is NP-hard to distinguish whether an n -vertex graph has an independent set of size ( 1- 1/√2 ) n - o ( n ) or whether every independent set has size o ( n ), and consequently, that it is NP-hard to approximate the Vertex Cover problem within a factor √2- o (1).

Details

FOCS Conference 2015 Conference Paper

On Monotonicity Testing and Boolean Isoperimetric Type Theorems

  • Subhash Khot
  • Dor Minzer
  • Muli Safra

We show a directed and robust analogue of a boolean isoperimetric type theorem of Talagrand [13]. As an application, we give a monotonicity testing algorithm that makes O̅(√n/ε 2 ) non-adaptive queries to a function f: {0, 1} n → {0, 1}, always accepts a monotone function and rejects a function that is ε-far from being monotone with constant probability.

Details