V Vinay
  • Member for 11 years, 4 months
  • Last seen more than 5 years ago
Advice on good research practices
67 votes

Manuel Blum has this extraordinary page on advice to a beginning Ph.D student. Read it slowly though, for there is much to absorb. Update: Let me add this piece of advice by Dijkstra, his Third ...

View answer
Why are mod_m gates interesting?
Accepted answer
39 votes

$ACC^0$ is a natural complexity class. 1) Barrington showed that computation over non-solvable monoids capture $NC^1$ while over solvable monoids capture $ACC^0$. 2) Recently, Hansen and Koucky ...

View answer
How practical is Automata Theory?
33 votes

One of the more practical manifestation of CS is Compiler Construction. In 1965, Knuth started the study of LR parsers. Quickly (in less than a decade), we had LALR parsers which are a subset of ...

View answer
Alan Turing's Contributions to Computer Science
27 votes

I did not know of these until recently. 1) The LU decomposition of a matrix is due to Turing! Considering how fundamental LU decomposition is, this is one contribution that deserves to be highlighted ...

View answer
Monotone arithmetic circuits
15 votes

Yes. We do know good lower bounds and we have known them for quite some time now. Jerrum and Snir proved an exponential lower bound over monotone arithmetic circuits for the permanent by 1980. ...

View answer
Machine characterization of $SAC^i$
Accepted answer
14 votes

Yes. Stack heights. $\mathsf{SAC^1} = \mathsf{NAuxPDA}(\log n, \log n)$, that is, with $O(\log n)$ space and $O(\log n)$ stack height; this implies $\log n$ configurations and therefore $\log^2(n)$ ...

View answer
CFG parsing using $o(n^2)$ space
Accepted answer
14 votes

The first half of this answer is nothing more than an efficient ($\log^4(n)$ to $\log^2(n)$) rephrasing of David's answer in complexity theoretic terms. Context free languages live in the complexity ...

View answer
Why are linear bounded automata not as popular as other automata?
Accepted answer
13 votes

With "appropriate" modifications we can turn these classes into complexity classes; Finite Automata into $NC^1$, CFL into LogCFL, and LBA into PSPACE. It should now be quite clear why we are ...

View answer
Does L have a definition in terms of circuits?
12 votes

Check out this paper of McKenzie, Reinhardt, Vinay. We use multiplex-select gates to characterize classes between $NC^1$ and $LOGCFL$, including $L$, $LOGDCFL$ etc. For example, $L = MWidth, Size(log,...

View answer
If you could rename dynamic programming...
11 votes

To go with divide-and-conquer, I would say splice-and-combine. I usually use both words, splice and combine while teaching/explaining DP; but not used splice-and-combine explicitly. Sometimes I have ...

View answer
Does there exist a complexity class such that the number of accepting paths is a prime number?
Accepted answer
10 votes

What you are looking for is likely Leaf Languages. Look at the output of each path of an NP machine and concatenate them into an exponentially long string. We can now talk of the machine accepting the ...

View answer
Improved lower bound on monotone circuit complexity of perfect matching?
10 votes

Eva Tardos proved that the gap is truly exponential by showing that there is a monotone boolean function that has poly size circuits but requires exponential size monotone circuits. Nothing better ...

View answer
Alternate proofs of Immerman-Szelepcsenyi theorem
Accepted answer
10 votes

Since we don't seem to have any answers, can I make a comment? Suppose we are given $n$ bits, $X=x_1,\cdots,x_n$ and we have to complement each bit to get $\neg x_1,\cdots, \neg x_n.$ The only ...

View answer
Dynamic programming and shortest path problem
9 votes

Shortest paths in DAGs are typically problems in NL and many times complete as well. A slightly "larger" class is LOGCFL (of course, we don't know if NL=?LOGCFL) where typical problems solvable with ...

View answer
Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?
8 votes

What you ask for should have bad consequences but I cannot think of any immediately. So I have only some pointers to what we know. Check out Viola's On the power of small depth computation The best ...

View answer
Proof of the pumping lemma for context-free languages using pushdown automata
7 votes

Yes it is possible. We could use the notion of surface configurations; they were introduced by Cook a long time back. With this it should be quite easy to get a version of pumping lemma out. As to ...

View answer
Human intelligence and algorithms
7 votes

Check out Luis Von Ahn at CMU. He is the original Captcha guy. You will find enough videos like this google techtalk on the subject of Human Computation.

View answer
Deterministic Parallel algorithm for perfect matching in general graphs?
7 votes

When an optimization problem is known to be hard, it is usual to look at their maximal versions. For example, whereas independent set is NP-Complete, the lex first maximal independent set, which is P-...

View answer
Papers to credit for spectral partitioning of graphs
6 votes

Some additional references I remember of that era: 1) Diaconis and Stroock, Geometric bounds for eigenvalues of Markov chains, The Annals of Applied Probability, 1991; but I remember getting my hands ...

View answer
Other applications of Karger-Stein branching amplification?
5 votes

@JeffE, Here is a paper that counts min weight cycles in a graph. As far as I remember, it was definitely inspired by Karger's technique/result and it was a fun proof. Hope this helps with the ...

View answer
Complexity of a certain leaf language with Prime & Composite number of accepting paths.
Accepted answer
5 votes

@Tayfun Pay, you are trying to get us to solve a problem for you! As it turns out, you only need to apply primality on the count of the number of accepting paths and this count requires polynomial ...

View answer
Why doesn't computer science follow biology more closely in computer design?
4 votes

1) An average human consumes 100 Watts of power, which is roughly the same order of magnitude as a desktop (mostly display). The brain consumes about 20% of this, which is about 20 Watts. Now, your ...

View answer