Most Popular
1500 questions
23
votes
3 answers
What bounds can be put on counting reachable nodes in a dag?
Given is a dag. You want to label each node by how many nodes are reachable from it. $O(V(V+E))$ is a trivial upper bound; $\Omega(V+E)$ is a lower bound (I think). Is there a better algorithm? Is there reason to believe the lower bound can be…
Radu GRIGore
- 4,796
- 30
- 69
23
votes
1 answer
Is there any justification to believe that $NL\neq L$?
I wonder if there is any justification to believe that $NL=L$ or to believe that $NL\neq L$?
It is known that $NL \subset L^2$.
The literature on derandomization of $RL$ is pretty convincing that $RL=L$.
Does anyone know about some articles or…
Klim
- 903
- 4
- 16
23
votes
0 answers
Can we do integer addition in linear time?
Why, yes, of course. But I'm actually interested in the cost of computing the sum of multiple integers:
Input: A sequence of nonnegative integers $\langle X_i:i
Emil Jeřábek
- 17,430
- 3
- 61
- 90
23
votes
1 answer
Prove proof irrelevance in Coq?
Is there a way to prove the following theorem in Coq?
Theorem bool_pirrel : forall (b : bool) (p1 p2 : b = true), p1 = p2.
EDIT: An attempt to give a brief explanation for "what proof irrelevance is" (correct me someone if I am wrong or…
day
- 2,795
- 1
- 20
- 27
23
votes
1 answer
FOCS virtual fee $600
I'm not sure this is on topic here, but probably can be best answered by this community, so I'm posting it as a soft-question.
Due to the pandemic, FOCS 2021 will be a virtual conference. Most conferences, when moving online, reduced the…
domotorp
- 13,931
- 37
- 93
23
votes
2 answers
Question about two matrices: Hadamard v. "the magical one" in the proof of the sensitivity conjecture
The recent and incredibly slick proof of the sensitivity conjecture relies on the explicit* construction of a matrix $A_n\in\{-1,0,1\}^{2^n\times 2^n}$, defined recursively as follows:
$$A_1 = \begin{pmatrix} 0&1\\1&0\end{pmatrix}$$
and, for $n\geq…
Clement C.
- 4,461
- 29
- 51
23
votes
2 answers
Are there any hard instances of 3-SAT when the clauses can only use literals that are "nearby" each other?
Let the variables be $x_1 , x_2 , x_3 ... x_n$. The distance between two variables is defined as $d(x_a , x_b) = |a-b|$. The distance between two literals is the distance between the corresponding two variables.
Suppose I have a 3-SAT instance…
IIAOPSW
- 339
- 1
- 4
23
votes
2 answers
Testing whether letters can be scheduled to achieve a word in a regular language
I fix a regular language $L$ on an alphabet $\Sigma$, and I consider the following problem that I call letter scheduling for $L$. Informally, the input gives me $n$ letters and an interval for each letter (i.e., a minimal and maximal position), and…
a3nm
- 9,269
- 27
- 86
23
votes
0 answers
Fine-grained complexity of BPP
If E does not have i.o.-$2^{o(n)}$ circuits, then P=BPP, but this does not tell us about the fine-grained containments between $\mathrm{Time}(n^a)$ and $\mathrm{BPTime}(n^b)$.
Are there reasonable computational complexity conjectures that imply a…
Dmytro Taranovsky
- 2,577
- 1
- 10
- 24
23
votes
4 answers
Communication Complexity ...Classes?
Discussion:
I've been spending some personal time lately learning various things in communication complexity. For instance, I've re-familiarized myself with the relevant chapter in Arora/Barak, started reading some papers, and ordered the book by…
Daniel Apon
- 6,001
- 1
- 37
- 53
23
votes
1 answer
Is the 2016 implementation of Shor's algorithm really scalable?
In the 2016 Science paper "Realization of a scalable Shor algorithm" [1], the authors factor 15 with only 5 qubits, which is fewer than the 8 qubits "required" according to Table 1 of [2] and Table 5 of [3]. The 8-qubit requirement comes from the…
user1271772
- 541
- 3
- 16
23
votes
1 answer
For which regular expressions $\alpha$ is $\{ \beta \mid L(\alpha) = L(\beta) \}$ PSPACE-complete?
It is well known that the following problem is PSPACE-complete:
Given regular expression $\beta$, does $L(\beta) = \Sigma^*$?
What about determining equivalence to other (fixed) regular expressions $\alpha$?
Given regular expression $\beta$, does…
mikero
- 2,799
- 22
- 23
23
votes
2 answers
Are there descriptive complexity representations of quantum complexity classes?
The title more or less says it all, but I guess I could add a bit of background and some specific examples I'm interested in.
Descriptive complexity theorists, such as Immerman and Fagin, have characterized many of the most well-known complexity…
user1338
23
votes
8 answers
graphs from real-life problems
Where can I find graphs relevant to real-life problems?
Two repositories I know of are:
University of Florida's Sparse Matrix Collection
Bodlaender's TreewidthLib
Yaroslav Bulatov
- 4,701
- 1
- 25
- 39
23
votes
2 answers
Which graph parameters are NOT concentrated on random graphs?
It is well known that many important graph parameters show (strong) concentration on random graphs, at least in some range of the edge probability. Some typical examples are the chromatic number, maximum clique, maximum independent set, maximum…
Andras Farago
- 11,396
- 37
- 70