All reports by Author Irit Dinur:

__
TR18-136
| 1st August 2018
__

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma#### List Decoding with Double Samplers

__
TR18-093
| 10th May 2018
__

Irit Dinur, Pasin Manurangsi#### ETH-Hardness of Approximating 2-CSPs and Directed Steiner Network

__
TR18-075
| 23rd April 2018
__

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha#### Boolean function analysis on high-dimensional expanders

Revisions: 1

__
TR18-050
| 15th March 2018
__

Irit Dinur, Oded Goldreich, Tom Gur#### Every set in P is strongly testable under a suitable encoding

__
TR17-181
| 26th November 2017
__

Irit Dinur, Yuval Filmus, Prahladh Harsha#### Agreement tests on graphs and hypergraphs

__
TR17-180
| 26th November 2017
__

Irit Dinur, Yuval Filmus, Prahladh Harsha#### Low degree almost Boolean functions are sparse juntas

__
TR17-096
| 30th May 2017
__

Irit Dinur, Inbal Livni Navon#### Exponentially Small Soundness for the Direct Product Z-test

__
TR17-094
| 25th May 2017
__

Irit Dinur, Subhash Khot, Guy Kindler, Dor Minzer, Muli Safra#### On Non-Optimally Expanding Sets in Grassmann Graphs

__
TR17-089
| 11th May 2017
__

Irit Dinur, Tali Kaufman#### High dimensional expanders imply agreement expanders

__
TR16-205
| 22nd December 2016
__

Amey Bhangale, Irit Dinur, Inbal Livni Navon#### Cube vs. Cube Low Degree Test

__
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?

__
TR16-160
| 26th October 2016
__

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen#### Multiplayer parallel repetition for expander games

Revisions: 1

__
TR16-128
| 13th August 2016
__

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

__
TR16-035
| 11th March 2016
__

Irit Dinur, Or Meir#### Toward the KRW Composition Conjecture: Cubic Formula Lower Bounds via Communication Complexity

Revisions: 2

__
TR15-085
| 23rd May 2015
__

Irit Dinur, Prahladh Harsha, Guy Kindler#### Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition

__
TR14-083
| 19th June 2014
__

Irit Dinur, Shafi Goldwasser, Huijia Lin#### The Computational Benefit of Correlated Instances

__
TR14-002
| 8th January 2014
__

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar#### Direct Sum Testing

Revisions: 1

__
TR13-179
| 15th December 2013
__

Irit Dinur, David Steurer#### Direct Product Testing

__
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

__
TR13-122
| 5th September 2013
__

Irit Dinur, Venkatesan Guruswami#### PCPs via low-degree long code and hardness for constrained hypergraph coloring

Revisions: 1

__
TR13-031
| 22nd February 2013
__

Irit Dinur, Elazar Goldenberg#### Clustering in the Boolean Hypercube in a List Decoding Regime

Revisions: 2

__
TR12-088
| 7th July 2012
__

Irit Dinur, Gillat Kol#### Covering CSPs

__
TR11-055
| 14th April 2011
__

Irit Dinur, Tali Kaufman#### Dense locally testable codes cannot have constant rate and distance

__
TR10-107
| 6th July 2010
__

Irit Dinur, Or Meir#### Derandomized Parallel Repetition via Structured PCPs

Revisions: 3

__
TR09-042
| 5th May 2009
__

Irit Dinur, Prahladh Harsha#### Composition of low-error 2-query PCPs using decodable PCPs

__
TR08-020
| 7th March 2008
__

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan#### Decodability of Group Homomorphisms beyond the Johnson Bound

__
TR06-118
| 2nd September 2006
__

Irit Dinur, Madhu Sudan, Avi Wigderson#### Robust Local Testability of Tensor Products of LDPC Codes

__
TR05-046
| 17th April 2005
__

Irit Dinur#### The PCP theorem by gap amplification

Revisions: 1
,
Comments: 3

__
TR05-039
| 13th April 2005
__

Irit Dinur, Elchanan Mossel, Oded Regev#### Conditional Hardness for Approximate Coloring

__
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)

__
TR01-104
| 17th December 2001
__

Irit Dinur, Shmuel Safra#### The Importance of Being Biased

__
TR99-016
| 25th April 1999
__

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

__
TR99-015
| 25th April 1999
__

Irit Dinur, S. Safra#### On the hardness of approximating label cover

__
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

__
TR98-048
| 6th July 1998
__

Irit Dinur, Guy Kindler, Shmuel Safra#### Approximating CVP to Within Almost Polynomial Factor is NP-Hard

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 [Proc. 58th FOCS, 2017], 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 ... more >>>

Irit Dinur, Pasin Manurangsi

We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph $G = (V, E)$, an alphabet set $\Sigma$ and, for each edge $\{u, v\} \in E$, a constraint $C_{uv} \subseteq \Sigma \times \Sigma$, the goal is to find an assignment $\sigma: V ... more >>>

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

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

Irit Dinur, Oded Goldreich, Tom Gur

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

Irit Dinur, Yuval Filmus, Prahladh Harsha

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

Irit Dinur, Yuval Filmus, Prahladh Harsha

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

Irit Dinur, Inbal Livni Navon

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

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

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

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

Amey Bhangale, Irit Dinur, Inbal Livni Navon

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

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

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.

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

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

Irit Dinur

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

Irit Dinur, Or Meir

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

Irit Dinur, Prahladh Harsha, Guy Kindler

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

Irit Dinur, Shafi Goldwasser, Huijia Lin

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

Roee David, Irit Dinur, Elazar Goldenberg, Guy Kindler, Igor Shinkar

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

Irit Dinur, David Steurer

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

Irit Dinur, Igor Shinkar

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

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

Irit Dinur, Elazar Goldenberg

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

Irit Dinur, Gillat Kol

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

Irit Dinur, Tali Kaufman

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

Irit Dinur, Or Meir

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

Irit Dinur, Prahladh Harsha

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

Irit Dinur, Elena Grigorescu, Swastik Kopparty, Madhu Sudan

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

Irit Dinur, Madhu Sudan, Avi Wigderson

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

Irit Dinur

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

Irit Dinur, Elchanan Mossel, Oded Regev

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

Irit Dinur, Venkatesan Guruswami, Subhash Khot

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

Irit Dinur, Shmuel Safra

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.

Irit Dinur

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

Irit Dinur, S. Safra

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

Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra

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

Irit Dinur, Guy Kindler, Shmuel Safra

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}$.