Most Popular
1500 questions
23
votes
1 answer
How big is the variance of the treewidth of a random graph in G(n,p)?
I am trying to find how close $tw(G)$ and $E[tw(G)]$ really are, when $G \in G(n,p=c/n)$
and $c>1$ is a constant not depending on n (so $E[tw(G)] = \Theta(n)$). My estimate is that $tw(G) \leq E[tw(G)] + o(n)$ w.h.p, but i haven't been able to prove…
Kostas
- 331
- 1
- 3
23
votes
1 answer
Can all unambiguous grammars be parsed in linear time?
When tinkering with noncanonical LR parsing, I thought up a parsing method (with infinitely sized tables, which makes it somewhat unpractical) capable of parsing exactly the unambiguous grammars in $O(n^2)$ time, and I wondered if it is possible to…
Alex ten Brink
- 4,680
- 25
- 48
22
votes
1 answer
What's the "real" reason that IP=PSPACE is non-relativizing?
IP=PSPACE is listed as the canonical example of a non-relativizing result, and the proof for this is that there exists an oracle $O$ such that ${\sf coNP}^O \not\subseteq {\sf IP}^O$, while ${\sf coNP}^O \subseteq {\sf PSPACE}^O$ for all oracles…
Henry Yuen
- 3,798
- 1
- 21
- 33
22
votes
2 answers
Yao's Minimax Principle on Monte Carlo Algorithms
The celebrated Yao's Minimax Principle states the relation between distributional complexity and randomized complexity. Let $P$ be a problem with a finite set $\mathcal{X}$ of inputs and a finite set $\mathcal{A}$ of deterministic algorithm to solve…
Federico Magallanez
- 591
- 4
- 8
22
votes
5 answers
Theoretical Applications for Approximation Algorithms
Lately I've started looking into approximation algorithms for NP-hard problems and I was wondering about the theoretical reasons for studying them. (The question is not meant to be inflammatory - I'm merely curious).
Some truly beautiful theory has…
Anon1234
- 229
- 1
- 3
22
votes
8 answers
Other kinds of running time analysis besides worst-case, average-case, etc?
Here are some ways to analyze the running time of an algorithm:
1) Worst-case analysis: Running time on the worst instance.
2) Average-case analysis: Expected running time on a random instance.
3) Amortized analysis: Average running time on the…
umar
- 329
- 1
- 7
22
votes
1 answer
Does $\mathsf{P/poly}$ have subexponential-size bounded-depth circuits?
Is there any plausible complexity/crypto hypothesis that rules out the possibility that polynomial size circuits have subexponential-size (i.e. $2^{O(n^\epsilon)}$ with $\epsilon<1$) bounded-depth ($d = O(1)$) circuits?
We know that every function…
Kaveh
- 21,577
- 8
- 82
- 183
22
votes
1 answer
Partition a graph into node-disjoint cycles
Related problem: Veblen’s Theorem states that "A graph admits a cycle decomposition if and only if it is even". The cycles are edge disjoint, but not necessarily node disjoint. Put another way, "The edge set of a graph can be partitioned into cycles…
Peng Zhang
- 1,453
- 9
- 19
22
votes
1 answer
Are there natural separations in the nondeterministic time hierarchy?
The original Nondeterministic Time Hierarchy Theorem is due to Cook (the link is to S. Cook, A hierarchy for nondeterministic time complexity, JCSS 7 343–353, 1973). The theorem states that for any real numbers $r_1$ and $r_2$, if $1 \le r_1 \lt…
András Salamon
- 19,000
- 3
- 64
- 150
22
votes
3 answers
Problems outside of P that are not P-hard
While reading an answer by Peter Shor and an earlier question by Adam Crume I realized that I have some misconceptions about what it means to be $\mathsf{P}$-hard.
A problem is $\mathsf{P}$-hard if any problem in $\mathsf{P}$ is reducible to it with…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
22
votes
1 answer
What is the current known hardness of Graph Isomorphism?
Inspired by the question is factoring known to be P-hard, I wonder what the current similar state of knowledge is about the hardness of graph isomorphism. I am sure that it is currently not known if GI is in P, but:
what is the currently known…
Mitch
- 905
- 8
- 19
22
votes
1 answer
Belief propagation for approximate real 3LIN?
In a Science paper from 2002, Mezard, Parisi and Zecchina put forward the belief propagation heuristic for random 3SAT. Experiments indicate that the heuristic works well for ratios of constraints-per-variable for which a satisfying assignment is…
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
22
votes
5 answers
Direct SAT to 3-SAT reduction
Here the goal is to reduce an arbitrary SAT problem to 3-SAT in polynomial time using the fewest number of clauses and variables. My question is motivated by curiosity. Less formally, I would like to know: "What is the 'most natural' reduction…
Mikola
- 581
- 1
- 3
- 10
22
votes
2 answers
Bounds on $E[f(x)]$ in terms of $f(E[x])$ other than Jensen's inequality?
If $f$ is a convex function then Jensen's inequality states that $f(\textbf{E}[x]) \le \textbf{E}[f(x)]$, and mutatis mutandis when $f$ is concave. Clearly in the worst case you cannot upper bound $\textbf{E}[f(x)]$ in terms of $f(\textbf{E}[x])$…
Ian
- 2,727
- 20
- 24
22
votes
5 answers
Program for computing Tree decomposition of a graph
Does anybody know of an open-source program for computing Tree decomposition of graphs for a fixed "k"(width)? I know that the problem of finding Tree-Decomposition is NP-Hard for variable "k", but my input instances will be really small (~10 nodes)…
user4654