Most Popular
1500 questions
31
votes
1 answer
Treewidth and the NL vs L Problem
ST-Connectivity is the problem of determining whether there exists a directed path between two distinguished vertices $s$ and $t$ in a directed graph $G(V,E)$. Whether this problem can be solved in logspace, is a long-standing open problem. This is…
Shiva Kintali
- 10,578
- 41
- 74
31
votes
19 answers
Beautiful results in TCS
Recently, a friend of mine (working in TCS) mentioned in a conversation that "he wanted to see/know all (or as much as possible) of the beautiful results in TCS in his lifetime". This kind of made me wonder about the beautiful results in this area…
Nikhil
- 664
- 7
- 15
30
votes
3 answers
Known algorithms to go from a DFA to a regular expression
I was wondering whether there is a ``better'' (I will explain in what sense) algorithm to start from a DFA $\mathcal{A}$ and construct a regular expression $r$ such that $L(\mathcal{A})=L(r)$, than the one in the book by Hopcroft and Ullman (1979).…
Janoma
- 1,406
- 11
- 27
30
votes
2 answers
Drunken birds vs drunken ants: random walks between two and three dimensions
It's well known that a random walk in the two dimensional grid will return to the origin with probability 1. It's also known that the same random walk in THREE dimensions has a probability strictly less than 1 of returning to the origin.
My…
Suresh Venkat
- 32,071
- 4
- 95
- 271
30
votes
2 answers
How hard is it to count the number of factors of an integer?
Given an integer $N$ of length $n$ bits, how hard is it to output the number of prime factors (or alternatively number of factors) of $N$?
If we knew the prime factorization of $N$, then this would be easy. However, if we knew the number of prime…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
30
votes
9 answers
What is the best place to get BibTeX entries for computer science articles ?
Other than ACM, IEEE computer Society, Google Scholar which is the best site to get bibtex entries for computer science related articles ?
user3162
- 709
- 5
- 12
30
votes
3 answers
Curry-Howard and programs from non-constructive proofs
This is a follow up question to
What is the difference between proofs and programs (or between propositions and types)?
What program would correspond to a non-constructive (classical) proof of the form $\forall k \ T(e,k) \lor \lnot \forall k \…
Kaveh
- 21,577
- 8
- 82
- 183
30
votes
2 answers
Hierarchies in NP (under the assumption that P != NP)
Assuming that P != NP, I believe it has been shown that there are problems which are not in P and not NP-Complete. Graph Isomorphism is conjectured to be such a problem.
Is there any evidence of more such 'layers' in NP? i.e. A hierachy of more than…
Aryabhata
- 1,855
- 3
- 21
- 29
30
votes
1 answer
Functions that are Not Efficiently Computable but Learnable
We know that (see, e.g., Theorems 1 and 3 of [1]), roughly speaking, under suitable conditions, functions that can be efficiently computed by Turing machine in polynomial time ("efficiently computable") can be expressed by polynomial neural networks…
Minkov
- 852
- 5
- 17
30
votes
3 answers
Did "Where the really hard problems are" hold up? What are current ideas on the subject?
I found this paper to be very interesting. To summarize: it discusses why in practice you rarely find a worst-case instance of a NP-complete problem. The idea in the article is that instances usually are either very under- or very overconstrained,…
dimpol
- 403
- 3
- 5
30
votes
2 answers
Proof refutation: Amateur reviews of ambitious CoRR papers
I guess that I read too many ambitious CoRR papers. The problem is that those papers are not peer reviewed, but often sound interesting and pass basic plausibility checks. Or maybe they don't, and I just need to improve my plausibility checks. Here…
Thomas Klimpel
- 3,043
- 18
- 44
30
votes
6 answers
Well known classes of boolean formulas that require exponentially long resolution proofs
You might often find cutting plane methods, variable propagation, branch and bound, clause learning, intelligent backtracking or even handwoven human heuristics in SAT solvers. Yet for decades the best SAT solvers have relied heavily on resolution…
Ross Snider
- 2,035
- 2
- 20
- 33
30
votes
1 answer
Fourier coefficients Boolean Functions described by Bounded Depth Circuits with AND OR and XOR gates
Let $f$ be a Boolean function and let's think about f as a function from $\{-1,1\}^n$ to $\{ -1,1 \}$. In this language the Fourier expansion of f is simply the expansion of f in terms of square free monomials. (These $2^n$ monomials form a basis to…
Gil Kalai
- 6,033
- 35
- 73
30
votes
0 answers
The complexity of checking whether two DAG have the same number of topological sorts
This problem is highly related to the CNF one.
Here is the problem: given two DAG (directed acyclic graphs), if they have the same counting of topological sorts, answer "Yes", otherwise, answer "No".
Intuitively, the complexity of this problem is…
Mike Chen
- 709
- 4
- 10
30
votes
2 answers
Is there an oracle such that SAT is not infinitely often in sub-exponential time?
Define $io$-$SUBEXP$ to be the class of languages $L$ such that there is a language $L' \in \cap_{\varepsilon > 0} TIME(2^{n^{\varepsilon}})$ and for infinitely many $n$, $L$ and $L'$ agree on all instances of length $n$. (That is, this is the class…
Ryan Williams
- 27,465
- 7
- 115
- 164