Most Popular
1500 questions
25
votes
19 answers
What tools do you use to give presentations?
I was wondering what tools that people in this field (theoretical computer science) use to create presentations. Since a great deal of computer science is not just writing papers but also giving presentations I thought that this would be an…
Joshua Herman
- 1,661
- 17
- 38
25
votes
2 answers
Formula size lower bounds for AC0 functions
Question:
What is the best known formula size lower bound for an explicit function in AC0? Is there an explicit function with an $\Omega(n^2)$ lower bound?
Background:
Like most lower bounds, formula size lower bounds are hard to come by. I am…
Robin Kothari
- 13,617
- 2
- 60
- 116
25
votes
2 answers
Do dependent types give you everything subtyping does?
Types and Programming Languages focuses quite a bit on subtyping, but as far as I can tell, subtyping doesn't seem especially fundamental. Does subtyping give you anything more than dependent types do? Working with dependent types is bound to be…
John Salvatier
- 1,325
- 13
- 11
25
votes
3 answers
What's the difference between term rewriting and pattern matching?
As there was no response at Lambda the Ultimate I try it here again: term rewriting systems are used for instance in automated theorem proving a symbolic calculation, and of course to define formal grammars. There are some programming languages…
Jakob
- 1,259
- 11
- 16
25
votes
1 answer
Major mistakes in accepted FOCS/STOC papers
Have you come across an occasion like that in the past? Well, there is a possibility for everything but I would like to know how realistic this incidence can be. I am referring to serious mistakes altering the target of the paper and not minor…
N27
- 573
- 5
- 14
25
votes
5 answers
What is the maximum number of stable marriages for an instance of the Stable Marriage Problem?
Stable Marriage Problem: http://en.wikipedia.org/wiki/Stable_marriage_problem
I am aware that for an instance of a SMP, many other stable marriages are possible apart from the one returned by the Gale-Shapley algorithm. However, if we are given only…
asc
- 353
- 1
- 3
- 4
25
votes
5 answers
Minimum Flip Connectivity Problem
I formulated the following problem today while playing with my GPS. Here it is :
Let $G(V,E)$ be a directed graph such that if $e=(u,v) \in E$ then $(v,u) \notin E$, i.e., $G$ is an orientation of the underlying undirected graph. Consider the…
Shiva Kintali
- 10,578
- 41
- 74
25
votes
1 answer
Random self-avoiding lattice cycle within a given bounding box
In connection with the Slither Link puzzle, I've been wondering: Suppose that I have an $n\times n$ grid of square cells, and I want to find a simple cycle of grid edges, uniformly at random among all possible simple cycles.
One way to do this would…
David Eppstein
- 50,990
- 3
- 170
- 278
25
votes
2 answers
Is "Experimental Complexity Theory" being used to solve open problems?
Scott Aaronson proposed an interesting challange: can we use supercomputers today to help solve CS problems in the same way that physicists use large particle colliders?
More concretely, my proposal is to
devote some of the world’s computing
…
Shane
- 2,233
- 3
- 26
- 25
25
votes
3 answers
How is proving a context free language to be ambiguous undecidable?
I've read somewhere that a Turing machine cannot compute this and it's therefore undecidable but why? Why is it computationally impossible for a machine to generate the parse tree's and make a decision? Perhaps I'm wrong and it can be done?
Ulkmun
- 379
- 1
- 3
- 6
25
votes
7 answers
Finding twin vertices in graphs
Let $G=(V,E)$ be a graph. For a vertex $x\in V$, define $N(x)$ to be the (open) neighbourhood of $x$ in $G$. That is, $N(x)=\{y\in V \,\vert\, \{x,y\}\in E\}$. Define two vertices $u,v$ in $G$ to be twins if $u$ and $v$ have the same set of…
gphilip
- 1,394
- 1
- 12
- 31
25
votes
3 answers
Graph Isomorphism and hidden subgroups
I'm trying to understand the relationship between graph isomorphism and the hidden subgroup problem. Is there a good reference for this ?
Suresh Venkat
- 32,071
- 4
- 95
- 271
25
votes
1 answer
Tardos Function Counterexample to Blum's $P\neq NP$ Claim
In this thread, Norbet Blum's attempted $P \neq NP$ proof is succinctly disproved by noting that the Tardos function is a counterexample to Theorem 6.
Theorem 6: Let $f \in \mathcal{B}_n$ be any monotone Boolean function. Assume that there is a…
user144527
- 371
- 2
- 3
25
votes
2 answers
Is there an NP-complete language that contains precisely half of the n-bit instances?
Is there a (preferably natural) NP-complete language $L\subseteq \{0,1\}^*$, such that for every $n\geq 1$
$$|L\cap \{0,1\}^n|=2^{n-1}$$
holds? In other words, $L$ contains precisely half of all $n$-bit instances.
Andras Farago
- 11,396
- 37
- 70
25
votes
5 answers
Subexponentially solvable hard graph problems
In light of the recent result of Arora, Barak, and Steurer, Subexponential Algorithms for Unique Games and Related Problems, I'm interested in graph problems that have subexponential time algorithms but believed not to be polynomially solvable. A…
Mohammad Al-Turkistany
- 20,928
- 5
- 63
- 149