Most Popular
1500 questions
27
votes
6 answers
Graph families which have polynomial time algorithms for computing the chromatic number
Post updated on 31st of August: I added a summary of the current answers below the original question. Thanks for all the interesting answers! Of course, everyone can continue posting any new findings.
For which graph families there exists a…
Joel Rybicki
- 523
- 5
- 9
27
votes
6 answers
How do you get a "Physical Intuition" for results in TCS?
I'm sorry if this question is a little vague, but I am curious how successful researchers get a "feel" for the results in TCS.
For example, linear algebra can be understood geometrically, or in terms of its physical interpretations (eigenvectors can…
gabgoh
- 1,548
- 12
- 22
27
votes
3 answers
Computing any information about Max-3SAT
For a 3CNF formula $C$ let $M(C)$ be the maximal number of satisfied clauses in any assignment to $C$. It is known that Max-3SAT is hard to approximate (subject to P≠NP), i.e. there is no polytime algorithm whose input is a 3CNF formula $C$, and…
Boris Bukh
- 1,007
- 9
- 16
27
votes
2 answers
Is it possible to find if a sequence exists in polynomial time in the following problem?
I've been thinking about the following problem for a time, and I haven't found a polynomial solution for it. Only brute-fource. I've been trying to reduce an NP-Complete problem into it too with no sucess.
Here is the problem:
You have a sorted…
Oscar Mederos
- 443
- 3
- 12
27
votes
7 answers
Why would a TCS researcher need funding?
I was reading this. It says
... You won't find yourself as starving for funding like Pure Mathematics. (You'll still always find yourself starving for funding.)...
Why do pure mathematicians need funding?(Ooops its mathoverflow question)
Why…
Pratik Deoghare
- 1,924
- 18
- 26
27
votes
3 answers
Reverse Graph Spectra Problem?
Usually one constructs a graph and then asks questions about the adjacency matrix's (or some close relative like the Laplacian) eigenvalue decomposition (also called the spectra of a graph).
But what about the reverse problem? Given $n$…
user834
- 2,806
- 21
- 27
27
votes
2 answers
Papers to credit for spectral partitioning of graphs
If $G=(V,E)$ is an undirected $d$-regular graph and $S$ is a subset of the vertices of cardinality $\leq |V|/2$, call the edge expansion of $S$ the quantity
$\phi(S) := \frac {Edges(S,V-S)}{d\cdot |S|\cdot |V-S|}$
Where $Edges(A,B)$ is the number…
Luca Trevisan
- 4,912
- 28
- 34
27
votes
2 answers
Can we not output the Kolmogorov complexity?
Let us fix a prefix-free encoding of Turing-machines and a universal Turing-machine $U$ that on input $(T,x)$ (encoded as the prefix-free code of $T$ followed by $x$) outputs whatever $T$ outputs on input $x$ (possibly both running forever).
Define…
domotorp
- 13,931
- 37
- 93
27
votes
0 answers
Is Hankelability NP-hard?
I asked this question on SO on April 7 and added a bounty which has now expired but no poly time solution has been found yet.
I am trying to write code to detect if a matrix is a permutation of a Hankel matrix. Here is the spec.
Input: An n by n…
Simd
- 3,902
- 20
- 49
27
votes
1 answer
What are consequences of the collapse of CH?
I don't grasp the full complexity of the counting hierarchy $CH$. I understand $CH$ is in $PSPACE$, and contains $PH$ within its second level, due to the Toda's theorem. But, what would be important consequences of the collapse of $CH$? I got a sort…
neophyte
- 531
- 3
- 5
27
votes
1 answer
Deciding emptiness of intersection of regular languages in subquadratic time
Let $L_1,L_2$ be two regular languages given by NFAs $M_1,M_2$ as input.
Assume we would like to check whether $L_1\cap L_2\neq \emptyset$. This can clearly be done by a quadratic algorithm which computes the product automaton of $M_1,M_2$, but I…
R B
- 9,448
- 5
- 34
- 74
27
votes
2 answers
Complexity of n-queens-completion?
The classical $n$-queens problems asks, given a positive integer $n$, whether there is an array $Q[1..n]$ of integers satisfying the following conditions:
$1\le Q[i] \le n$ for all $i$
$Q[i] \ne Q[j]$ for all $i\ne j$
$Q[i]-i \ne Q[j]-j$ for all…
Jeffε
- 23,129
- 10
- 96
- 163
27
votes
1 answer
Other applications of Karger-Stein branching amplification?
I just taught the Karger-Stein randomized mincut algorithm in my graduate algorithms class. This is a real algorithmic gem, so I can't not teach it, but it always leaves me frustrated, because I don't know any other applications of the main…
Jeffε
- 23,129
- 10
- 96
- 163
27
votes
2 answers
Why are Ramanujan graphs named after Ramanujan?
I recently taught expanders, and introduced the notion of Ramanujan graphs.
Michael Forbes asked why they are called this way, and I had to admit I don't know.
Anyone?
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
27
votes
1 answer
Is there a regular tree language in which the average height of a tree of size $n$ is neither $\Theta(n)$ nor $\Theta(\sqrt{n})$?
We define a regular tree language as in the book TATA: It is the set of trees accepted by a non-deterministic finite tree automaton (Chapter 1) or, equivalently, the set of trees generated by a regular tree grammar (Chapter 2). Both formalisms hold…
john_leo
- 431
- 4
- 7