Most Popular
1500 questions
50
votes
5 answers
Casual tours around proofs
Today Ryan Williams posted an article on the arXiv (previously appeared in SIGACT News) containing a less technical version of his recent ACC lower bound technique.
My question is not about the technique itself (of course worthy of immense praise),…
Alessandro Cosentino
- 4,000
- 35
- 43
50
votes
5 answers
Is the Chomsky-hierarchy outdated?
The Chomsky(–Schützenberger) hierarchy is used in textbooks of theoretical computer science, but it obviously only covers a very small fraction of formal languages (REG, CFL, CSL, RE) compared to the full Complexity Zoo Diagram. Does the hierarchy…
Jakob
- 1,259
- 11
- 16
50
votes
0 answers
Monotone complexity of s-t connectivity
In the problem CONN, we obtain a directed $n$-vertex graph (encoded as a boolean string of $n^2$ bits, one for each potential edge), and want to decide
whether there is a path between all $n^2$ pairs $(s,t)$ of vertices.
In its special case, STCONN,…
Stasys
- 6,765
- 29
- 54
50
votes
12 answers
What is the theoretical basis of imperative programming?
Functional programming has a theoretical basis in lambda calculus and combinatory logic. As someone involved with statistical computing, I find these concepts to be very useful for modeling.
Is there an equivalent mathematical basis of imperative…
Shane
- 2,233
- 3
- 26
- 25
49
votes
3 answers
How do 'tactics' work in proof assistants?
Question: How do 'tactics' work in proof assistants? They seem to be ways of specifying how to rewrite a term into an equivalent term (for some definition of 'equivalent'). Presumably there are formal rules for this, how can I learn what they are…
John Salvatier
- 1,325
- 13
- 11
49
votes
11 answers
What is the most efficient way to generate a random permutation from probabilistic pairwise swaps?
The question I am interested in is related to generating random permutations. Given a probabilistic pairwise swap gate as the basic building block, what is the most efficient way to produce a uniformly random permutation of $n$ elements? Here I take…
Joe Fitzsimons
- 13,675
- 47
- 91
49
votes
3 answers
Is there a sensible notion of an approximation algorithm for an undecidable problem?
Certain problems are known to be undecidable, but it is nevertheless possible to make some progress on solving them. For example, the halting problem is undecidable, but practical progress can be made on creating tools for detecting potential…
Timothy Chow
- 7,550
- 35
- 43
49
votes
8 answers
The importance of Integrality Gap
I always had trouble in understanding the importance of the Integrality Gap (IG) and bounds on it. IG is the ratio of (the quality of) an optimal integer answer to (the quality of) an optimal real solution of the relaxation of the problem. Lets…
Kaveh
- 21,577
- 8
- 82
- 183
49
votes
4 answers
What are the consequences of $\mathsf{L}^2 \subseteq \mathsf{P}$?
We know that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{P}$ and that $\mathsf{L} \subseteq \mathsf{NL} \subseteq \mathsf{L}^2 \subseteq $ $\mathsf{polyL}$, where $\mathsf{L}^2 = \mathsf{DSPACE}(\log^2 n)$. We also know that $\mathsf{polyL}…
argentpepper
- 2,281
- 15
- 27
48
votes
4 answers
Generalized Ladner's Theorem
Ladner's Theorem states that if P ≠ NP, then there is an infinite hierarchy of complexity classes strictly containing P and strictly contained in NP. The proof uses the completeness of SAT under many-one reductions in NP. The hierarchy contains…
András Salamon
- 19,000
- 3
- 64
- 150
48
votes
5 answers
What is the most intuitive dependent type theory I could learn?
I am interested in getting a really solid grasp on dependent typing. I've read most of TaPL and read (if not fully absorbed) 'Dependent Types' in ATTaPL. I've also read and skimmed a bunch of articles on dependent typing.
Many type theory…
John Salvatier
- 1,325
- 13
- 11
48
votes
6 answers
Ways for a mathematician to stay informed of current research in complexity theory
Complexity theory is a strong secondary interest of mine but it's not my primary research interest, so there is no hope for me to attend all the conferences, read all the blogs, and ensure that the "in" crowd cc: me on every bit of hot news. I try…
Timothy Chow
- 7,550
- 35
- 43
48
votes
17 answers
Physics results in TCS?
It seems clear that a number of subfields of theoretical computer science have been significantly impacted by results from theoretical physics. Two examples of this are
Quantum computation
Statistical mechanics results used in complexity…
Joe Fitzsimons
- 13,675
- 47
- 91
48
votes
2 answers
Explaining Applicative functor in categorical terms - monoidal functors
I'd like to understand Applicative in terms of category theory.
The documentation for Applicative says that it's a strong lax monoidal functor.
First, Wikipedia page about monoidal functors says that a monoidal functor is either lax or strong. So it…
Petr
- 2,601
- 15
- 28
47
votes
3 answers
An NP-complete variant of factoring.
Arora and Barak's book presents factoring as the following problem:
$\text{FACTORING} = \{\langle L, U, N \rangle \;|\; (\exists \text{ a prime } p \in \{L, \ldots, U\})[p | N]\}$
They add, further in Chapter 2, that removing the fact that $p$ is…
Michaël Cadilhac
- 3,946
- 22
- 39