Dana Moshkovitz

STOC Conference 2025 Conference Paper

Time and Space Efficient Deterministic Decoders

• Joshua Cook
• Dana Moshkovitz

STOC Conference 2023 Conference Paper

Almost Chor-Goldreich Sources and Adversarial Random Walks

• Dean Doron
• Dana Moshkovitz
• Justin Oh
• David Zuckerman

A Chor–Goldreich (CG) source is a sequence of random variables X = X 1 ∘ … ∘ X t , where each X i ∼ {0,1} d and X i has δ d min-entropy conditioned on any fixing of X 1 ∘ … ∘ X i −1 . The parameter 0<δ≤ 1 is the entropy rate of the source. We typically think of d as constant and t as growing. We extend this notion in several ways, defining almost CG sources. Most notably, we allow each X i to only have conditional Shannon entropy δ d . We achieve pseudorandomness results for almost CG sources which were not known to hold even for standard CG sources, and even for the weaker model of Santha–Vazirani sources: We construct a deterministic condenser that on input X , outputs a distribution which is close to having constant entropy gap, namely a distribution Z ∼ {0,1} m for m ≈ δ dt with min-entropy m − O (1). Therefore, we can simulate any randomized algorithm with small failure probability using almost CG sources with no multiplicative slowdown. This result extends to randomized protocols as well, and any setting in which we cannot simply cycle over all seeds, and a “one-shot” simulation is needed. Moreover, our construction works in an online manner, since it is based on random walks on expanders. Our main technical contribution is a novel analysis of random walks, which should be of independent interest. We analyze walks with adversarially correlated steps, each step being entropy-deficient, on good enough lossless expanders. We prove that such walks (or certain interleaved walks on two expanders), starting from a fixed vertex and walking according to X 1 ∘ … ∘ X t , accumulate most of the entropy in X .

FOCS Conference 2020 Conference Paper

Nearly Optimal Pseudorandomness From Hardness

• Dean Doron
• Dana Moshkovitz
• Justin Oh
• David Zuckerman

Existing proofs that deduce BPP = 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 randomized single-valued nondeterministic (SVN) circuits, we convert any randomized algorithm over inputs of length n running in time t ≥ n to a deterministic one running in time t 2+α for an arbitrarily small constant. Such a slowdown is nearly optimal, as, under complexity-theoretic assumptions, there are problems with an inherent quadratic derandomization slowdown. We also convert any randomized algorithm that errs rarely into a deterministic algorithm having a similar running time (with pre-processing). The latter derandomization result holds under weaker assumptions, of exponential lower bounds against deterministic SVN circuits. Our results follow from a new, nearly optimal, explicit pseudorandom generator fooling circuits of size s with seed length (1 + α)log s, under the assumption that there exists a function f ϵ E that requires randomized SVN circuits of size at least 2 (1-α')n, where. α=O(α'). The construction uses, among other ideas, a new connection between pseudoentropy generators and locally list recoverable codes.

SODA Conference 2017 Conference Paper

Approximation Algorithms for Label Cover and The Log-Density Threshold

• Eden Chlamtac
• Pasin Manurangsi
• Dana Moshkovitz
• Aravindan Vijayaraghavan

Many known optimal NP-hardness of approximation results are reductions from a problem called Label Cover. The input is a bipartite graph G = ( L, R, E ) and each edge e = ( x, y ) ∊ E carries a projection π ∊ that maps labels to x to labels to y. The objective is to find a labeling of the vertices that satisfies as many of the projections as possible. It is believed that the best approximation ratio efficiently achievable for La bel -Co ver is of the form N −c where N = nk, n is the number of vertices, k is the number of labels, and 0 ≤ c < 1 is some constant. Inspired by a framework originally developed for Densest k -SuBGRAPH, we propose a “log density threshold” for the approximability of Label-Cover. Specifically, we suggest the possibility that the Label-Cover approximation problem undergoes a computational phase transition at the same threshold at which local algorithms for its random counterpart fail. This threshold is We then design, for any ∊ > 0, a polynomial-time approximation algorithm for semirandom Label-Cover whose approximation ratio is In our semi-random model, the input graph is random (or even just expanding), and the projections on the edges are arbitrary. For worst-case La bel -Co ver we show a polynomial- time algorithm whose approximation ratio is roughly Ν-°· 2 33. The previous best efficient approximation ratio was Ν −0 · 25. We present some evidence towards an Ν −c threshold by constructing integrality gaps for Ν ω(1) rounds of the Sum-of-squares/Lasserre hierarchy of the natural relaxation of Label Cover. For general 2CSP the “log density threshold” is Ν −0 · 25, and we give a polynomial-time algorithm in the semi-random model whose approximation ratio is Ν −0 · 25 + ∊ for any ∊ > 0.

FOCS Conference 2016 Conference Paper

Amplification and Derandomization without Slowdown

• Ofer Grossman
• Dana Moshkovitz

We present techniques for decreasing the error probability of randomized algorithms and for converting randomized algorithms to deterministic (nonuniform) 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 amplification technique is related to a certain stochastic multi-armed bandit problem. The derandomization technique - which is the main contribution of this work - points to an intriguing connection between derandomization and sketching/sparsification. We demonstrate the techniques by showing algorithms for approximating free games (constraint satisfaction problems on dense bipartite graphs).

STOC Conference 2016 Conference Paper

Candidate hard unique game

• Subhash Khot
• Dana Moshkovitz

We propose a candidate reduction for ruling out polynomial-time algorithms for unique games, either under plausible complexity assumptions, or unconditionally for Lasserre semi-definite programs with a constant number of rounds. We analyze the completeness and Lasserre solution of our construction, and provide a soundness analysis in a certain setting of interest. Addressing general settings is tightly connected to a question on Gaussian isoperimetry. Our construction is based on our previous work on the complexity of approximately solving a system of linear equations over reals, which we suggested as an avenue towards a (positive) resolution of the Unique Games Conjecture. The construction employs a new encoding scheme that we call the real code. The real code has two useful properties: like the long code, it has a unique local test, and like the Hadamard code, it has the so-called sub-code covering property.

FOCS Conference 2014 Conference Paper

Parallel Repetition from Fortification

• Dana Moshkovitz

The Parallel Repetition Theorem upper-bounds the value of a repeated (tensored) two prover game in terms of the value of the base game and the number of repetitions. In this work we give a simple transformation on games -- "fortification" -- and show that for fortified games, the value of the repeated game decreases perfectly exponentially with the number of repetitions, up to an arbitrarily small additive error. Our proof is combinatorial and short. As corollaries, we obtain: (1) Starting from a PCP Theorem with soundness error bounded away from 1, we get a PCP with arbitrarily small constant soundness error. In particular, starting with the combinatorial PCP of Dinur, we get a combinatorial PCP with low error. The latter can be used for hardness of approximation as in the work of Håstad. (2) Starting from the work of the author and Raz, we get a projection PCP theorem with the smallest soundness error known today. The theorem yields nearly a quadratic improvement in the size compared to previous work. We then discuss the problem of derandomizing parallel repetition, and the limitations of the fortification idea in this setting. We point out a connection between the problem of derandomizing parallel repetition and the problem of composition. This connection could shed light on the so-called Projection Games Conjecture, which asks for projection PCP with minimal error.

STOC Conference 2011 Conference Paper

NP-hardness of approximately solving linear equations over reals

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

STOC Conference 2010 Conference Paper

Erratum for: on basing one-way functions on NP-hardness

• Adi Akavia
• Oded Goldreich 0001
• Shafi Goldwasser
• Dana Moshkovitz

FOCS Conference 2008 Conference Paper

Two Query PCP with Sub-Constant Error

• Dana Moshkovitz
• Ran Raz

We show that the NP-Complete language 3Sat has a PCPverifier 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 second query. Previously, by the parallel repetition theorem, there were PCP Theorems with two-query projection tests, but only (arbitrarily small) constant error and polynomial size. There were also PCP Theorems with sub-constant error andalmost-linear size, but a constant number of queries that is larger than 2. As a corollary, we obtain a host of new results. In particular, our theorem improves many of the hardness of approximation results that are proved using the parallel repetition theorem. A partial list includes the following: (1) 3Sat cannot be efficiently approximated to withina factor of 7/8+o(1), unless P = NP. This holds even under almost-linear reductions. Previously, the best knownNP-hardness factor was 7/8+epsilon for any constant epsilonGt0, under polynomial reductions. (2) 3Lin cannot be efficiently approximated to withina factor of 1/2+o(1), unless P = NP. This holdseven under almost-linear reductions. Previously, the best known NP-hardness factor was 1/2+epsilon for any constant epsilonGt0, under polynomial reductions. (3) A PCP Theorem with amortized query complexity 1 + o(1)and amortized free bit complexity o(1). Previously, the best known amortized query complexity and free bit complexity were 1+epsilon and epsilon, respectively, for any constant epsilon Gt 0. One of the new ideas that we use is a new technique for doing the composition step in the (classical) proof of the PCP Theorem, without increasing the number of queries to the proof. We formalize this as a composition of new objects that we call Locally Decode/Reject Codes (LDRC). The notion of LDRC was implicit in several previous works, and we make it explicit in this work. We believe that the formulation of LDRCs and their construction are of independent interest.

STOC Conference 2006 Conference Paper

On basing one-way functions on NP-hardness

• Adi Akavia
• Oded Goldreich 0001
• Shafi Goldwasser
• Dana Moshkovitz

STOC Conference 2006 Conference Paper

Sub-constant error low degree test of almost-linear size

• Dana Moshkovitz
• Ran Raz

Given a function f:F m →F over a finite field F, a low degree tester tests its agreement with 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 constant dimension (e.g., lines, planes, etc.). The tester makes very few (probabilistic) queries to f and to A (say, one query to f and one query to A), and decides whether to accept or reject based on the replies.We wish to minimize two parameters of a tester: its error and its size . The error bounds the probability that the tester accepts although the function is far from a low degree polynomial. The size is the number of bits required to write the oracle replies on all possible tester's queries.Low degree testing is a central ingredient in most constructions of probabilistically checkable proofs (PCPs) and locally testable codes (LTCs). The error of the low degree tester is related to the soundness of the PCP and its size is related to the size of the PCP (or the length of the LTC).We design and analyze new low degree testers that have both sub-constant error o(1) and almost-linear size n 1+o(1) (where n=|F| m ). Previous constructions of sub-constant error testers had polynomial size [13, 16]. These testers enabled the construction of PCPs with sub-constant soundness , but polynomial size [13, 16, 9]. Previous constructions of almost-linear size testers obtained only constant error [13, 7]. These testers were used to construct almost-linear size LTCs and almost-linear size PCPs with constant soundness [13, 7, 5, 6, 8].