Most Popular
1500 questions
22
votes
1 answer
Complexity of a matrix problem
The following problem recently appeared in my research. Being no expert on algorithmic questions I have Googled extensively in the search for suitable problems to reduce from. I don't see how 3SAT would work, and even though ZOE is similar in spirit…
M.B.
- 313
- 1
- 8
22
votes
5 answers
Easy problems with hard counting versions
Wikipedia provides examples of problems where the counting version is hard, whereas the decision version is easy. Some of these are counting perfect matchings, counting the number of solutions to $2$-SAT and number of topological sortings.
Are…
Turbo
- 12,812
- 1
- 19
- 68
22
votes
4 answers
Chaos and the $P{=}NP$ question
I am interested in learning connections between "chaos," or more broadly, dynamical systems, and
the $P{=}NP$ question.
Here is an example of the type of literature I am seeking:
Ercsey-Ravasz, Mária, and Zoltán Toroczkai. "Optimization hardness as…
Joseph O'Rourke
- 3,753
- 23
- 41
22
votes
0 answers
What is the power of general poly-size permutation branching programs?
Call $\mathsf{PPBP}$ the class of languages decided by poly-size families of permutation branching programs, which are layered branching programs (i.e., the ones defined here) whose transitions functions are permutations (without any restriction on…
Damiano Mazza
- 5,473
- 1
- 25
- 36
22
votes
1 answer
Problems in BQP but conjectured to be outside P
Wikipedia listed four problems that are in $BQP$ but conjectured to be outside $P$: Integer factorization; Discrete logarithm; Simulation of quantum systems; Computing the Jones polynomial at certain roots of unity.
Are there any other such…
Minkov
- 852
- 5
- 17
22
votes
2 answers
Can a fully homomorphic encryption be used for oblivious code execution?
After reading this answer a while ago, I took an interest in fully homomorphic encryption. After reading the introduction of Gentry's thesis, I started wondering if his encryption scheme could be used for oblivious code execution as defined in the…
Alex ten Brink
- 4,680
- 25
- 48
22
votes
1 answer
How much computational power fits into a cubic centimeter?
This question is a followup on the question about DNA algorithms asked by Aadita Mehra.
In comments there, Joe Fitzsimmons said, in part:
[T]he radius of the system must scale proportionately to the mass to avoid this. The computational power…
Aaron Sterling
- 6,994
- 6
- 42
- 74
22
votes
2 answers
Can the cost of GC be neglected when analyzing the running time of worst-case data structures specified in a garbage-collected programming language?
I just realized that I have been assuming the answer to my question is "yes" but I don't have a good reason. I imagine that maybe there is a garbage collector that provably introduces only $O(1)$ worst-case slowdown. Is there a definitive reference…
Maverick Woo
- 591
- 6
- 12
22
votes
1 answer
Classifying reversible gates
Post's lattice, described by Emil Post in 1941, is basically a complete inclusion diagram of sets of Boolean functions that are closed under composition: for example, the monotone functions, the linear functions over GF(2), and all functions. (Post…
Scott Aaronson
- 13,733
- 2
- 62
- 68
22
votes
3 answers
Complexity of intersection of regular languages as context-free grammars
Given regular expressions $R_1, \dots, R_n$, are there any non-trivial bounds on the size of the smallest context-free grammar for $R_1 \cap \cdots \cap R_n$?
Max
- 1,561
- 11
- 19
22
votes
1 answer
Binary multiplication and parity convolution
This question is about the relationship between normal multiplication of binary numbers and polynomial multiplication mod 2. To make the question concrete, I would ideally like to know if there is a better solution to the question from Knuth vol. 2,…
Simd
- 3,902
- 20
- 49
22
votes
2 answers
Multiplicative version of 3-SUM
What is known about the time complexity of the following problem, which we call 3-MUL?
Given a set $S$ of $n$ integers, are there elements $a,b,c\in S$ such that $ab=c$?
This problem is similar to the 3-SUM problem, which asks whether there are…
Markus Jalsenius
- 321
- 1
- 2
22
votes
1 answer
How to write the introduction of a research paper?
Apologies if this is too broad a question for this forum, but I'm interested in specific tactics and tips that researchers (in TCS) use to write the introduction of a research paper.
Madhav Jha
- 413
- 3
- 7
22
votes
2 answers
Why did Kolmogorov publish Karatsuba's algorithm?
Karatsuba's algorithm for fast multiplication was first published in A. Karatsuba and Yu. Ofman (1962), "Multiplication of Many-Digital Numbers by Automatic Computers", Proceedings of the USSR Academy of Sciences 145: 293–294.
According to Karatsuba…
Max
- 1,561
- 11
- 19
22
votes
1 answer
Alternate proofs of Immerman-Szelepcsenyi theorem
Immerman and Szelepcsenyi independently proved that $NL=coNL$. Using their technique of inductive counting, Borodin et al proved that $SAC^i$ is closed under complementation, for $i > 0$. Prior to Reingold's theorem ($SL=L$), Nisan and Ta-Shma…
Shiva Kintali
- 10,578
- 41
- 74