Most Popular
1500 questions
16
votes
1 answer
Novel proof of pumping lemma for regular languages
Let $\mathcal{L}$ be the family of all languages over $\Sigma$ satisfying the pumping property of regular languages. Namely: for each $L\in\mathcal{L}$, there is an $N\in\mathbb{N}$ s.t. every word $w\in L$, $|w|> N$ can be written in the form
$…
Aryeh
- 10,494
- 1
- 27
- 51
16
votes
5 answers
Examples of successful derandomization from BPP to P
What are some major examples of successful derandomization or at least progress in showing concrete evidence towards $P=BPP$ goal (not the hardness randomness connection)?
The only example that comes to my mind is AKS deterministic polynomial time…
user34945
16
votes
2 answers
Regular versus TC0
According to the Complexity Zoo,
$\mathsf{Reg} \subseteq \mathsf{NC^1}$ and
we know that $\mathsf{Reg}$ cannot count so $\mathsf{TC^0} \not\subseteq \mathsf{Reg}$.
However it doesn't say if $\mathsf{Reg} \subseteq \mathsf{TC^0}$ or not. Since we…
Kaveh
- 21,577
- 8
- 82
- 183
16
votes
1 answer
Is Dynamic Programming never weaker than Greedy?
In the circuit complexity, we have separations between powers of various circuit models.
In the proof complexity, we have separations between powers of various proof systems.
But in the algorithmic, we still have only few separations between…
Stasys
- 6,765
- 29
- 54
16
votes
0 answers
When does adding edges decrease the cover time of a graph?
When first learning about random walks on a graph $G$, one may have an intuitive feeling that adding edges to $G$ will decrease its cover time $C(G)$. However, this is not the case. The path graph $P_n$ has cover time $C(P_n) = \Theta(n^2)$ while…
Tyson Williams
- 4,258
- 2
- 23
- 44
16
votes
2 answers
Recent TCS publications with philosophical aspects
Many computer science publications from the 1950s and 1960s contain fascinating philosophical speculations on the nature of the mind and the meaning of information in relation to the physical world. Famous examples are the "Turing Test", Zuse's…
user36322
- 161
- 2
16
votes
0 answers
Quantum Hardness of Finding Nash Equilibria
This question is inspired by the recent, beautiful work On the Cryptographic Hardness of Finding a Nash Equilibrium by Bitansky, Paneth, and Rosen.
Their main result is that the existence of indistinguishability obfuscation ($i\mathcal{O}$) and…
Daniel Apon
- 6,001
- 1
- 37
- 53
16
votes
2 answers
What is worst case complexity of number field sieve?
Given composite $N\in\Bbb N$ general number field sieve is best known factorization algorithm for integer factorization of $N$. It is a randomized algorithm and we get an expected complexity of $O\Big(e^{\sqrt{\frac{64}{9}}(\log N)^{\frac…
user34945
16
votes
1 answer
Complexity classes for proofs of knowledge
Prompted by a question Greg Kuperberg asked me, I'm wondering if there are any papers that define and study complexity classes of languages admitting various kinds of proofs of knowledge. Classes like SZK and NISZK are extremely natural from a…
Scott Aaronson
- 13,733
- 2
- 62
- 68
16
votes
4 answers
Program reasoning about own source code
The inspiration for this question is the following (vague) question: What are the programming language/logical foundations for having an AI which could reason about its own source code and modify it?
This isn't at all rigorous, so here is my attempt…
Holden Lee
- 638
- 3
- 13
16
votes
0 answers
Is it possible to boost the error probability of a Consensus protocol over dynamic network?
Consider the binary consensus problem in a synchronous setting over dynamic network (thus, there are $n$ nodes, and some of them are connected by edges that may change round to round). Given a randomized $\delta$-error Monte Carlo protocol for…
Irvan
- 211
- 1
- 5
16
votes
1 answer
Complexity of deciding whether a family is a Sperner familiy
We are given a family $\mathcal{F}$ of $m$ subsets of {1, ...,n}. Is it possible to find a non-trivial lower bound on the complexity of deciding whether $\mathcal{F}$ is a Sperner family ? The trivial lower bound is $O(n m)$ and I strongly suspect…
Anthony Leverrier
- 987
- 7
- 16
16
votes
1 answer
How expensive may it be to destroy all long s-t paths in a DAG?
We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal destroys all $s$-$t$ paths longer than $k$; shorter…
Stasys
- 6,765
- 29
- 54
16
votes
1 answer
Which monotone Boolean functions are representable as thresholds on sums?
I will introduce my problem with an example. Say you are designing an exam, which consists of a certain set of $n$ independent questions (that the candidates can get either right or wrong). You want to decide on a score to give to each of the…
a3nm
- 9,269
- 27
- 86
16
votes
0 answers
a geometric variant of k-medians. NP-hard or in P?
The following problem is a special case of k-medians. Is it NP-hard? Is it in P?
Input: $n$ points $(x_1,y_1), (x_2,y_2), \ldots, (x_n, y_n)$ with each $y_i \ge 0$, and an integer $k$.
Output: a set $S$ containing $k$ of the given points, of…
Neal Young
- 10,546
- 33
- 60