Most Popular
1500 questions
28
votes
10 answers
Probabilistic (randomized) algorithms before "modern" computer science appeared
Edit: I choice the answer with highest score by December 06, 2012.
This is a soft question.
The concept of (deterministic) algorithms dates back to BC. What about the probabilistic algorithms?
In this wiki entry, Rabin's algorithm for the closest…
Abuzer Yakaryilmaz
- 3,707
- 1
- 20
- 38
28
votes
4 answers
A lottery that you can be convinced that it is fair
(Sorry if this is well known.) I would like to give some item to one of $k$ agents, so that agent $j$ will get the item with probability $p_i$. Is there a cryptographic (or other) tool so that every agent (and even every observer) will be able to be…
Gil Kalai
- 6,033
- 35
- 73
28
votes
0 answers
Adiabatic quantum computing with level crossings
Question.
In adiabatic evolution, to ensure that the ground state high overlap with the unique ground state of the system (i.e. to achieve arbitrarily small error) using adiabatic theorems, it is crucial that there is always some measurable…
Niel de Beaudrap
- 8,821
- 31
- 70
27
votes
1 answer
Deciding if a given $\mathsf{NC}^0$ circuit computes a permutation
What is the complexity of deciding whether an $\mathsf{NC}^0$ circuit
with $n$ input bits and $n$ output bits computes a permutation
of $\{0,1\}^n$? in the other words, whether every bit strings in
$\{0,1\}^n$ is an output of the circuit for some…
QiCheng
- 443
- 3
- 5
27
votes
5 answers
Quantum proofs of classical theorems
I'm interested in examples of problems where a theorem which seemingly has nothing to do with quantum mechanics/information (e.g. states something about purely classical objects) can nevertheless be proved using quantum tools. A survey Quantum…
Marcin Kotowski
- 2,806
- 19
- 25
27
votes
4 answers
Quantum approximation algorithms
It is generally considered unlikely that quantum computers will be able to solve NP-complete problems efficiently. In the classical case one approach to tackle such problems is to use approximation algorithms. Has there been any research on…
Michal Kotowski
- 371
- 2
- 5
27
votes
3 answers
The complexity of determining if a fixed graph is a minor of another
The result by Robertson and Seymour demonstrates an $O(n^3)$ algorithm for testing whether a fixed graph $G$ is a minor of $H$. I have two and a half questions on this topic:
1) It appears that there have been improvements to this algorithm since.…
Timothy Sun
- 779
- 5
- 12
27
votes
5 answers
Long-lasting errors in computer science
This is my first question on the cstheory stack, so don't be too rude if I'm violating etiquette somehow )
As we know, in mathematics even famous mathematicians, superstars and geniuses are doing serious mistakes time to time. For example, both…
shabunc
- 121
- 1
- 6
27
votes
2 answers
I dreamt of a data structure, does it exist?
I haven't managed to find this data structure, but I'm not an expert in the field.
The structure implements a set, and is basically an array of comparable elements with an invariant. The invariant is the following (defined recursively):
An array of…
pbaren
- 653
- 5
- 9
27
votes
2 answers
Complexity of Topological Properties.
I am a computer scientist taking a course on Topology (a sprinkling of point-set topology heavily flavored with continuum theory). I have become interested in decision problems testing a description of a space (by simplices) for topological…
Ross Snider
- 2,035
- 2
- 20
- 33
27
votes
4 answers
What specific evidence is there for P = RP?
RP is the class of problems decidable by a nondeterministic Turing machine that terminates in polynomial time, but that is also allowed one-sided error. P is the usual class of problems decidable by a deterministic Turing machine that terminates in…
András Salamon
- 19,000
- 3
- 64
- 150
27
votes
1 answer
Good codes decodable by linear-sized circuits?
I'm looking for error-correcting codes of the following type:
binary codes with constant rate,
decodable from some constant fraction of errors, by a decoder implementable as a Boolean circuit of size $O(N)$, where $N$ is the encoding length.
Some…
Andy Drucker
- 4,634
- 23
- 33
27
votes
1 answer
Isometric embedding of L2 into L1
It is known that given an $n$-point subset of $\ell_2^d$ (that is, given $n$ points in ${\mathbb R}^d$ with Euclidean distance) it is possible to embed them isometrically in $\ell^{n\choose 2}_1$.
Is the isometry computable in (possibly,…
Luca Trevisan
- 4,912
- 28
- 34
27
votes
1 answer
How many multiplications are needed to compute the determinant of a 3×3 matrix?
In a comment on this question in 2016, Jeffrey Shallit remarked:
I've asked experts about this, and apparently it is not even currently known whether or not 9 multiplications are needed to compute the determinant of a 3x3 matrix.
I’m curious as to…
Robin Houston
- 761
- 4
- 10
27
votes
1 answer
Consequences of Complete problems for NP intersects coNP
What are the consequences of having complete problems in $NP\cap coNP$?
Marcos Villagra
- 3,290
- 27
- 45