Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Irit Dinur:

TR18-075 | 23rd April 2018
Irit Dinur, Yuval Filmus, Prahladh Harsha

Boolean function analysis on high-dimensional expanders

We initiate the study of Boolean function analysis on high-dimensional expanders. We describe an analog of the Fourier expansion and of the Fourier levels on simplicial complexes, and generalize the FKN theorem to high-dimensional expanders.

Our results demonstrate that a high-dimensional expanding complex X can sometimes serve as a sparse ... more >>>

TR18-050 | 15th March 2018
Irit Dinur, Oded Goldreich, Tom Gur

Every set in P is strongly testable under a suitable encoding

We show that every set in $\cal P$ is strongly testable under a suitable encoding. By ``strongly testable'' we mean having a (proximity oblivious) tester that makes a constant number of queries and rejects with probability that is proportional to the distance of the tested object from the property. By ... more >>>

TR17-181 | 26th November 2017
Irit Dinur, Yuval Filmus, Prahladh Harsha

Agreement tests on graphs and hypergraphs

Agreement tests are a generalization of low degree tests that capture a local-to-global phenomenon, which forms the combinatorial backbone of most PCP constructions. In an agreement test, a function is given by an ensemble of local restrictions. The agreement test checks that the restrictions agree when they overlap, and the ... more >>>

TR17-180 | 26th November 2017
Irit Dinur, Yuval Filmus, Prahladh Harsha

Low degree almost Boolean functions are sparse juntas

Nisan and Szegedy showed that low degree Boolean functions are juntas. Kindler and Safra showed that low degree functions which are *almost* Boolean are close to juntas. Their result holds with respect to $\mu_p$ for every *constant* $p$. When $p$ is allowed to be very small, new phenomena emerge. ... more >>>

TR17-096 | 30th May 2017
Irit Dinur, Inbal Livni Navon

Exponentially Small Soundness for the Direct Product Z-test

Given a function $f:[N]^k\rightarrow[M]^k$, the Z-test is a three query test for checking if a function $f$ is a direct product, namely if there are functions $g_1,\dots g_k:[N]\to[M]$ such that $f(x_1,\ldots,x_k)=(g_1(x_1),\dots g_k(x_k))$ for every input $x\in [N]^k$.

This test was introduced by Impagliazzo et. al. (SICOMP 2012), who ... more >>>

TR17-094 | 25th May 2017
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

On Non-Optimally Expanding Sets in Grassmann Graphs

The paper investigates expansion properties of the Grassmann graph,
motivated by recent results of [KMS, DKKMS] concerning hardness
of the Vertex-Cover and of the $2$-to-$1$ Games problems. Proving the
hypotheses put forward by these papers seems to first require a better
understanding of these expansion properties.

We consider the edge ... more >>>

TR17-089 | 11th May 2017
Irit Dinur, Tali Kaufman

High dimensional expanders imply agreement expanders

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 ... more >>>

TR16-205 | 22nd December 2016
Amey Bhangale, Irit Dinur, Inbal Livni Navon

Cube vs. Cube Low Degree Test

We revisit the Raz-Safra plane-vs.-plane test and study the closely related cube vs. cube test. In this test the tester has access to a "cubes table" which assigns to every cube a low degree polynomial. The tester randomly selects two cubes (affine sub-spaces of dimension $3$) that intersect on a ... more >>>

TR16-198 | 14th December 2016
Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra

Towards a Proof of the 2-to-1 Games Conjecture?

We propose a combinatorial hypothesis regarding a subspace vs. subspace agreement test, and prove that if correct it leads to a proof of the 2-to-1 Games Conjecture, albeit with imperfect completeness.

more >>>

TR16-160 | 26th October 2016
Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Multiplayer parallel repetition for expander games

Revisions: 1

We investigate the value of parallel repetition of one-round games with any number of players $k\ge 2$. It has been an open question whether an analogue of Raz's Parallel Repetition Theorem holds for games with more than two players, i.e., whether the value of the repeated game decays exponentially ... more >>>

TR16-128 | 13th August 2016
Irit Dinur

Mildly exponential reduction from gap 3SAT to polynomial-gap label-cover

We show that if gap-3SAT has no sub-exponential time algorithms then a weak form of the sliding scale conjecture holds. Namely, for every $\alpha>0$ any algorithm for $n^\alpha$-approximating the value of label cover must run in time at least $n^{\Omega(\exp(1/\alpha))}$, where $n$ is the size of the instance.

Put differently, ... more >>>

TR16-035 | 11th March 2016
Irit Dinur, Or Meir

Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected'' with respect to the composition of functions $f\circ g$. They showed that this conjecture, ... more >>>

TR15-085 | 23rd May 2015
Irit Dinur, Prahladh Harsha, Guy Kindler

Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

We show that every language in NP has a PCP verifier that tosses $O(\log n)$ random coins, has perfect completeness, and a soundness error of at most $1/poly(n)$, while making at most $O(poly\log\log n)$ queries into a proof over an alphabet of size at most $n^{1/poly\log\log n}$. Previous constructions that ... more >>>

TR14-083 | 19th June 2014
Irit Dinur, Shafi Goldwasser, Huijia Lin

The Computational Benefit of Correlated Instances

The starting point of this paper is that instances of computational problems often do not exist in isolation. Rather, multiple and correlated instances of the same problem arise naturally in the real world. The challenge is how to gain computationally from instance correlations when they exist. We will be interested ... more >>>

TR14-002 | 8th January 2014
Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

Direct Sum Testing

For a string $a \in \{0,1\}^n$ its $k$-fold direct sum encoding is a function $f_a$ that takes as input sets $S \subseteq [n]$ of
size $k$ and outputs $f_a(S) = \sum_{i \in S} a_i$.
In this paper we are interested in the Direct Sum Testing Problem,
where we are given ... more >>>

TR13-179 | 15th December 2013
Irit Dinur, David Steurer

Direct Product Testing

A direct product is a function of the form $g(x_1,\ldots,x_k)=(g_1(x_1),\ldots,g_k(x_k))$. We show that the direct product property is locally testable with $2$ queries, that is, a canonical two-query test distinguishes between direct products and functions that are from direct products with constant probability.

This local testing question comes up ... more >>>

TR13-148 | 26th October 2013
Irit Dinur, Igor Shinkar

On the Conditional Hardness of Coloring a 4-colorable Graph with Super-Constant Number of Colors

For $3 \leq q < Q$ we consider the $\text{ApproxColoring}(q,Q)$ problem of deciding for a given graph $G$ whether $\chi(G) \leq q$ or $\chi(G) \geq Q$. It was show in [DMR06] that the problem $\text{ApproxColoring}(q,Q)$ is NP-hard for $q=3,4$ and arbitrary large constant $Q$ under variants of the Unique Games ... more >>>

TR13-122 | 5th September 2013
Irit Dinur, Venkatesan Guruswami

PCPs via low-degree long code and hardness for constrained hypergraph coloring

Revisions: 1

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 ... more >>>

TR13-031 | 22nd February 2013
Irit Dinur, Elazar Goldenberg

Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

We consider the following clustering with outliers problem: Given a set of points $X \subset \{-1,1\}^n$, such that there is some point $z \in \{-1,1\}^n$ for which at least $\delta$ of the points are $\epsilon$-correlated with $z$, find $z$. We call such a point $z$ a $(\delta,\epsilon)$-center of X.

In ... more >>>

TR12-088 | 7th July 2012
Irit Dinur, Gillat Kol

Covering CSPs

We study the covering complexity of constraint satisfaction problems (CSPs). The covering number of a CSP instance C, denoted $\nu(C)$, is the smallest number of assignments to the variables, such that each constraint is satisfied by at least one of the assignments. This covering notion describes situations in which we ... more >>>

TR11-055 | 14th April 2011
Irit Dinur, Tali Kaufman

Dense locally testable codes cannot have constant rate and distance

A q-query locally testable code (LTC) is an error correcting code that can be tested by a randomized algorithm that reads at most q symbols from the given word.
An important question is whether there exist LTCs that have the ccc property: {c}onstant relative rate, {c}onstant relative distance, and that ... more >>>

TR10-107 | 6th July 2010
Irit Dinur, Or Meir

Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

A PCP is a proof system for NP in which the proof can be checked by a probabilistic verifier. The verifier is only allowed to read a very small portion of the proof, and in return is allowed to err with some bounded probability. The probability that the verifier accepts ... more >>>

TR09-042 | 5th May 2009
Irit Dinur, Prahladh Harsha

Composition of low-error 2-query PCPs using decodable PCPs

The main result of this paper is a simple, yet 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 ... more >>>

TR08-020 | 7th March 2008
Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

Decodability of Group Homomorphisms beyond the Johnson Bound

Given a pair of finite groups $G$ and $H$, the set of homomorphisms from $G$ to $H$ form an error-correcting code where codewords differ in at least $1/2$ the coordinates. We show that for every pair of {\em abelian} groups $G$ and $H$, the resulting code is (locally) list-decodable from ... more >>>

TR06-118 | 2nd September 2006
Irit Dinur, Madhu Sudan, Avi Wigderson

Robust Local Testability of Tensor Products of LDPC Codes

Given two binary linear codes R and C, their tensor product R \otimes C consists of all matrices with rows in R and columns in C. We analyze the "robustness" of the following test for this code (suggested by Ben-Sasson and Sudan~\cite{BenSasson-Sudan04}): Pick a random row (or column) and check ... more >>>

TR05-046 | 17th April 2005
Irit Dinur

The PCP theorem by gap amplification

Revisions: 1 , Comments: 3

Let C={c_1,...,c_n} be a set of constraints over a set of
variables. The {\em satisfiability-gap} of C is the smallest
fraction of unsatisfied constraints, ranging over all possible
assignments for the variables.

We prove a new combinatorial amplification lemma that doubles the
satisfiability-gap of a constraint-system, with only a linear ... more >>>

TR05-039 | 13th April 2005
Irit Dinur, Elchanan Mossel, Oded Regev

Conditional Hardness for Approximate Coloring

We study the approximate-coloring(q,Q) problem: Given a graph G, decide
whether \chi(G) \le q or \chi(G)\ge Q. We derive conditional
hardness for this problem for any constant 3\le q < Q. For q \ge
4, our result is based on Khot's 2-to-1 conjecture [Khot'02].
For q=3, we base our hardness ... more >>>

TR02-027 | 30th April 2002
Irit Dinur, Venkatesan Guruswami, Subhash Khot

Vertex Cover on k-Uniform Hypergraphs is Hard to Approximate within Factor (k-3-\epsilon)

Given a $k$-uniform hypergraph, the E$k$-Vertex-Cover problem is
to find a minimum subset of vertices that ``hits'' every edge. We
show that for every integer $k \geq 5$, E$k$-Vertex-Cover is
NP-hard to approximate within a factor of $(k-3-\epsilon)$, for
an arbitrarily small constant $\epsilon > 0$.

This almost matches the ... more >>>

TR01-104 | 17th December 2001
Irit Dinur, Shmuel Safra

The Importance of Being Biased

We show Minimum Vertex Cover NP-hard to approximate to within a factor
of 1.3606. This improves on the previously known factor of 7/6.

more >>>

TR99-016 | 25th April 1999
Irit Dinur

Approximating SVP_\infty to within Almost-Polynomial Factors is NP-hard

This paper shows SVP_\infty and CVP_\infty to be NP-hard to approximate
to within any factor up to $n^{1/\log\log n}$. This improves on the
best previous result \cite{ABSS} that showed quasi-NP-hardness for
smaller factors, namely $2^{\log^{1-\epsilon}n}$ for any constant
$\epsilon>0$. We show a direct reduction from SAT to these
problems, that ... more >>>

TR99-015 | 25th April 1999
Irit Dinur, S. Safra

On the hardness of approximating label cover

The label-cover problem was introduced in \cite{ABSS} and shown
there to be quasi-NP-hard to approximate to within a factor of
$2^{\log^{1-\delta}n}$ for any {\em constant} $\delta>0$. This
combinatorial graph problem has been utilized \cite{ABSS,GM,ABMP}
for showing hardness-of-approximation of numerous problems. We
present a direct combinatorial reduction from low
error-probability PCP ... more >>>

TR98-066 | 3rd November 1998
Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability

This paper strengthens the low-error PCP characterization of NP, coming
closer to the ultimate BGLR conjecture. Namely, we prove that witnesses for
membership in any NP language can be verified with a constant
number of accesses, and with an error probability exponentially
small in the ... more >>>

TR98-048 | 6th July 1998
Irit Dinur, Guy Kindler, Shmuel Safra

Approximating CVP to Within Almost Polynomial Factor is NP-Hard

This paper shows finding the closest vector in a lattice
to be NP-hard to approximate to within any factor up to
$2^{(\log{n})^{1-\epsilon}}$ where
$\epsilon = (\log\log{n})^{-\alpha}$
and $\alpha$ is any positive constant $<{1\over 2}$.

more >>>

ISSN 1433-8092 | Imprint