Most Popular
1500 questions
26
votes
2 answers
Current tightest bounds for critical 3-SAT density
I'm interested in the critical 3-satisfiability (3-SAT) density $\alpha$. It's conjectured that such $\alpha$ exists: if the number of randomly generated 3-SAT clauses is $(\alpha + \epsilon) n$ or more, they are almost surely unsatisfiable.
(Here…
Jun
- 361
- 2
- 4
26
votes
2 answers
Natural CLIQUE to k-Color reduction
There is clearly a reduction from CLIQUE to k-Color because they're both NP-Complete. In fact, I can construct one by composing a reduction from CLIQUE to 3-SAT with a reduction from 3-SAT to k-Color. What I'm wondering is whether there is a…
William Macrae
- 448
- 4
- 14
26
votes
1 answer
Complexity of matrix powering
Let $M$ be a square integer matrix, and let $n$ be a positive integer. I am interested in the complexity of the following decision problem:
Is the top-right entry of $M^n$ positive?
Note that the obvious approach of iterated squaring (or any other…
Joel
- 497
- 3
- 7
26
votes
1 answer
Interesting algorithms in the formalization of the Feit-Thompson theorem?
It looks like George Gonthier and his collaborators have finished formalizing the Odd Order Theorem.
In his earlier work on the Four Color Theorem, Gonthier invented a bunch of new algorithms (mostly variants of BDDs and graph algorithms) which…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
26
votes
1 answer
Unification and Gaussian Elimination
Does anyone knows of references that precisely spell out the connection between the unification algorithm and Gaussian elimination? I'm particularly interested in the relationship between triangular substitutions and LU decompositions.
Wayne Snyder…
Neel Krishnaswami
- 32,528
- 1
- 100
- 165
26
votes
2 answers
Exact number of comparisons to compute the median
Volume III of Knuth's The Art of Computer Programming (chapter 5, verse 3.2) includes the following table listing the exact minimum number of comparisons required to select the $t$th smallest element from an unsorted set of size $n$, for all $1\le t…
Jeffε
- 23,129
- 10
- 96
- 163
26
votes
1 answer
Who first proposed using $x^2+y^2 < 1$ Monte Carlo algorithm to calculate Pi?
I'm sure everybody knows of Buffon's needle experiment in the 18th century, that is one of the first probabilistic algorithms to calculate $\pi$.
The implementation of the algorithm in computers usually calls for the use of $\pi$, or a trigonometric…
Jérémie
- 638
- 4
- 12
26
votes
5 answers
Universal sets of gates for SU(3)?
In quantum computing we are often interested in cases where group of special unitary operators, G, for some d-dimensional system gives either the whole group SU(d) exactly or even just an approximation provided by a dense cover of SU(d).
A group…
Earl
26
votes
4 answers
How to find the cycles which, together, involve the biggest number of non-shared edges in a directed graph?
I am not a computer science theorist, but think this real world problem belongs here.
The problem
My company have several units accross the country.
We offered to employees the possibility to work on another unit. But there is a condition: The total…
motobói
- 363
- 2
- 8
25
votes
3 answers
Can we quantify the "degree of quantumness" in a quantum algorithm ?
Entanglement is often held up as the key ingredient that makes quantum algorithms well... quantum, and this can be traced back to the Bell states that destroy the idea of quantum physics as a hidden-state probabilistic model. In quantum information…
Suresh Venkat
- 32,071
- 4
- 95
- 271
25
votes
1 answer
Class of functions computable by Coq
Since it does not allow nonterminating computation, Coq is necessarily not Turing-complete. What is the class of functions that Coq can compute? (is there an interesting characterization thereof?)
Steve
- 251
- 2
- 3
25
votes
10 answers
For a language to be programmable, is it mandatory that it be based on a context free grammar
Practically, for a language that can eventually be compiled/transformed into system level instructions, is it necessary that it be a context free grammar?
ex: Are all programming/scripting languages context free grammars? Java is based on CFGs, but…
sandeepkunkunuru
- 361
- 3
- 7
25
votes
2 answers
Advice for attending my first TCS conference
I will be attending my first computer science conference and after reading the advice for how to improve conferences I noticed the several suggestions were about grad students attending their first conference.
What advice do you have for a grad…
Juan Besa
- 384
- 2
- 6
25
votes
4 answers
Arguments for existence of one-way functions
I have read in several papers that the existence of one-way functions is widely believed. Can someone shed light on why this is the case? What arguments do we have for supporting the existence of one-way functions?
Anonymous
- 4,041
- 19
- 43
25
votes
3 answers
Minimum Unsatisfiable 3-CNF Formulae
I am currently interested in obtaining (or constructing) and studying 3-CNF formulae which are unsatisfiable, and are of minimum size. That is, they must consist of as few clauses (m = 8 preferably) as possible, and as few distinct variables (n = 4…
MAF
- 259
- 3
- 5