-
Rounding Large Independent Sets on Expanders
Authors:
Mitali Bafna,
Jun-Ting Hsieh,
Pravesh K. Kothari
Abstract:
We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has the second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost $3$-colorable or are promised to contain an inde…
▽ More
We develop a new approach for approximating large independent sets when the input graph is a one-sided spectral expander - that is, the uniform random walk matrix of the graph has the second eigenvalue bounded away from 1. Consequently, we obtain a polynomial time algorithm to find linear-sized independent sets in one-sided expanders that are almost $3$-colorable or are promised to contain an independent set of size $(1/2-ε)n$. Our second result above can be refined to require only a weaker vertex expansion property with an efficient certificate. Somewhat surprisingly, we observe that the analogous task of finding a linear-sized independent set in almost $4$-colorable one-sided expanders (even when the second eigenvalue is $o_n(1)$) is NP-hard, assuming the Unique Games Conjecture.
All prior algorithms that beat the worst-case guarantees for this problem rely on bottom eigenspace enumeration techniques (following the classical spectral methods of Alon and Kahale) and require two-sided expansion, meaning a bounded number of negative eigenvalues of magnitude $Ω(1)$. Such techniques naturally extend to almost $k$-colorable graphs for any constant $k$, in contrast to analogous guarantees on one-sided expanders, which are Unique Games-hard to achieve for $k \geq 4$.
Our rounding builds on the method of simulating multiple samples from a pseudodistribution introduced by Barak et. al. for rounding Unique Games instances. The key to our analysis is a new clustering property of large independent sets in expanding graphs - every large independent set has a larger-than-expected intersection with some member of a small list - and its formalization in the low-degree sum-of-squares proof system.
△ Less
Submitted 16 May, 2024;
originally announced May 2024.
-
Constant Degree Direct Product Testers with Small Soundness
Authors:
Mitali Bafna,
Noam Lifshitz,
Dor Minzer
Abstract:
Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(σ) = (f(σ_1), \ldots, f(σ_k))$ for each $k$-face $σ$. In an effort to simplify components of the PCP theorem, Goldreich and Safra introduced the problem of direct product testing, which asks whether one can…
▽ More
Let $X$ be a $d$-dimensional simplicial complex. A function $F\colon X(k)\to \{0,1\}^k$ is said to be a direct product function if there exists a function $f\colon X(1)\to \{0,1\}$ such that $F(σ) = (f(σ_1), \ldots, f(σ_k))$ for each $k$-face $σ$. In an effort to simplify components of the PCP theorem, Goldreich and Safra introduced the problem of direct product testing, which asks whether one can test if $F\colon X(k)\to \{0,1\}^k$ is correlated with a direct product function by querying $F$ on only $2$ inputs. Dinur and Kaufman 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 $δ>0$, there exists a family of high-dimensional expanders with degree $O_δ(1)$ and a $2$-query direct product tester with soundness $δ$.
We use the characterization given by a subset of the authors and independently by Dikstein and Dinur, 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 Chapman and Lubotzky satisfies the necessary conditions, thus admitting a 2-query direct product tester with small soundness.
△ Less
Submitted 7 February, 2024; v1 submitted 1 February, 2024;
originally announced February 2024.
-
Characterizing Direct Product Testing via Coboundary Expansion
Authors:
Mitali Bafna,
Dor Minzer
Abstract:
A $d$-dimensional simplicial complex $X$ is said to support a direct product tester if any locally consistent function defined on its $k$-faces (where $k\ll d$) necessarily come from a function over its vertices. More precisely, a direct product tester has a distribution $μ$ over pairs of $k$-faces $(A,A')$, and given query access to $F\colon X(k)\to\{0,1\}^k$ it samples $(A,A')\sim μ$ and checks…
▽ More
A $d$-dimensional simplicial complex $X$ is said to support a direct product tester if any locally consistent function defined on its $k$-faces (where $k\ll d$) necessarily come from a function over its vertices. More precisely, a direct product tester has a distribution $μ$ over pairs of $k$-faces $(A,A')$, and given query access to $F\colon X(k)\to\{0,1\}^k$ it samples $(A,A')\sim μ$ and checks that $F[A]|_{A\cap A'} = F[A']|_{A\cap A'}$. The tester should have (1) the ``completeness property'', meaning that any assignment $F$ which is a direct product assignment passes the test with probability $1$, and (2) the ``soundness property'', meaning that if $F$ passes the test with probability $s$, then $F$ must be correlated with a direct product function.
Dinur and Kaufman showed that a sufficiently good spectral expanding complex $X$ admits a direct product tester in the ``high soundness'' regime where $s$ is close to $1$. They asked whether there are high dimensional expanders that support direct product tests in the ``low soundness'', when $s$ is close to $0$.
We give a characterization of high-dimensional expanders that support a direct product tester in the low soundness regime. We show that spectral expansion is insufficient, and the complex must additionally satisfy a variant of coboundary expansion, which we refer to as \emph{Unique-Games coboundary expanders}. Conversely, we show that this property is also sufficient to get direct product testers. This property can be seen as a high-dimensional generalization of the standard notion of coboundary expansion over non-Abelian groups for 2-dimensional complexes. It asserts that any locally consistent Unique-Games instance obtained using the low-level faces of the complex, must admit a good global solution.
△ Less
Submitted 1 February, 2024; v1 submitted 18 August, 2023;
originally announced August 2023.
-
Solving Unique Games over Globally Hypercontractive Graphs
Authors:
Mitali Bafna,
Dor Minzer
Abstract:
We study the complexity of affine Unique-Games (UG) over globally hypercontractive graphs, which are graphs that are not small set expanders but admit a useful and succinct characterization of all small sets that violate the small-set expansion property. This class of graphs includes the Johnson and Grassmann graphs, which have played a pivotal role in recent PCP constructions for UG, and their ge…
▽ More
We study the complexity of affine Unique-Games (UG) over globally hypercontractive graphs, which are graphs that are not small set expanders but admit a useful and succinct characterization of all small sets that violate the small-set expansion property. This class of graphs includes the Johnson and Grassmann graphs, which have played a pivotal role in recent PCP constructions for UG, and their generalizations via high-dimensional expanders.
Our algorithm shows how to round "low-entropy" solutions to sum-of-squares (SoS) semidefinite programs, broadly extending the algorithmic framework of [BBKSS'21]. We give a new rounding scheme for SoS, which eliminates global correlations in a given pseudodistribution so that it retains various good properties even after conditioning. Getting structural control over a pseudodistribution after conditioning is a fundamental challenge in many SoS based algorithms. Due to these challenges, [BBKSS] were not able to establish strong algorithms for globally hypercontractive graphs, and could only do so for certifiable small-set expanders. Our results improve upon the results of [BBKSS] in various aspects: we are able to deal with instances with arbitrarily small (but constant) completeness, and most importantly, their algorithm gets a soundness guarantee that degrades with other parameters of the graph (which in all PCP constructions grow with the alphabet size), whereas our doesn't.
Our result suggests that UG is easy on globally hypercontractive graphs, and therefore highlights the importance of graphs that lack such a characterization in the context of PCP reductions for UG.
△ Less
Submitted 14 April, 2023;
originally announced April 2023.
-
Polynomial-Time Power-Sum Decomposition of Polynomials
Authors:
Mitali Bafna,
Jun-Ting Hsieh,
Pravesh K. Kothari,
Jeff Xu
Abstract:
We give efficient algorithms for finding power-sum decomposition of an input polynomial $P(x)= \sum_{i\leq m} p_i(x)^d$ with component $p_i$s. The case of linear $p_i$s is equivalent to the well-studied tensor decomposition problem while the quadratic case occurs naturally in studying identifiability of non-spherical Gaussian mixtures from low-order moments.
Unlike tensor decomposition, both the…
▽ More
We give efficient algorithms for finding power-sum decomposition of an input polynomial $P(x)= \sum_{i\leq m} p_i(x)^d$ with component $p_i$s. The case of linear $p_i$s is equivalent to the well-studied tensor decomposition problem while the quadratic case occurs naturally in studying identifiability of non-spherical Gaussian mixtures from low-order moments.
Unlike tensor decomposition, both the unique identifiability and algorithms for this problem are not well-understood. For the simplest setting of quadratic $p_i$s and $d=3$, prior work of Ge, Huang and Kakade yields an algorithm only when $m \leq \tilde{O}(\sqrt{n})$. On the other hand, the more general recent result of Garg, Kayal and Saha builds an algebraic approach to handle any $m=n^{O(1)}$ components but only when $d$ is large enough (while yielding no bounds for $d=3$ or even $d=100$) and only handles an inverse exponential noise.
Our results obtain a substantial quantitative improvement on both the prior works above even in the base case of $d=3$ and quadratic $p_i$s. Specifically, our algorithm succeeds in decomposing a sum of $m \sim \tilde{O}(n)$ generic quadratic $p_i$s for $d=3$ and more generally the $d$th power-sum of $m \sim n^{2d/15}$ generic degree-$K$ polynomials for any $K \geq 2$. Our algorithm relies only on basic numerical linear algebraic primitives, is exact (i.e., obtain arbitrarily tiny error up to numerical precision), and handles an inverse polynomial noise when the $p_i$s have random Gaussian coefficients.
Our main tool is a new method for extracting the linear span of $p_i$s by studying the linear subspace of low-order partial derivatives of the input $P$. For establishing polynomial stability of our algorithm in average-case, we prove inverse polynomial bounds on the smallest singular value of certain correlated random matrices with low-degree polynomial entries that arise in our analyses.
△ Less
Submitted 29 July, 2022;
originally announced August 2022.
-
Hypercontractivity on High Dimensional Expanders: a Local-to-Global Approach for Higher Moments
Authors:
Mitali Bafna,
Max Hopkins,
Tali Kaufman,
Shachar Lovett
Abstract:
Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of Khot's 2-2 Games Conjecture (Khot, M…
▽ More
Hypercontractivity is one of the most powerful tools in Boolean function analysis. Originally studied over the discrete hypercube, recent years have seen increasing interest in extensions to settings like the $p$-biased cube, slice, or Grassmannian, where variants of hypercontractivity have found a number of breakthrough applications including the resolution of Khot's 2-2 Games Conjecture (Khot, Minzer, Safra FOCS 2018). In this work, we develop a new theory of hypercontractivity on high dimensional expanders (HDX), an important class of expanding complexes that has recently seen similarly impressive applications in both coding theory and approximate sampling. Our results lead to a new understanding of the structure of Boolean functions on HDX, including a tight analog of the KKL Theorem and a new characterization of non-expanding sets.
Unlike previous settings satisfying hypercontractivity, HDX can be asymmetric, sparse, and very far from products, which makes the application of traditional proof techniques challenging. We handle these barriers with the introduction of two new tools of independent interest: a new explicit combinatorial Fourier basis for HDX that behaves well under restriction, and a new local-to-global method for analyzing higher moments. Interestingly, unlike analogous second moment methods that apply equally across all types of expanding complexes, our tools rely inherently on simplicial structure. This suggests a new distinction among high dimensional expanders based upon their behavior beyond the second moment.
△ Less
Submitted 24 November, 2021; v1 submitted 17 November, 2021;
originally announced November 2021.
-
Optimal Fine-grained Hardness of Approximation of Linear Equations
Authors:
Mitali Bafna,
Nikhil Vyas
Abstract:
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system $(A,b)$, for $A \in \mathbb{R}^{n \times n}$ and $b \in \mathbb{R}^n$, we wish to find a vector $x \in \mathbb{R}^n$ such that $Ax = b$. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time…
▽ More
The problem of solving linear systems is one of the most fundamental problems in computer science, where given a satisfiable linear system $(A,b)$, for $A \in \mathbb{R}^{n \times n}$ and $b \in \mathbb{R}^n$, we wish to find a vector $x \in \mathbb{R}^n$ such that $Ax = b$. The current best algorithms for solving dense linear systems reduce the problem to matrix multiplication, and run in time $O(n^ω)$. We consider the problem of finding $\varepsilon$-approximate solutions to linear systems with respect to the $L_2$-norm, that is, given a satisfiable linear system $(A \in \mathbb{R}^{n \times n}, b \in \mathbb{R}^n)$, find an $x \in \mathbb{R}^n$ such that $||Ax - b||_2 \leq \varepsilon||b||_2$. Our main result is a fine-grained reduction from computing the rank of a matrix to finding $\varepsilon$-approximate solutions to linear systems. In particular, if the best known $O(n^ω)$ time algorithm for computing the rank of $n \times O(n)$ matrices is optimal (which we conjecture is true), then finding an $\varepsilon$-approximate solution to a dense linear system also requires $\tildeΩ(n^ω)$ time, even for $\varepsilon$ as large as $(1 - 1/\text{poly}(n))$. We also prove (under some modified conjectures for the rank-finding problem) optimal hardness of approximation for sparse linear systems, linear systems over positive semidefinite matrices, well-conditioned linear systems, and approximately solving linear systems with respect to the $L_p$-norm, for $p \geq 1$. At the heart of our results is a novel reduction from the rank problem to a decision version of the approximate linear systems problem. This reduction preserves properties such as matrix sparsity and bit complexity.
△ Less
Submitted 24 June, 2021;
originally announced June 2021.
-
High Dimensional Expanders: Eigenstripping, Pseudorandomness, and Unique Games
Authors:
Mitali Bafna,
Max Hopkins,
Tali Kaufman,
Shachar Lovett
Abstract:
Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass [KM16], yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders [DK17], which of…
▽ More
Higher order random walks (HD-walks) on high dimensional expanders (HDX) have seen an incredible amount of study and application since their introduction by Kaufman and Mass [KM16], yet their broader combinatorial and spectral properties remain poorly understood. We develop a combinatorial characterization of the spectral structure of HD-walks on two-sided local-spectral expanders [DK17], which offer a broad generalization of the well-studied Johnson and Grassmann graphs. Our characterization, which shows that the spectra of HD-walks lie tightly concentrated in a few combinatorially structured strips, leads to novel structural theorems such as a tight $\ell_2$-characterization of edge-expansion, as well as to a new understanding of local-to-global algorithms on HDX.
Towards the latter, we introduce a spectral complexity measure called Stripped Threshold Rank, and show how it can replace the (much larger) threshold rank in controlling the performance of algorithms on structured objects. Combined with a sum-of-squares proof of the former $\ell_2$-characterization, we give a concrete application of this framework to algorithms for unique games on HD-walks, in many cases improving the state of the art [RBS11, ABS15] from nearly-exponential to polynomial time (e.g. for sparsifications of Johnson graphs or of slices of the $q$-ary hypercube). Our characterization of expansion also holds an interesting connection to hardness of approximation, where an $\ell_\infty$-variant for the Grassmann graphs was recently used to resolve the 2-2 Games Conjecture [KMS18]. We give a reduction from a related $\ell_\infty$-variant to our $\ell_2$-characterization, but it loses factors in the regime of interest for hardness where the gap between $\ell_2$ and $\ell_\infty$ structure is large. Nevertheless, we open the door for further work on the use of HDX in hardness of approximation and unique games.
△ Less
Submitted 17 July, 2021; v1 submitted 9 November, 2020;
originally announced November 2020.
-
Playing Unique Games on Certified Small-Set Expanders
Authors:
Mitali Bafna,
Boaz Barak,
Pravesh Kothari,
Tselil Schramm,
David Steurer
Abstract:
We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally…
▽ More
We give an algorithm for solving unique games (UG) instances whenever low-degree sum-of-squares proofs certify good bounds on the small-set-expansion of the underlying constraint graph via a hypercontractive inequality. Our algorithm is in fact more versatile, and succeeds even when the constraint graph is not a small-set expander as long as the structure of non-expanding small sets is (informally speaking) "characterized" by a low-degree sum-of-squares proof. Our results are obtained by rounding \emph{low-entropy} solutions -- measured via a new global potential function -- to sum-of-squares (SoS) semidefinite programs. This technique adds to the (currently short) list of general tools for analyzing SoS relaxations for \emph{worst-case} optimization problems.
As corollaries, we obtain the first polynomial-time algorithms for solving any UG instance where the constraint graph is either the \emph{noisy hypercube}, the \emph{short code} or the \emph{Johnson} graph. The prior best algorithm for such instances was the eigenvalue enumeration algorithm of Arora, Barak, and Steurer (2010) which requires quasi-polynomial time for the noisy hypercube and nearly-exponential time for the short code and Johnson graphs. All of our results achieve an approximation of $1-ε$ vs $δ$ for UG instances, where $ε>0$ and $δ> 0$ depend on the expansion parameters of the graph but are independent of the alphabet size.
△ Less
Submitted 26 June, 2021; v1 submitted 17 June, 2020;
originally announced June 2020.
-
Imperfect Gaps in Gap-ETH and PCPs
Authors:
Mitali Bafna,
Nikhil Vyas
Abstract:
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfect completeness when the initial gap is a constant. In particular, we show that $\text{PCP}_{c,s}[r,q] \subseteq \text{PCP}_{1,1-Ω(1)}[r+O(1),q+O(r)]$, for $c-s=Ω(1)$. This implies that one can convert imperfect completen…
▽ More
We study the role of perfect completeness in probabilistically checkable proof systems (PCPs) and give a new way to transform a PCP with imperfect completeness to a PCP with perfect completeness when the initial gap is a constant. In particular, we show that $\text{PCP}_{c,s}[r,q] \subseteq \text{PCP}_{1,1-Ω(1)}[r+O(1),q+O(r)]$, for $c-s=Ω(1)$. This implies that one can convert imperfect completeness to perfect in linear-sized PCPs for $NTIME[O(n)]$ with a $O(\log n)$ additive loss in the query complexity $q$. We show our result by constructing a "robust circuit" using threshold gates. These results are a gap amplification procedure for PCPs (when completeness is imperfect), analogous to questions studied in parallel repetition and pseudorandomness.
We also investigate the time complexity of approximating perfectly satisfiable instances of 3SAT versus those with imperfect completeness. We show that the Gap-ETH conjecture without perfect completeness is equivalent to Gap-ETH with perfect completeness, i.e. we show that Gap-3SAT, where the gap is not around 1, has a subexponential algorithm, if and only if, Gap-3SAT with perfect completeness has subexponential algorithms. We also relate the time complexities of these two problems in a more fine-grained way, to show that $T_2(n) \leq T_1(n(\log\log n)^{O(1)})$, where $T_1(n),T_2(n)$ denote the randomized time-complexity of approximating MAX 3SAT with perfect and imperfect completeness, respectively.
△ Less
Submitted 18 July, 2019;
originally announced July 2019.
-
Thwarting Adversarial Examples: An $L_0$-RobustSparse Fourier Transform
Authors:
Mitali Bafna,
Jack Murtagh,
Nikhil Vyas
Abstract:
We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that has been corrupted by worst-case $L_0$ noise, namely a bounded number of coordinates of the signal have been corrupted arbitrarily. Our techniques generalize to a wide range of linear transformations that are used in data analysis such as the Discrete Cosine and Sine transforms, the Hada…
▽ More
We give a new algorithm for approximating the Discrete Fourier transform of an approximately sparse signal that has been corrupted by worst-case $L_0$ noise, namely a bounded number of coordinates of the signal have been corrupted arbitrarily. Our techniques generalize to a wide range of linear transformations that are used in data analysis such as the Discrete Cosine and Sine transforms, the Hadamard transform, and their high-dimensional analogs. We use our algorithm to successfully defend against well known $L_0$ adversaries in the setting of image classification. We give experimental results on the Jacobian-based Saliency Map Attack (JSMA) and the Carlini Wagner (CW) $L_0$ attack on the MNIST and Fashion-MNIST datasets as well as the Adversarial Patch on the ImageNet dataset.
△ Less
Submitted 12 December, 2018;
originally announced December 2018.
-
Communication-Rounds Tradeoffs for Common Randomness and Secret Key Generation
Authors:
Mitali Bafna,
Badih Ghazi,
Noah Golowich,
Madhu Sudan
Abstract:
We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $μ$. They wish to communicate so as to agree on $L$ bits…
▽ More
We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples $X_1,X_2,\dots$ and $Y_1,Y_2,\dots$ with the pairs $(X_1,Y_1)$, $(X_2, Y_2)$, $\dots$ being drawn independently from some known probability distribution $μ$. They wish to communicate so as to agree on $L$ bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions $μ= μ_{r, n,L}$, parametrized by integers $r$, $n$ and $L$, such that for every $r$ there exists a constant $b = b(r)$ for which CRG (respectively SKG) is feasible when $(X_i,Y_i) \sim μ_{r,n,L}$ with $r+1$ rounds of communication, each consisting of $O(\log n)$ bits, but when restricted to $r/2 - 3$ rounds of interaction, the total communication must exceed $Ω(n/\log^{b}(n))$ bits. Prior to our work no separations were known for $r \geq 2$.
△ Less
Submitted 27 August, 2018;
originally announced August 2018.
-
Local decoding and testing of polynomials over grids
Authors:
Mitali Bafna,
Srikanth Srinivasan,
Madhu Sudan
Abstract:
The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate polynomials of total degree at most $d$ over grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$). In this work we explore their local decodability and (tolerant) local testability. While these aspects have been st…
▽ More
The well-known DeMillo-Lipton-Schwartz-Zippel lemma says that $n$-variate polynomials of total degree at most $d$ over grids, i.e. sets of the form $A_1 \times A_2 \times \cdots \times A_n$, form error-correcting codes (of distance at least $2^{-d}$ provided $\min_i\{|A_i|\}\geq 2$). In this work we explore their local decodability and (tolerant) local testability. While these aspects have been studied extensively when $A_1 = \cdots = A_n = \mathbb{F}_q$ are the same finite field, the setting when $A_i$'s are not the full field does not seem to have been explored before.
In this work we focus on the case $A_i = \{0,1\}$ for every $i$. We show that for every field (finite or otherwise) there is a test whose query complexity depends only on the degree (and not on the number of variables). In contrast we show that decodability is possible over fields of positive characteristic (with query complexity growing with the degree of the polynomial and the characteristic), but not over the reals, where the query complexity must grow with $n$. As a consequence we get a natural example of a code (one with a transitive group of symmetries) that is locally testable but not locally decodable.
Classical results on local decoding and testing of polynomials have relied on the 2-transitive symmetries of the space of low-degree polynomials (under affine transformations). Grids do not possess this symmetry: So we introduce some new techniques to overcome this handicap and in particular use the hypercontractivity of the (constant weight) noise operator on the Hamming cube.
△ Less
Submitted 14 December, 2018; v1 submitted 18 September, 2017;
originally announced September 2017.
-
The Price of Selection in Differential Privacy
Authors:
Mitali Bafna,
Jonathan Ullman
Abstract:
In the differentially private top-$k$ selection problem, we are given a dataset $X \in \{\pm 1\}^{n \times d}$, in which each row belongs to an individual and each column corresponds to some binary attribute, and our goal is to find a set of $k \ll d$ columns whose means are approximately as large as possible. Differential privacy requires that our choice of these $k$ columns does not depend too m…
▽ More
In the differentially private top-$k$ selection problem, we are given a dataset $X \in \{\pm 1\}^{n \times d}$, in which each row belongs to an individual and each column corresponds to some binary attribute, and our goal is to find a set of $k \ll d$ columns whose means are approximately as large as possible. Differential privacy requires that our choice of these $k$ columns does not depend too much on any on individual's dataset. This problem can be solved using the well known exponential mechanism and composition properties of differential privacy. In the high-accuracy regime, where we require the error of the selection procedure to be to be smaller than the so-called sampling error $α\approx \sqrt{\ln(d)/n}$, this procedure succeeds given a dataset of size $n \gtrsim k \ln(d)$.
We prove a matching lower bound, showing that a dataset of size $n \gtrsim k \ln(d)$ is necessary for private top-$k$ selection in this high-accuracy regime. Our lower bound is the first to show that selecting the $k$ largest columns requires more data than simply estimating the value of those $k$ columns, which can be done using a dataset of size just $n \gtrsim k$.
△ Less
Submitted 9 February, 2017;
originally announced February 2017.
