Dana Moshkovitz
• Member for 11 years, 4 months
• Last seen more than 6 years ago
• Cambridge, MA

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, ...

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 ...

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....

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 ...

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., ...

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 ...

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 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 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 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 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 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 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 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 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 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 18 votes What about proving BPP is contained in NP? (Unconditionally; we already know that BPP=P assuming pretty reasonable complexity assumptions) View answer 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 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 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 ...

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 ...

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 ...

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 ...

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 ...

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....

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 ...

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 (...

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 ...