didest
  • Member for 11 years, 5 months
  • Last seen more than a month ago
  • Argentina
Major unsolved problems in theoretical computer science?
75 votes

P = BPP?

View answer
What videos should everybody watch?
32 votes

Don Knuth's musings are great, always describing some amazing thing unknown to me before.

View answer
Algorithms from the Book.
22 votes

Knuth's Algorithm X finds all solutions to the exact cover problem. What is so magical about it is the technique he proposed to efficiently implement it: Dancing Links.

View answer
Algorithms from the Book.
21 votes

I think we must include Schieber-Vishkin's, which answers lowest common ancestor queries in constant time, preprocessing the forest in linear time. I like Knuth's exposition in Volume 4 Fascicle 1, ...

View answer
How did Knuth derive A?
Accepted answer
20 votes

See exercise 9 of section 6.4 of The Art of Computer Programming. Any irrational $A$ would work, because $\{kA\}$ breaks up a largest gap of $\{A\}, \{2A\}, \ldots, \{(k-1)A\}$ (I use the notation $\{...

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

A good example is Barrington's theorem: If a boolean function $f$ is computable by a circuit of depth $d$, then $f$ is computable by a branching program of width 5 and length $4^d$. The ...

View answer
Algorithms from the Book.
12 votes

We cannot forget Binary Decision Diagrams, a family of data structures that have become the method for representing boolean functions. I think the key insight is the dual nature of being a data ...

View answer
Is there an efficient algorithm to find the i-th dearrangement?
9 votes

Actually this is might be good question but it is badly formulated in its current form. The well-known algorithms for generating random derangements have linear expected time, but maybe it's an open ...

View answer
Can testing show the absence of bugs?
9 votes

(This was meant as a comment, but went long). Very interesting question. If you are willing to think about other complexity measures besides Kolmogorov's, then there are some answers in Learning ...

View answer
Is it possible to encrypt a CNF?
8 votes

The application you mention is called "proof of useful work" in the literature, see for instance this article. You can use a fully homomorphic encryption scheme (where the plaintext is the CNF ...

View answer
NP-hardness of a graph partition problem?
Accepted answer
7 votes

I've found that this problem is NP-hard, even restricted to trees. The reference is Graham and Robinson, "Isomorphic factorizations IX: even trees", but I couldn't get it.

View answer
Which algorithms are used most often in practice?
7 votes

I think the most used algorithm is Parity Check (or maybe CRC or some kind of error-correcting code), because they appear in every RAM access.

View answer
Algorithms from the Book.
7 votes

Knuth-Bendix algorithm and the analogous Buchberger's algorithm.

View answer
Funny TCS-related papers etc?
6 votes

How much damage could be caused by a peer reviewer having a bad day? Hilarious fictional reviews of famous old CS papers.

View answer
Definition of matrix-multiplication exponent $\omega$
6 votes

It is well-known the result of Coppersmith and Winograd that $O(n^{\omega})$-time cannot be realized by any single algorithm. But I've read that they restricted to algorithms based on Strassen-like ...

View answer
Algorithms from the Book.
6 votes

I think that LR parsers are beautiful. A language is deterministic context-free if and only if there exists a LR(1) grammar for it.

View answer
Amplitude of Random Cubic Graphs
5 votes

Peter Shor's answer is really good, but there is another way to answer this: proving that treewidth is upper bounded by two times the amplitude (the vertex version). Since we know that 3-regular ...

View answer
Funny TCS-related papers etc?
3 votes

The winner of the 2007 Aaronson/Gasarch Complexity Theme Song Contest is amazing! Download the mp3 and its lyrics.

View answer
Hard problems on subclasses of planar cubic bipartite graphs
3 votes

Cubic Montone Planar 1-in-3 SAT: 1-in-3 SAT without negated variables and where each variable is in exactly 3 clauses, and the incidence graph (the bipartite graph where the variables and the clauses ...

View answer
Optimally listing of subsets
2 votes

Although mikero proved that your problem is hard, there is a fast general algorithm that gives reasonably good solutions to this kind of problem (where you want an ordering of a set of "objects" such ...

View answer
How to compute ROOK Polynomials for NxM Matrices
Accepted answer
2 votes

See the answers of this question. Your case is a lot easier, just choose $k$ of the $m$ columns and then you have $n (n-1)\ldots (n-k+1)$ ways to put the $k$ rooks. So the coefficient of $x^k$ is $\...

View answer
Reductions from the book.
2 votes

EXACT COVER BY 3-SETS to SUBSET SUM EXACT COVER BY 3-SETS: given $U=\{1,2,\ldots,3m\}$ and $S_1,\ldots,S_n$ 3-subsets of $U$, are there $m$ disjoint sets that cover $U$? SUBSET SUM: given integers $...

View answer
Approximations for the Stable Fixtures Problem
Accepted answer
1 votes

Your problem is called maximum weighted simple b-matching, and it's solvable in strongly polynomial time. See this paper for instance.

View answer