Most Popular
1500 questions
17
votes
0 answers
Is Node Multiway Cut NP-complete on planar graphs when all terminals lie on the outer face?
I am interested in the following problem.
Node Multiway Cut on Planar Graphs with terminals on the outer face
Instance: A plane graph G, and integer k, and a set $S \subseteq V(G)$ of terminals which are all incident on the outer face of…
Bart Jansen
- 5,265
- 21
- 39
17
votes
1 answer
Forbidden minors for bounded genus graphs
It is well known that $K_5$ and $K_{3,3}$ are forbidden minors for planar graphs. There are hundreds of forbidden minors for graphs embeddable on a torus. The number of forbidden minors for graphs embeddable on surface of genus g is an exponential…
Shiva Kintali
- 10,578
- 41
- 74
17
votes
2 answers
Sorting by Euclidean distance
$S$ is a set of points on a plane. A random point $x \notin S$ is given on the same plane. The task is to sort all $y \in S$ by Euclidean distance between $x$ and $y$.
A no-brain approach is to calculate distances between $x$ and $y$ for all $y \in…
Alex K.
- 173
- 4
17
votes
0 answers
Problem-Dependent Derandomization
The famous result of Impagliazzo and Wigderson in '97 cemented our belief that BPP is most likely the same as P; that is, problems that can be efficiently solved with randomness can also be efficiently solved without randomness. This result was…
Henry Yuen
- 3,798
- 1
- 21
- 33
17
votes
2 answers
Is there any problem in $\mathsf{\Sigma^P_2}$ which is solvable in bounded tree width graphs?
I'm looking for a problem which belongs to $\mathsf{\Sigma^P_2}$ in general graphs but is in $\mathsf{P}$ in bounded tree width graphs, In fact I think this problems are harder than using normal dynamic programming in bounded-treewidth graphs to…
Saeed
- 3,440
- 1
- 22
- 39
17
votes
2 answers
Can chess simulate a Universal Turing Machine?
I am looking to get a definite answer to title question.
Is there a set of rules that translates any program into a configuration of finite pieces on an infinite board, such that if black and white plays only legal moves, the game ends in finite…
TROLLHUNTER
- 209
- 2
- 6
17
votes
3 answers
Which $AC^0$ problems are not "truly feasible"?
Neil Immerman's famous Picture of The World is the following (click to enlarge):
His "Truly feasible" class includes no other class; my question is then:
What is an AC0 problem which is considered to be…
Michaël Cadilhac
- 3,946
- 22
- 39
17
votes
2 answers
A reading list on experimental algorithmics
As in, the area of the papers in the ACM Journal on Experimental Algorithmic JEA.
Which were the foundational works? What are the main results? How are they characterized? Any interesting connections to other areas of computer science?
Alexandre Passos
- 1,459
- 12
- 20
17
votes
4 answers
How can I show a Gap-P problem is outside #P
There are a number of problems in combinatorial representation theory and algebraic geometry for which no positive formula is known. There are several examples I am thinking of, but let me take computing Kronecker coefficients as my example.…
David E Speyer
- 401
- 2
- 10
17
votes
3 answers
How Hard is Exact Simulation of Algorithms, and a Related Operation on Complexity Classes
Teaser
Since the problem is longish, here is a special case that captures its essence.
Problem: Let A be a deterministic algorithm for 3-SAT. Is the
problem of completely simulating the algorithm A (on every instance of
the problem). P-Space…
Gil Kalai
- 6,033
- 35
- 73
17
votes
1 answer
Sensitivity of Graph Properties
In [1], Turan shows that the sensitivity (called "critical complexity" in the paper) of a graph property is strictly greater than $\lfloor {1\over 4} m \rfloor$ where $m$ is the number of vertices in the graph. He goes on to conjecture that any…
mhum
- 171
- 2
17
votes
1 answer
Algorithm for optimizing decision trees
Background
A binary decision tree $T$ is a rooted tree where each internal node (and root) is labeled by an index $j \in \{1,..., n\}$ such that no path from root to leaf repeats an index, the leafs are labeled by outputs in $\{A,B\}$, and each edge…
Artem Kaznatcheev
- 10,251
- 12
- 74
- 174
17
votes
1 answer
Fast convolution over small finite fields
What are the best known methods for cyclic convolution of length $n$ over a small field, i.e. when $|\mathbb{F}| \ll n$? I'm particularly interested in constant-sized fields, or even $\mathbb{F} = \mathbb{F}_2$. General asymptotic-efficiency…
Andy Drucker
- 4,634
- 23
- 33
17
votes
2 answers
Importance of ACM/IEEE in TCS conference
Recently I was in an ACM supported conference.
During the banquet, the conference organizers told us about the future and past of the conference. They told us that during the 2010 edition of the conference there was a loss of 5000$.
They showed us…
Gopi
- 1,655
- 16
- 21
17
votes
2 answers
Can strong NP-hardness really be shown using plain polytime reductions?
I recently read a proof that intended to show that a problem was strongly NP-hard, simply by reducing to it (in polynomial time) from a strongly NP-hard problem. This didn’t make any sense to me. I would have thought that you’d have to show that any…
Magnus Lie Hetland
- 1,520
- 10
- 17