All reports by Author Dana Moshkovitz:

__
TR24-032
| 22nd February 2024
__

Joshua Cook, Dana Moshkovitz#### Explicit Time and Space Efficient Encoders Exist Only With Random Access

__
TR23-056
| 26th April 2023
__

Geoffrey Mon, Dana Moshkovitz, Justin Oh#### Approximate Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate

__
TR22-103
| 15th July 2022
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Almost Chor--Goldreich Sources and Adversarial Random Walks

Revisions: 2

__
TR22-014
| 8th February 2022
__

Joshua Cook, Dana Moshkovitz#### Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE

Revisions: 2

__
TR21-042
| 16th March 2021
__

Dana Moshkovitz#### Strong Parallel Repetition for Unique Games on Small Set Expanders

Revisions: 1
,
Comments: 1

__
TR20-093
| 23rd June 2020
__

Ronen Eldan, Dana Moshkovitz#### Reduction From Non-Unique Games To Boolean Unique Games

Revisions: 1

__
TR19-099
| 29th July 2019
__

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman#### Nearly Optimal Pseudorandomness From Hardness

Revisions: 3

__
TR18-078
| 23rd April 2018
__

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra#### Small Set Expansion in The Johnson Graph

__
TR17-116
| 5th July 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Strong Lower Bounds for Space Bounded Learning

__
TR17-017
| 5th February 2017
__

Michal Moshkovitz, Dana Moshkovitz#### Mixing Implies Lower Bounds for Space Bounded Learning

__
TR15-158
| 27th September 2015
__

Ofer Grossman, Dana Moshkovitz#### Amplification and Derandomization Without Slowdown

__
TR14-182
| 22nd December 2014
__

Dana Moshkovitz#### Direct Product Testing With Nearly Identical Sets

Comments: 1

__
TR14-142
| 1st November 2014
__

Subhash Khot, Dana Moshkovitz#### Candidate Lasserre Integrality Gap For Unique Games

__
TR14-054
| 16th April 2014
__

Dana Moshkovitz#### Parallel Repetition of Fortified Games

Revisions: 2

__
TR14-030
| 5th March 2014
__

Dana Moshkovitz#### An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing

__
TR14-012
| 27th January 2014
__

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz#### AM with Multiple Merlins

Revisions: 1

__
TR11-112
| 10th August 2011
__

Dana Moshkovitz#### The Projection Games Conjecture and The NP-Hardness of ln n-Approximating Set-Cover

__
TR10-112
| 15th July 2010
__

Subhash Khot, Dana Moshkovitz#### NP-Hardness of Approximately Solving Linear Equations Over Reals

__
TR10-096
| 16th June 2010
__

Dana Moshkovitz#### An Alternative Proof of The Schwartz-Zippel Lemma

Revisions: 1

__
TR10-053
| 28th March 2010
__

Dana Moshkovitz, Subhash Khot#### Hardness of Approximately Solving Linear Equations Over Reals

Comments: 1

__
TR08-071
| 6th August 2008
__

Dana Moshkovitz, Ran Raz#### Two Query PCP with Sub-Constant Error

__
TR07-026
| 21st November 2006
__

Dana Moshkovitz, Ran Raz#### Sub-Constant Error Probabilistically Checkable Proof of Almost Linear Size

__
TR05-086
| 14th August 2005
__

Dana Moshkovitz, Ran Raz#### Sub-Constant Error Low Degree Test of Almost Linear Size

Revisions: 1

Joshua Cook, Dana Moshkovitz

We give the first explicit constant rate, constant relative distance, linear codes with an encoder that runs in time $n^{1 + o(1)}$ and space $\mathop{polylog}(n)$ provided random access to the message. Prior to this work, the only such codes were non-explicit, for instance repeat accumulate codes [DJM98] and the codes ... more >>>

Geoffrey Mon, Dana Moshkovitz, Justin Oh

We present simple constructions of good approximate locally decodable codes (ALDCs) in the presence of a $\delta$-fraction of errors for $\delta<1/2$. In a standard locally decodable code $C \colon \Sigma_1^k \to \Sigma_2^n$, there is a decoder $M$ that on input $i \in [k]$ correctly outputs the $i$-th symbol of a ... more >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>

Joshua Cook, Dana Moshkovitz

We prove for some constant $a > 1$, for all $k \leq a$,

$$\mathbf{MATIME}[n^{k + o(1)}] / 1 \not \subset \mathbf{SIZE}[O(n^{k})],$$

for some specific $o(1)$ function. This improves on the Santhanam lower bound, which says there exists constant $c$ such that for all $k > 1$:

$$\mathbf{MATIME}[n^{c k}] / 1 ...
more >>>

Dana Moshkovitz

We show that NP-hardness of approximating Boolean unique games on small set expanders can be amplified to the full Unique Games Conjecture on small set expanders.

The latter conjecture is known to imply hardness results for problems like Balanced-Separator, Minimum-Linear-Rearrangement and Small-Set-Expansion that are not known under the Unique ...
more >>>

Ronen Eldan, Dana Moshkovitz

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap $1-\delta$ vs. $1-C\delta$, for any $C> 1$, and sufficiently small $\delta>0$) to the problem of proving a PCP Theorem for a certain non-unique game.

In a previous work, Khot and Moshkovitz suggested an inefficient candidate reduction (i.e., ...
more >>>

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Existing proofs that deduce $\mathbf{BPP}=\mathbf{P}$ from circuit lower bounds convert randomized algorithms into deterministic algorithms with a large polynomial slowdown. We convert randomized algorithms into deterministic ones with little slowdown. Specifically, assuming exponential lower bounds against nondeterministic circuits, we convert any randomized algorithm over inputs of length $n$ running in ... more >>>

Subhash Khot, Dor Minzer, Dana Moshkovitz, Muli Safra

This paper studies expansion properties of the (generalized) Johnson Graph. For natural numbers

t < l < k, the nodes of the graph are sets of size l in a universe of size k. Two sets are connected if

their intersection is of size t. The Johnson graph arises often ...
more >>>

Michal Moshkovitz, Dana Moshkovitz

With any hypothesis class one can associate a bipartite graph whose vertices are the hypotheses H on one side and all possible labeled examples X on the other side, and an hypothesis is connected to all the labeled examples that are consistent with it. We call this graph the hypotheses ... more >>>

Michal Moshkovitz, Dana Moshkovitz

One can learn any hypothesis class $H$ with $O(\log|H|)$ labeled examples. Alas, learning with so few examples requires saving the examples in memory, and this requires $|X|^{O(\log|H|)}$ memory states, where $X$ is the set of all labeled examples. A question that arises is how many labeled examples are needed in ... more >>>

Ofer Grossman, Dana Moshkovitz

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (non-uniform) algorithms. Unlike most existing techniques that involve repetition of the randomized algorithm, and hence a slowdown, our techniques produce algorithms with a similar run-time to the original randomized algorithms.

The ... more >>>

Dana Moshkovitz

In this work we analyze a direct product test in which each of two provers receives a subset of size n of a ground set U,

and the two subsets intersect in about (1-\delta)n elements.

We show that if each of the provers provides labels to the n ...
more >>>

Subhash Khot, Dana Moshkovitz

We propose a candidate Lasserre integrality gap construction for the Unique Games problem.

Our construction is based on a suggestion in [KM STOC'11] wherein the authors study the complexity of approximately solving a system of linear equations over reals and suggest it as an avenue towards a (positive) resolution ...
more >>>

Dana Moshkovitz

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game G^k in terms of the value of the game G and the number of repetitions k.

Contrary to what one might have guessed, the value of G^k is not val(G)^k, but rather a more complicated ...
more >>>

Dana Moshkovitz

The Sliding Scale Conjecture in PCP states that there are PCP verifiers with a constant number of queries and soundness error that is exponentially small in the randomness of the verifier and the length of the prover's answers.

The Sliding Scale Conjecture is one of the oldest open problems in ... more >>>

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

We introduce and study a new model of interactive proofs: AM(k), or Arthur-Merlin with k non-communicating Merlins. Unlike with the better-known MIP, here the assumption is that each Merlin receives an independent random challenge from Arthur. One motivation for this model (which we explore in detail) comes from the close ... more >>>

Dana Moshkovitz

In this paper we put forward a conjecture: an instantiation of the Sliding Scale Conjecture of Bellare, Goldwasser, Lund and Russell to projection games. We refer to this conjecture as the Projection Games Conjecture.

We further suggest the research agenda of establishing new hardness of approximation results based on the ... more >>>

Subhash Khot, Dana Moshkovitz

In this paper, we consider the problem of approximately solving a system of homogeneous linear equations over reals, where each

equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be ``non-trivial". Here is

an informal statement of our ...
more >>>

Dana Moshkovitz

We show a non-inductive proof of the Schwartz-Zippel lemma. The lemma bounds the number of zeros of a multivariate low degree polynomial over a finite field.

more >>>Dana Moshkovitz, Subhash Khot

In this paper, we consider the problem of approximately solving a

system of homogeneous linear equations over reals, where each

equation contains at most three variables.

Since the all-zero assignment always satisfies all the equations

exactly, we restrict the assignments to be ``non-trivial". Here is

an informal statement of our ...
more >>>

Dana Moshkovitz, Ran Raz

We show that the NP-Complete language 3Sat has a PCP

verifier that makes two queries to a proof of almost-linear size

and achieves sub-constant probability of error $o(1)$. The

verifier performs only projection tests, meaning that the answer

to the first query determines at most one accepting answer to the

more >>>

Dana Moshkovitz, Ran Raz

We show a construction of a PCP with both sub-constant error and

almost-linear size. Specifically, for some constant alpha in (0,1),

we construct a PCP verifier for checking satisfiability of

Boolean formulas that on input of size n uses log n + O((log

n)^{1-alpha}) random bits to query a constant ...
more >>>

Dana Moshkovitz, Ran Raz

Given a function f:F^m \rightarrow F over a finite

field F, a low degree tester tests its proximity to

an m-variate polynomial of total degree at most d

over F. The tester is usually given access to an oracle

A providing the supposed restrictions of f to

affine subspaces of ...
more >>>