Most Popular
1500 questions
18
votes
2 answers
Computation beyond unitary matrices
Just out of curiosity, if the classical computation is about permutation matrices and quantum computing is about unitary matrices (of which the permutation matrices are a subgroup), then will there be any computation paradigm beyond unitary…
huyichen
- 361
- 1
- 5
18
votes
1 answer
Using the extra power of the negative adversary method
The negative adversary method ($ADV^\pm$) is an SDP that characterizes quantum query complexity. It is a generalization of the widely used adversary method ($ADV$), and overcomes the two barriers that hindered the adversary method:
The property…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
18
votes
4 answers
Can testing show the absence of bugs?
$(n + 1)$ points are required to uniquely determine a polynomial of degree $n$; for instance, two points in a plane determine exactly one line.
How many points are required to uniquely determine a computable function $f : N \rightarrow N$, given the…
pbaren
- 653
- 5
- 9
18
votes
1 answer
Bitcoin and preventing double spending in decentralized digital currencies
A recent approach to creating a decentralized online currency, called Bitcoin, has been generating some interest. The goal is to have a way to transfer currency without a central authority and without double spending or counterfeiting. Their…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
18
votes
2 answers
Why is it so difficult for a computer to prove something?
This may be considered a stupid question. I am not a computer science major (and I'm not a mathematics major yet, either), so please excuse me if you think that the following questions display some major erroneous assumptions.
While there are plans…
Max Muller
- 647
- 1
- 6
- 9
18
votes
1 answer
Efficient concatenation of DFAs?
There is theoretical evidence that the naive cartesian-product construction for the intersection of DFAs is "the best we can do". What about the concatenation of two DFAs? The trivial construction involves converting each DFA into an NFA, adding an…
Aryeh
- 10,494
- 1
- 27
- 51
18
votes
1 answer
Cutting-sticks puzzle
Problem: We are given a set of sticks all having integer lengths. The total sum of their lengths is n(n+1)/2.
Can we break them up to get sticks of size ${1,2,\ldots,n}$ in polynomial time?
Surprisingly, the only reference I find for this problem…
Jagadish
- 1,955
- 21
- 27
18
votes
1 answer
Reading up on $BQP = BPP^{BQNC}$
What should I read to understand this problem?
The power of small-depth quantum
circuits. Is $BQP = BPP^{BQNC}$? In other
words, can the "quantum" part of any
quantum algorithm be compressed to
polylog(n) depth, provided we're
willing to…
Joshua Herman
- 1,661
- 17
- 38
18
votes
2 answers
Solving a Number-Hopper Maze
My 8-yr old has gotten bored creating conventional mazes, and has taken to creating variants that look like this:
The idea is to start from x and reach o via the normal rules. Additionally, you can "hop" from any integer $a$ to any other integer…
Fixee
- 1,003
- 8
- 15
18
votes
3 answers
What is the role of predicativity in inductive definitions in type theory?
We often want to define an object $A \in U$ according to some inference rules. Those rules denote a generating function $F$ which, when it is monotonic, yields a least fixed point $\mu F$. We take $A := \mu F$ to be the "inductive definition" of…
Scott Kilpatrick
- 185
- 6
18
votes
1 answer
What is the status of fuzzy logic for TCS in 2011?
I am reviewing the Handbook of Nature-Inspired and Innovative Computing for SIGACT News. It's a very interesting read. Each chapter, though, has the flavor, "This is my research area, and damn it's awesome!" So part of what I am trying to do is…
Aaron Sterling
- 6,994
- 6
- 42
- 74
18
votes
2 answers
Find a largest cube contained in the union of cuboids
I have a lot of cuboids in 3D space, each has a starting point at (x,y,z) and has size of (Lx,Ly,Lz). I wonder how to find a largest cube in this 3D space that is contained in the union of the cuboids. Is there an efficient algorithm for this?
For…
pantoffski
- 183
- 4
18
votes
2 answers
Why does it matter how difficult a proof is?
I am confused by how the objective worth of CS theory research is assessed.
In the last year, I had been working on formalizing some tasks from a different research field in cs theoretic terms, i.e. providing proper definitions, proving bounds etc.…
mto_19
- 291
- 1
- 5
18
votes
2 answers
Hierarchy theorem for circuit size
I think that a size hierarchy theorem for circuit complexity can be a major breakthrough in the area.
Is it an interesting approach to class separation?
The motivation for the question is that we have to say
there is some function that cannot be…
AntonioFa
- 445
- 4
- 8
18
votes
2 answers
Proof relevance vs. proof irrelevance
I want to use use Agda to help me write proofs, but I am getting contradictory feedback about the value of proof relevance.
Jacques Carette wrote a Proof-relevant Category Theory in Agda library. But some seem to think (perhaps here, but I was told…
Henry Story
- 585
- 2
- 13