Papers by Dana Moshkovitz

 

 

     

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Almost Chor-Goldreich Sources and Adversarial Random Walks,

Does a random walk on an expander mix when the randomness comes from a weak randomness source? It was folklore that the answer was “NO”, since an adversary who only controls every other step can keep the walk around its starting point. In this paper we show that if there’s a little bit of fresh randomness in each step the walk does mix. This is so, even though such a walk is no longer Markovian and standard spectral techniques fail to analyze it. Our analysis is based on the l1+e-norm and could be of independent interest. Randomness sources where each step contains a little fresh entropy (known as Santha-Vazirani/Chor-Goldreich sources) were the first sources considered in the extractor community back in the 1980’s. It was known that one cannot extract nearly uniform bits from them deterministically. Yet we show that one can extract from them bits with nearly full entropy deterministically! 

The proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC23)

ECCC TR22-103  

Joshua Cook, Dana Moshkovitz

Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE,

Santhanam proved the unconditional lower bound MA/1 Ë SIZE(nk) for any constant k. The lower bound uses the fact that the MA/1 verifier may run in polynomial time much larger than nk. We prove a tight lower bound MA/1(nk+o(1)) Ë SIZE(nk) for some constant k>1. For the proof we construct the first PCP for SPACE(n) where the verifier runs in ~O(n) time and makes O(logn) queries.

The proceedings of the 27th international conference on Randomization and Computation (RANDOM23)

ECCC TR22-014

Shuichi Hirahara, Dana Moshkovitz

Regularization of Low Error PCPs and an Application to MCSP,

We show how to regularize and minimize the degree of PCPs with low soundness error and an arbitrary number of queries. Previous transformations worked for large soundness error or projection (two queries).

Currently soundness error for PCP that is exponentially small in the randomness of the verifier is known only with a super-constant number queries.

Such a PCP is used in recent works on the hardness of the Minimum Circuit Size Problem, and regularization simplifies the proofs.   

ISAAC 2023

Ronen Eldan, Dana Moshkovitz

Reduction From Non-Unique Games To Boolean Unique Games,

We reduce the problem of proving a "Boolean Unique Games Conjecture" (with gap 1-d vs. 1-Cd, for any C>1, and sufficiently small d>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., without a proof of soundness). The current work is the first to provide an efficient reduction along with a proof of soundness. The non-unique game we reduce from is similar to non-unique games for which PCP theorems are known. Our proof relies on a new concentration theorem for functions in Gaussian space that are restricted to a random hyperplane. 

The proceedings of the 13th Innovations in Theoretical Computer Science conference (ITCS22)

ECCC TR20-093/arXiv:2006.13073 

Talk at the Simons Institute in Berkeley

Akhil Jalan, Dana Moshkovitz

Near-Optimal Cayley Expanders for Abelian Groups,

We generalize Ta-Shma’s eps-biased sets construction to all finite Abelian groups, giving explicit Cayley expanders nearly matching the random construction by Alon and Roichman.

41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS21)

arXiv:2105.01149Top of Form

Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Near Optimal Pseudorandomness From Hardness,

Starting with a hard function, we construct pseudorandom generators that use seed (1+e)logn to output n bits that look random to size-n circuits.

Existing constructions had seed clogn for a large c>1. This allows us to derandomize any randomized algorithm with minimal slowdown.

Along the way, we beat the hybrid argument and show a tight connection between pseudo-entropy generators and locally list recoverable codes.

Journal of the ACM, 2022

The proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS20)

ECCC TR19-099

Justin’s FOCS’20 talk. My TCS+ talk

Dana Moshkovitz

Sliding Scale Conjectures in PCP,

We still don’t have PCP theorems where the error is as low as we think it should be, and as a result, we can’t prove desirable hardness of approximation results. This survey is about what we have and where we’re stuck.

SIGACT Open Problems Column 2019

[Survey]

Dana Moshkovitz, Justin Oh, David Zuckerman

Randomness Efficient Noise Stability and Generalized Small Bias Sets,

We generalize epsilon biased sets to general product distributions and construct such with small support. This lets us define a randomness efficient version of the noise stability test.

FSTTCS 2020

Subhash Khot, Dor Minzer, Dana Moshkovitz, Shmuel Safra

Small Set Expansion in The Johnson Graph,

The Johnson graph is a slice of the Boolean hypercube (i.e., we focus only on strings of a fixed Hamming weight). In this paper we characterize the small non-expanding sets in this graph. The paper led to a similar characterization for the Grassmann graph and the resolution of the Two to Two Conjecture in PCP.

ECCC TR18-078

[presentation]

Dana Moshkovitz, Michal Moshkovitz

Entropy Samplers and Strong Generic Lower Bounds For Space Bounded Learning,

Consider the following simple (inefficient) algorithms for learning in the PAC model [where one wishes to learn a function h from random labelled examples (x,h(x))]: (1) minimize the number of examples by deducing all possible conclusions from every example. (2) minimize space by enumerating over the possible hypotheses, checking each example only against the current hypothesis. We show that, for a wide family of possible h’s, every algorithm that is more space efficient than (1) must use as many examples as (2).

The proceedings of the 9th Innovations in Theoretical Computer Science conference (ITCS18)

ECCC TR17-116

[presentation]

Dana Moshkovitz, Michal Moshkovitz

Mixing Implies Lower Bounds For Space Bounded Learning,

We develop a combinatorial framework for analyzing space bounded learning. 

The proceedings of the 30th Annual Conference on Learning Theory (COLT17)

ECCC TR17-017

Eden Chlamtáč, Pasin Manurangsi, Dana Moshkovitz, Aravindan Vijayaraghavan

Approximation Algorithms for Label Cover and The Log-Density Threshold,

We design and analyze state-of-the-art approximation algorithms for Label Cover (aka projection games), the problem that is the basis of known optimal inapproximability results.

The proceedings of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA17)

Subhash Khot, Dana Moshkovitz

Candidate Hard Unique Game,

We propose a construction of a Boolean unique game along with some evidence that it might be hard. Up to this work there were no proposals for possibly hard unique games (only works ruling out natural deterministic and randomized constructions).

The proceedings of the 48th Annual Symposium on the Theory of Computing (STOC16)

Preliminary version without analysis: ECCC TR14-142

Lemma in the proof: Direct Product Testing With Nearly Identical Sets, ECCC TR14-182

[paper]

Ofer Grossman, Dana Moshkovitz

Amplification and Derandomization Without Slowdown,

We show a method for decreasing the error probability of randomized algorithms without increasing the asymptotic run-time via a fun puzzle that we name “the biased coin problem” (it’s about finding a biased coin in a pile of identical coins, many of which are biased, by making as few coin tosses as possible).

We also show a method for converting randomized algorithms to deterministic non-uniform algorithms without asymptotic increase in the run-time. The method requires a verifier that checks the randomized algorithm while only looking at a sketch of the input.

SIAM Journal on Computing, 2020

The proceedings of the 57th Annual IEEE  Symposium  on Foundations of Computer Science (FOCS16)

ECCC TR15-158/ArXiv:1509.08123

[paper][presentation]

Dana Moshkovitz, Govind Ramnarayan, Henry Yuen

A No-Go Theorem for Derandomized Parallel Repetition: Beyond Feige-Kilian,

Counterintuitively, it seems that parallel repetition cannot be made randomness efficient. In 93 Feige and Kilian proved that for games with constant graph degree. This paper shows a different obstacle that applies even for games with large degree. 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (RANDOM16)

[paper]

Gil Goldshlager, Dana Moshkovitz

Approximating kCSP For Large Alphabet,

This paper was Gil’s undergrad project and it extends the state-of-the-art approximation algorithm for constraint satisfaction problem to large alphabet.

[paper]

Pasin Manurangsi, Dana Moshkovitz

Approximating Dense Max 2-CSPs,

This paper gives state-of-the-art approximation algorithms for constraint satisfaction problems on dense graphs.

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX15)

[paper]

Dana Moshkovitz

Parallel Repetition From Fortification,

The notoriously hard to analyze parallel repetition turns out to be easy to analyze and with better parameters than previously thought to be possible, as long as one makes a slight modification to the game (“fortification”) before repeating. This paper gives possibly the simplest known analysis for transforming a basic PCP Theorem to Label Cover form as needed for hardness of approximation.

The proceedings of the 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS14)

The latest version includes an extremely simple proof of parallel repetition and a correction to the fortification lemma.

[paper][presentation]

ECCC TR14-054

Dana Moshkovitz

Low Degree Test With Polynomially Small Error,

We show a low degree test that has very low error. Making the test randomness-efficient would prove the Sliding Scale Conjecture.

[paper]

Computational Complexity journal, 2016

(Previous version “An Approach To The Sliding Scale Conjecture Via Parallel Repetition For Low Degree Testing”,

ECCC TR14-30)

Sarah Eisenstat, Dana Moshkovitz, Robert E. Tarjan, Siyao Xu

Minimum Spanning Tree in Deterministic Linear Time For Graphs of High Girth,

Finding the minimum spanning tree of a graph in deterministic linear time is an outstanding open problem (there is a beautiful randomized algorithm).  This paper solves it in the case of graphs with high girth. It turned out that a previous paper implicitly had such an algorithm too.

[paper]

Scott Aaronson, Russell Impagliazzo, Dana Moshkovitz

AM with Multiple Merlins,

We define and explore the complexity class AM(k) in which there are k non-communicating provers. This paper introduced “birthday repetition” that found many uses since, most notably, proving the intractability of computing approximate Nash equilibrium.

Computational Complexity Conference (CCC14)

ECCC TR14-012

Pasin Manurangsi, Dana Moshkovitz

Improved Approximation Algorithms for Projection Games,

We give state-of-the-art approximation algorithms for projection games (Label Cover) with perfect completeness, which is the case relevant to hardness of approximation.

Algorithmica, 2015

ArXiv 1408.4048 (full version)

The Proceedings of the 21st European Symposium on Algorithms (ESA13)

Vitaly Abdrashitov, Muriel Médard, Dana Moshkovitz

Matched Filter Decoding of Random Binary and Gaussian Codes in Broadband Gaussian Channel,

We show that the random binary code is essentially as good as a Gaussian code in Gaussian channels.

IEEE International Symposium on Information Theory (ISIT13)

Dana Moshkovitz

The Projection Games Conjecture and the NP-Hardness of lnn-Approximating Set-Cover,

We show how to deduce optimal inapproximability for Set-Cover under an assumption about PCP. The assumption was proved after the publication of the paper. This paper explicitly defined “The Projection Games Conjecture” about the hardness of approximating projection games (aka Label Cover),

and the assumption needed for Set-Cover was a quantitatively weaker version of that conjecture.

Theory of Computing APPROX-RANDOM 2012 Special Issue

APPROX-RANDOM, 276-287, 2012

ECCC TR11-112

Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz, Omri Weinstein,

Inapproximability of Densest k-Subgraph From Average Case Hardness,

There’s a huge gap between the best approximation algorithms for Densest k-Subgraph (polynomial approximation) and the best hardness results (ruling out PTAS). We rule out constant factor approximation for the densest k-subgraph problem assuming average-case hardness of the planted clique problem (alternatively, assuming average-case hardness of kAND).

[paper]

Dana Moshkovitz,
Algebraic Construction of Projection PCPs
,

We describe a state-of-the-art construction of PCP. Most details are omitted and the focus is on the main ideas.
SIGACT Complexity Column 2012

[Survey]

Dana Moshkovitz,

The Tale of the PCP Theorem (popular article),

This is an article I wrote for the students’ magazine of the ACM. It assumes undergrad familiarity with computer science and surveys approximation algorithms and hardness of approximation, the PCP theorem and its proof, the Unique Games Conjecture and optimal inapproximability results.

ACM XRDS 2012

[Survey]

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

We show that the least mean squares algorithm is optimal for solving real linear equations, and we do so in the challenging case of finding a solution that is far from 0 for a homogeneous system of equations. Along the way, we develop robust real versions of linearity testing (via Hermite analysis) and dictator testing (via rounding algorithms). Our motivation for this paper was the vision that robust real linear equation problems would be the starting point for an eventual proof of the Unique Games Conjecture.

SIAM Journal on Computing, 42(3), 752-791, 2013
The Proceedings of the 43rd annual ACM symposium on Theory of computing (STOC11)

ECCC TR10-112
[paper][presentation]

A previous version achieving hardness under the Unique Games Conjecture: ECCC TR10-053 

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

A univariate polynomial of degree d has at most d roots. A multivariate polynomial of degree d over a finite field F has at most d/|F| fraction of roots. The latter is known as the incredibly useful Schwartz-Zippel Lemma. We give a simple proof of it by reduction to the univariate case.
ECCC TR10-096

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

Optimal NP-hardness of approximation results rely on a PCP Theorem of a special form (hardness of projection games/Label-Cover). In this 139-page paper we prove the first such theorem with sub-constant error and almost linear size, implying a sharp phase transition for the inapproximability of problems like Max-3SAT, Max-3LIN, and many others.
FOCS08 Best Paper award
The Journal of the ACM, 57(5), 2010
The Proceedings of The 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS08)
ECCC TR08-071

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

We prove the first PCP Theorem (constant number of queries) with both sub-constant error probability and almost linear proof size. Prior to this work there were PCP Theorems with either sub-constant error probability or almost linear size.
The Journal Computational Complexity, 19(3):367-422, 2010.
ECCC TR07-026
[full version] [IMU07 Presentation]

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

We show the first low degree test that is both randomness-efficient and has low error probability, resolving an open problem that stood for a few years prior. The challenge was to find a family of affine subspaces that, on one hand, was small and pseudorandom, and, on the other hand, was sufficiently dense in low dimensional spaces.

SIAM Journal on Computing, 38(1):140-180, 2008
The Proceedings of The 38th ACM Symposium on Theory of Computing (STOC06)
ECCC TR05-086
[conference version][full version] [STOC06 presentation] [IMU07 Presentation]

Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz
On Basing One-Way Functions on NP-Hardness
,

We give further evidence that the hardness of one way functions cannot be proved via reductions to NP-hard problems. If it could, the polynomial hierarchy would have collapsed to its second level.
The Proceedings of The 38th ACM Symposium on Theory of Computing (STOC06)
Erratum
[conference version]

Noga Alon, Dana Moshkovitz, Shmuel Safra
Algorithmic Construction of Sets for k-Restrictions, Overview

In k-restriction problems, one is given a set of tests on k symbols, and the task is to find a small set of size-m strings such that for every k positions, for every test, there is a string in the set that satisfies the test in those positions. This formalism captures problems like perfect hashing, group testing, color coding, set cover gadget, etc. We further develop a method for solving k-restriction problems via the Necklace Splitting Theorem in algebraic topology. We also give new applications, like an improved NP-hardness of approximating Set-Cover.

The ACM Transactions on Algorithms, 2(2):153-177, 2006
[full version] [presentation]