|
|
|
|
|
|
Joshua
Cook, Dana Moshkovitz Time and Space Efficient Deterministic Decoders, Time efficient decoding algorithms for error
correcting codes often require linear space. However, locally decodable codes
yield more efficient randomized decoders that run in almost linear
time and sub-linear space. In this work we focus on deterministic decoding. Gronemeier
showed that any non-adaptive deterministic decoder for a good code running in
almost linear time must use nearly linear space. In sharp contrast, we show
that typical locally correctable codes have time and space efficient deterministic
decoders via a new method for efficient derandomization. The new derandomization
method works when verifiable partial progress can be obtained from a very
small number of randomness strings. We show that this is the case for
decoding. The 57th Annual ACM
Symposium on Theory of Computing (STOC25) |
|
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman Online Condensing
of Unpredictable Sources via Random Walks, Consider a random
walk V0…Vn on a degree-D lossless expander on 2^m
vertices, where the walk is specified by instructions X1,…,Xn in [D] such that for most i and for most x1..xi-1
it holds that Xi|X1..Xi-1=x1…xi-1 has entropy. We prove that for n
sufficiently larger than m, for most i, the
vertex Vi is close to having min-entropy at least m-O(1).
In a previous work (STOC’23) we proved a similar result assuming the much
stronger premise that for all i and for all
x1..xi-1 it holds that Xi|X1..Xi-1=x1…xi-1 has
entropy. Then we could prove that for all sufficiently large i the vertex Vi is close to having min-entropy at least
m-O(1). Both results allow
us to condense and extract entropy from streams in an online fashion,
without knowing the length of the stream n, and in space proportional to the
output entropy as opposed to the length of the stream. The new result has
minimal assumptions and applies to general randomness sources. In particular, it
gives a new Chernoff bound for random walks on
lossless expanders (as opposed to expanders) where the probability for a
deviation from the expectation is exponentially small in en instead of e2n, where n is the
length of the walk and e is the deviation. |
|
Joshua
Cook, Dana Moshkovitz Explicit Time and Space Efficient Encoders Exist
Only with Random Access, We construct asymptotically good error correcting
codes with encoding algorithms that run in almost linear time and logarithmic
space. In contrast, we show that such encoders do not exist
if we only have sequential access to the message with sub-linear number of
heads. The Proceedings of the 39th Computational
Complexity Conference (CCC24) |
|
Geoffrey Mon, Dana Moshkovitz, Justin
Oh, Approximate
Locally Decodable Codes with Constant Query Complexity and Nearly Optimal Rate In an approximate locally decode code one wishes
to decode locally correctly most message indices (the decoder doesn’t
report whether the decoding failed or not). These codes are useful for
amplification of locally decodable codes and average case hardness. We give
constructions and lower bounds on such codes. The IEEE
International Symposium on Information Theory (ISIT24) |
|
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) |
|
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) |
|
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 (invited to special issue) |
|
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) |
|
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. |
|
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. The
proceedings of the 61st IEEE Symposium on Foundations of Computer Science (FOCS20) |
|
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 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. |
|
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) |
|
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)
|
|
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) |
|
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. |
|
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”, |
|
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) |
|
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. 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 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. |
|
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, We describe a state-of-the-art 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 dictator testing (via rounding
algorithms). Our motivation for this paper was the vision that robust real
linear equation SIAM Journal on
Computing, 42(3), 752-791, 2013 ECCC
TR10-112 A previous version achieving hardness under the Unique Games
Conjecture: ECCC TR10-053 |
|
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 Schwartz-Zippel Lemma. We give a
simple proof of it by reduction to the univariate case. |
|
Dana Moshkovitz, Ran Raz 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. |
|
Dana Moshkovitz, Ran Raz 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. |
|
Dana Moshkovitz, Ran Raz 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 |
|
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 NP-hard problems. If it could,
the polynomial hierarchy would have collapsed to its second level. |
|
Noga
Alon, 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 |