|
|
|
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 (non-uniform) time and space efficient deterministic
decoders via a new method for efficient derandomization.
|
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. |
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 |