


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 sizen
circuits. Existing constructions had seed clogn
for a large c>1. Along the way, we beat the hybrid argument and show an
equivalence between pseudoentropy generators and locally list recoverable
codes. 
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. 
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 nonexpanding 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. 
Dana Moshkovitz, Michal Moshkovitz Entropy Samplers and Strong Generic Lower Bounds For
Space Bounded Learning, Consider the following simple, inefficient,
algorithms for learning: (1) minimize the number of examples by deducing all
possible conclusions from every example.
(2) minimize space by enumerating over all
possible hypotheses. In this and the previous paper we show that, for a wide
family of hypotheses classes, 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) 
Dana Moshkovitz, Michal Moshkovitz Mixing Implies Lower Bounds For Space Bounded
Learning, The
proceedings of the 30th Annual Conference on Learning Theory (COLT17)

Eden Chlamtáč, Pasin
Manurangsi, Dana Moshkovitz,
Aravindan Vijayaraghavan Approximation Algorithms for Label Cover and The
LogDensity Threshold, We design and analyze stateoftheart
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 ACMSIAM 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 TR14142
Lemma in the proof: Direct Product Testing With
Nearly Identical Sets, ECCC
TR14182 [paper] 
Ofer Grossman, Dana Moshkovitz Amplification and Derandomization
Without Slowdown, We show a method for decreasing the error probability
of randomized algorithms via a fun puzzle that we name “the biased coin
problem” (it’s about finding a biased coin in a pile of identical coins that
contains many biased coins by tossing coins as few times as possible). We also show a method for converting randomized
algorithms to deterministic nonuniform algorithms without asymptotic
increase in the runtime. The method requires a verifier that checks the
randomized algorithm while only looking at a sketch of the input. The
proceedings of the 57th Annual IEEE
Symposium on Foundations of
Computer Science (FOCS16) 
Dana Moshkovitz, Govind Ramnarayan, Henry Yuen A NoGo Theorem for
Derandomized Parallel Repetition: Beyond FeigeKilian, 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 stateoftheart approximation
algorithm for constraint satisfaction problem to large alphabet. [paper] 
Pasin
Manurangsi, Dana Moshkovitz Approximating Dense
Max 2CSPs, This paper gives
stateoftheart 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. 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. 
Dana Moshkovitz Low Degree Test
With Polynomially Small Error, We show a low
degree test that has very low error. Making the test randomnessefficient
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”, 
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 noncommunicating 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) 
Pasin
Manurangsi, Dana Moshkovitz Improved
Approximation Algorithms for Projection Games, We give
stateoftheart approximation algorithms for projection games (Label Cover) with
perfect completeness, which is the case relevant to hardness of
approximation. 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. 
Dana Moshkovitz The Projection
Games Conjecture and the NPHardness of lnnApproximating
SetCover, We show how to
deduce optimal inapproximability for SetCover
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 SetCover was a quantitatively weaker version of that conjecture. 
Noga Alon, Sanjeev Arora, Rajsekar Manokaran, Dana Moshkovitz,
Omri Weinstein, Inapproximability of Densest
kSubgraph From Average Case Hardness, There’s a huge gap
between the best approximation algorithms for Densest kSubgraph (polynomial
approximation) and the best hardness results (ruling out PTAS). We rule out
constant factor approximation for the densest ksubgraph problem assuming
averagecase hardness of the planted clique problem (alternatively, assuming
averagecase hardness of kAND). [paper] 
Dana Moshkovitz, We describe a stateoftheart construction of PCP. Most
details are omitted and the focus is on the main ideas. [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 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 junta testing (via rounding
algorithms). Our motivation for this paper was the vision that robust real
linear equation SIAM Journal on
Computing, 42(3), 752791, 2013 ECCC
TR10112 A previous version achieving hardness under the Unique Games
Conjecture: ECCC TR10053 
Dana Moshkovitz 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 SchwartzZippel Lemma. We give a
simple proof of it by reduction to the univariate case. 
Dana Moshkovitz, Ran Raz Optimal NPhardness
of approximation results rely on a PCP Theorem of a special form (hardness of
projection games/LabelCover). In this 139page paper we prove the first such
theorem with subconstant error and almost linear size, implying a sharp
phase transition for the inapproximability of
problems like Max3SAT, Max3LIN, and many others. 
Dana Moshkovitz, Ran Raz We prove the first PCP Theorem (constant number of queries)
with both subconstant error probability and almost linear proof size. Prior
to this work there were PCP Theorems with either subconstant error
probability or almost linear size. 
Dana Moshkovitz, Ran Raz We show the first low degree test that is both
randomnessefficient 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):140180, 2008 
Adi Akavia, Oded
Goldreich, Shafi Goldwasser, Dana Moshkovitz We give further evidence that the hardness of one way
functions cannot be proved via reductions to NPhard problems. If it could,
the polynomial hierarchy would have collapsed to its second level. 
Noga
Alon, In krestriction problems, one is given a set of tests on k
symbols, and the task is to find a small set of sizem 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 krestriction problems via the Necklace
Splitting Theorem in algebraic topology. We also give new applications, like
an improved NPhardness of approximating SetCover. The
ACM Transactions on Algorithms, 2(2):153177, 2006 