Most Popular
1500 questions
16
votes
3 answers
Circuit complexity of Majority function
Let $f: \{0,1\}^n \to \{0,1\}$ be the majority function, i.e. $f(x) = 1$ if and only if $\sum_{i = 1}^n x_i > n/2$. I was wondering if there was a simple proof of the following fact (by "simple" I mean not relying on the probabilistic method like…
matthon
- 679
- 4
- 11
16
votes
2 answers
Complexity of counting the number of edge covers of a graph
An edge cover is a subset of edges of a graph such that every vertex of the graph is adjacent to at least one edge of the cover. The following two papers say that counting edge covers is #P-complete: A Simple FPTAS for Counting Edge Covers and…
a3nm
- 9,269
- 27
- 86
16
votes
1 answer
Gowers "discretized Borel determinacy" approach
Gowers has recently outlined a problem, which he calls "discretized Borel determinacy," whose solution is related to proving circuit lower bounds.
Can you provide a summary of the approach that is tailored to an audience of complexity…
Manu
- 7,659
- 3
- 37
- 42
16
votes
4 answers
Teaching high school TCS - existing programs
I was offered to teach a novel TCS high school program, which requires constructing a curriculum. I would very much like to hear opinions and suggestions regarding this.
First, does anyone know of high schools where a TCS program has been taught…
Shaull
- 5,571
- 1
- 22
- 32
16
votes
1 answer
Compared growth of the number of syntactic classes and Nerode classes.
For a language L ⊆ Σ^*, define the syntactic congruence ≡ of L as the least congruence on Σ^* that saturates L, i.e. :
u ≡ v ⇔ (∀ x, y)[xuy ∈ L ↔ xvy ∈ L].
Now define the Nerode equivalence as the following right congruence :
u ∼ v ⇔ (∀ x)[ux ∈ L ↔…
Michaël Cadilhac
- 3,946
- 22
- 39
16
votes
3 answers
Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?
I'm seeking an efficient algorithm for the problem:
Input: The positive integer $3^n$ (stored as bits) for some integer $n \geq 0$.
Output: The number $n$.
Question: Can we compute $n$ from the bits of $3^n$ in $O(n)$ time?
This is a theoretical…
Rebecca J. Stones
- 277
- 1
- 6
16
votes
0 answers
What is the fastest deterministic algorithm for incremental DAG reachability?
As the title. The incremental algorithm maintains the reachability information of a DAG when it undergoes a series of edge insertions (but no deletions). And the algorithm supports constant query (if node u reaches node v) time.
It takes amortized…
wei wang
- 519
- 2
- 7
16
votes
1 answer
Counterexample for Corneil's efficient algorithm for Graph Isomorphism
In the paper An Efficient Algorithm for Graph Isomorphism by Corneil and Gotlieb, 1970 a conjecture was stated upon which the stated algorithm relied for solving GI in polynomial time. Namely:
that the representative graphs exhibit the automorphism…
John D.
- 568
- 3
- 12
16
votes
2 answers
About generalized planar graphs and generalized outerplanar graphs
Any planar, respectively, outerplanar graph $G=(V,E)$ satisfies $|E'|\le 3|V'|-6$,
respectively, $|E'|\le 2|V'|-3$, for every subgraph $G'=(V',E')$ of $G$.
Also, (outer-)planar graphs can be recognized in polynomial time.
What is known about graphs…
Tobias Müller
- 332
- 2
- 8
16
votes
1 answer
Are there variants of visibly pushdown automata that allow pushing of words onto the stack?
I'm wondering, are there any papers or research dealing with visibly pushdown automata, but allowing words, rather than single letters, to be pushed onto the stack.
Alternately, a construction which allowed for symbols to be pushed on…
Joey Eremondi
- 2,832
- 15
- 29
16
votes
2 answers
New algorithm for Discrete log and its implications for Quantum computing
A new paper came out claiming quasi-polynomial algorithm for Discrete Logarithm.
http://arxiv.org/abs/1306.4244
If correct, does it mean we no longer have an exponential separation in complexity of a classical algorithm and its quantum version for…
Turbo
- 12,812
- 1
- 19
- 68
16
votes
1 answer
Implications of approximating the determinant
It is known that one can compute exactly the determinant of an $n\times n$ matrix in determinstic $\log^2(n)$ space.
What would be the complexity implications of approximating the determinant of a real matrix, of norm at most $1$…
Lior Eldar
- 1,224
- 6
- 14
16
votes
1 answer
Why is it important that the secret is at the end when signing with MD5?
it is often said that when using the MD5 algorithm to sign some arbitrary information, the shared secret has to be at the end. Why?
Hendrik Brummermann
- 263
- 1
- 3
- 7
16
votes
3 answers
Subset sum vs. Subset product (strong vs. weak NP hardness)
I was hoping that some one might be able to explain to me why exactly the subset product problem is strongly NP-hard while the subset sum problem is weakly NP-hard.
Subset Sum: Given $X = \{x_1,...,x_n\}$ and $T$, does there exist a subset $X'$ such…
RDN
- 325
- 2
- 7
16
votes
2 answers
minimizing size of regular expression for finite sets
It is known that minimizing the size of a regular expression is PSPACE-complete even if we have a DFA as the language's specification.
What are the results if the language is finite?
One can consider this problem in two models:
The input is all…
Chao Xu
- 4,399
- 23
- 32