Dana Moshkovitz
  • Member for 11 years, 3 months
  • Last seen more than 6 years ago
Advice on good research practices
Accepted answer
104 votes

One thing I found useful is to allocate time and designate a space for doing specific research activities. When I was at Princeton U, I loved sitting at the Engineering library that is well lit, ...

View answer
Polynomial-time algorithms with huge exponent/constant
Accepted answer
44 votes

Algorithms based on the regularity lemma are good examples for polynomial-time algorithms with terrible constants (either in the exponent or as leading coefficients). The regularity lemma of ...

View answer
What are good references to understanding the proof of the PCP theorem?
37 votes

In 2008 Irit Dinur and I taught a course on PCP at Weizmann, including both the algebraic and the combinatorial proofs. Hand-written lecture notes are available for most classes: http://people.csail....

View answer
How to get a job
35 votes

By far, the most important thing is to do great research. Then, there is making people know you do great research. Here's what I think (the order matters): Know yourself. What do you like? What are ...

View answer
What kind of mathematical background is needed for complexity theory?
30 votes

The previous answers already listed the basic ones: probability theory, combinatorics, linear algebra, abstract algebra (finite fields, group theory, etc). I would add: Fourier analysis, see, e.g., ...

View answer
If P=NP, could we obtain proofs of Goldbach's Conjecture etc.?
Accepted answer
28 votes

Indeed! If P=NP, not only we can decide whether there exists a proof of length n for Goldbach's Conjecture (or any other mathematical statement), but we can also find it efficiently! Why? Because we ...

View answer
An extension of Chernoff bound
Accepted answer
27 votes

What you want is the generalized Chernoff bound, which only assumes $P(\bigwedge_{i\in S} X_{i}) \leq p^{|S|}$ for any subset S of variable indices. The latter follows from your assumption, since for $...

View answer
Rigour leading to insight
27 votes

Parallel repetition is a nice example from my area: A Brief explanation of parallel repetition. Suppose you have a two-prover proof system for a language $L$: Given input $x$, known to everyone, a ...

View answer
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
26 votes

I have an example from a work I co-authored with Noga Alon and Muli Safra a few years ago: Noga used algebraic topology fixed-point theorems to prove the "Necklace Splitting Theorem": if you have a ...

View answer
Advice on good research practices
23 votes

There is envisioning: describing to yourself in a detailed way what you are going to do, before you start doing it. It works extremely well when you have a complicated task ahead of you, like writing ...

View answer
Polynomial method for complexity results
20 votes

There is Zeev Dvir's result on the finite field Kakeya problem that was mentioned on this website before. Zeev used the polynomial method to lower bound the number of points in any set of points in F^...

View answer
Applications of TCS to classical mathematics?
20 votes

Invariance principles were motivated from hardness of approximation, but are useful analytic theorems. The principle: A low degree function, in which each of the variables has small influence, behaves ...

View answer
Reducing P vs. NP to SAT
Accepted answer
20 votes

The way to view testing a math statement (e.g., a resolution of P vs NP) as a question of the form "is formula .. satisfiable" is the following: Fix some axiom system. Given a string of length n, ...

View answer
How easy is it to switch the area of research in CS (going from M.Tech to PhD)?
19 votes

I recently served on the TCS grad admissions committee of MIT, and I can give you my angle on things: When I'm reading applications, what I'm looking for is excellent people who strongly want to ...

View answer
How practical is Automata Theory?
18 votes

As was explained in the other answers, automata theory is important conceptually as a simple computational model that we understand well, and regular expressions and automata have many real-life ...

View answer
Examples of hardness phase transitions
Accepted answer
18 votes

In standard worst-case approximation, there are many sharp thresholds as the approximation factor varies. For example, for 3LIN, satisfying as many given Boolean linear equations on 3 variables each, ...

View answer
Major unsolved problems in theoretical computer science?
18 votes

What about proving BPP is contained in NP? (Unconditionally; we already know that BPP=P assuming pretty reasonable complexity assumptions)

View answer
Hard gaps in maximum constraint satisfaction problems?
Accepted answer
18 votes

Prasad Raghavendra in the STOC'08 best paper proved a dichotomy conjecture for approximating Max-CSP assuming the Unique Games Conjecture. This is not how he presented it originally, but he did give ...

View answer
Inapproximability of set cover: can I assume m=poly(n)?
Accepted answer
17 votes

Yes, the number of sets m in a set-cover instance is polynomial in the number of elements. By the way -- the state of the art hardness results for Set-Cover are: With Noga Alon and Muli Safra, we ...

View answer
Open problems on the frontiers of TCS
17 votes

Some PCP open problems: The Sliding Scale Conjecture. In PCP we want the error of the verifier to be as small as possible. BGLR conjectured that the error can go all the way to $2^{-\Theta(r)}$ where ...

View answer
Using error-correcting codes in theory
17 votes

There is a HUGE number of applications of error correcting codes in theoretical computer science. A classic application [that I think wasn't mentioned above] is to the construction of randomness ...

View answer
Examples of "Unrelated" Mathematics Playing a Fundamental Role in TCS?
16 votes

There are plenty of uses of information theory in theoretical computer science: e.g., in proving lower bounds for locally decodeable codes (see Katz and Trevisan), in Raz's proof of the parallel ...

View answer
Worst case to average case reductions
15 votes

The Wikipedia entry that Peter linked to mentions a few important examples of problems that have worst-case to average case reductions, like the permanent. Shortest vector problem (as well as related ...

View answer
Paradigms for complexity analysis of algorithms
15 votes

There is amortized complexity -- why some operations can be costly in the worst-case, but if you consider many operations, the average cost per operation is good. A classic example is a data ...

View answer
From Extractors to Pseudorandom Generators?
Accepted answer
14 votes

Salil Vadhan wrote to me that the answer to my question is known, and PRGs are equivalent to extractors. Quoting him: "See Proposition 21 and the discussion following it in my survey http://people....

View answer
Degree reduction step in Dinur's proof of the PCP theorem
14 votes

It is essential to the construction to have an expander between the copies of a vertex (the "cloud" of the vertex). Otherwise, you won't be able to argue that the adversary assigning values to the ...

View answer
PCPs with imperfect completeness
Accepted answer
14 votes

Yes, PCPs with imperfect completeness have been studied before. The main motivation is that for some natural and interesting problems, finding whether there is a perfect solution is actually easy (...

View answer
Hardness of approximation without the PCP theorem
13 votes

There are examples from approximate counting. Approximately counting the number of satisfying assignments of an NP-relation can only be harder than deciding whether a satisfying assignment exists, so ...

View answer
TCS Research Frontier with Huge Practical and Industrial Impact on our Society
13 votes

There are many examples of theoretical research that had a big impact on society, e.g., the RSA cryptosystem, the algorithm behind Google search, the algorithmic ideas behind Akamai, etc. But the ...

View answer
Chernoff-type Inequality for pair-wise independent random variables
13 votes

If you have pairwise independence, then you can bound the variance of the sum, and thus get a concentration bound using Chebyshev's inequality.

View answer