Most Popular
1500 questions
26
votes
4 answers
Missing Wikipedia articles
Which missing TCS topics on Wikipedia would you most like there to be an article about?
They could be glaring omissions or just topics you think should really have an article.
One topic per answer please so that the most wanted ones can be voted…
WSSW
- 11
- 1
- 3
26
votes
5 answers
Recovering a parse forest from an Earley parser?
I was recently reading up on the Earley parser and think it's one of the most elegant algorithms I've seen to date. However, the algorithm in its traditional sense is a recognizer and not a parser, meaning that it can detect whether a string…
templatetypedef
- 2,242
- 17
- 26
26
votes
1 answer
Computational complexity of the 3-partition problem with distinct numbers
This question is related to an answer I posted in response to another question.
The 3-partition problem is the following problem:
Instance: Positive integers a1, …, an, where n=3m and the sum of the n integers is equal to mB, such that each ai…
Tsuyoshi Ito
- 16,466
- 2
- 55
- 106
26
votes
1 answer
Are types propositions? (What are types exactly?)
I've been reading a lot on type systems and such and I understand roughly why they were introduced (in order to resolve Russel's paradox). I also understand roughly their practical relevance in programming languages and proof systems. However, I'm…
Rehno Lindeque
- 677
- 4
- 13
26
votes
5 answers
What is the difference between proofs and programs (or between propositions and types)?
Given that the Curry-Howard Correspondence is so widely spread/extended, is there any difference between proofs and programs (or between propositions and types)? Can we really identify them?
day
- 2,795
- 1
- 20
- 27
26
votes
5 answers
Is there any connection between the diamond norm and the distance of the associated states?
In quantum information theory, the distance between two quantum channels is often measured using the diamond norm. There are also a number of ways to measure distance between two quantum states, such as the trace distance, fidelity, etc. The…
Joe Fitzsimons
- 13,675
- 47
- 91
26
votes
1 answer
Is BPP vs. P a real problem after we know BPP lies in P/poly?
We know (for now about 40 years, thank Adleman, Bennet and Gill) that the inclusion BPP $\subseteq$ P/poly, and an even stronger BPP/poly $\subseteq$ P/poly hold.
The "/poly" means that we work non-uniformly (a separate circuit for each input…
Stasys
- 6,765
- 29
- 54
26
votes
0 answers
Rank mod 6 vs rank over the reals
Let $A$ be a boolean matrix (eg with $0,1$ entries). Assume that $A$ has rank $\le r$ both over $\mathbb{F}_2$ and over $\mathbb{F}_3$. Does this imply that $A$ has low rank over the reals? This seems highly unlikely to me, but I cannot find a…
Shachar Lovett
- 756
- 6
- 7
26
votes
1 answer
Approximately sampling from convex polyhedrons with quantum computers
Quantum computers are very good for sampling distributions that we don't know how to sample using classical computers. For example if $f$ is a Boolean function (from $\{-1,1\}^n$ to $\{-1,1\}$) that can be computed in polynomial time then with…
Gil Kalai
- 6,033
- 35
- 73
26
votes
2 answers
What is the complexity of distinguishing a true Fourier spectra from a fake one?
A $PH$ machine is given oracle access to a random Boolean function $f:\{0,1\}^n \to \{ -1,1 \}$ , and two Fourier spectra $g$ and $h$.
The Fourier spectra of a function $f$ is defined as $F:\{0,1\}^n \to R$:
$F(s)=\sum_{x\in\{0,1\}^n} (-1)^\left(…
Mirmojtaba Gharibi
- 361
- 2
- 4
26
votes
4 answers
What's the "smallest" complexity class for which a superlinear circuit bound is known?
Apologies for asking a question that must surely be in a lot of standard references. I'm curious about exactly the question in the title, in particular I am thinking of Boolean circuits, no depth bound. I put "smallest" in quotes to allow for the…
matt hastings
- 969
- 5
- 15
26
votes
2 answers
Complexity zoo for unary languages
Of course, some complexity results may collapse for unary languages but I wonder
if there is somewhere a survey summarizing the known results in this case: a kind of
complexity zoo for unary languages. Would you know of such a reference ?
J.-E. Pin
- 4,831
- 26
- 42
26
votes
1 answer
How does the BosonSampling paper avoid easy classes of complex matrices?
In The computational complexity of linear optics (ECCC TR10-170), Scott Aaronson and Alex Arkhipov argue that if quantum computers can be efficiently simulated by classical computers then the polynomial hierarchy collapses to the third level. The…
András Salamon
- 19,000
- 3
- 64
- 150
26
votes
4 answers
Is there a non Turing-complete model of computation whose halting problem is undecidable?
I cannot think of any such model, maybe some form of typed lambda calculus? some elementary cellular automaton?
This would almost disprove Wolfram's "Principle of Computational Equivalence":
Almost all processes that are not obviously simple can be…
didest
- 1,551
- 16
- 25
26
votes
2 answers
Context Sensitive Grammars and Types
1) What, if any, is the relationship between static typing and formal grammars?
2) In particular, would it be possible for a linear bounded automaton to check whether, say, a C++ or SML program was well typed? A nested stack automaton?
3) Is there a…
Diogenes Creosote
- 363
- 2
- 7