Most Popular
1500 questions
17
votes
1 answer
What is the complexity of this edge coloring problem?
Recently, I have encountered the following variant of edge coloring.
Given a connected undirected graph, find a coloring of the edges that uses the maximum number of colors while also satisfying the constraint that, for every vertex $v$, the edges…
RIC_Eien
- 439
- 2
- 4
17
votes
2 answers
Is propositional resolution a complete proof system?
This question is about propositional logic and all occurrences of "resolution" should be read as "propositional resolution".
This question is something extremely basic but it has been bothering me for a while. I see people assert that propositional…
Vijay D
- 12,566
- 2
- 35
- 61
17
votes
2 answers
SC^2 algorithms for st-connectivity
Savitch gave a deterministic algorithm to solve st-connectivity using $O({\log}^2{n})$ space, implying $NL \subseteq DSPACE({\log}^2{n})$. Savitch’s algorithm runs in time $2^{O({\log}^2{n})}$. It is a major open problem whether st-connectivity can…
Shiva Kintali
- 10,578
- 41
- 74
17
votes
1 answer
Asymptotically, how many permutations of $[1..n]$ have at most $k$ inversions?
Consider a permutation $\sigma$ of $[1..n]$. An inversion is defined as a pair $(i, j)$ of indices such that $i < j$ and $\sigma(i) > \sigma(j)$.
Define $A_k$ to be the number of permutations of $[1..n]$ with at most $k$ inversions.
Question:…
Vinayak Pathak
- 1,631
- 10
- 22
17
votes
5 answers
Stronger notions of uniformizations?
One gap that I was always aware that I don't really understand is between non uniform and uniform computational complexity where the circuit complexity represents the non uniform version and Turing machines is were things are uniform. I suppose…
Gil Kalai
- 6,033
- 35
- 73
17
votes
2 answers
What are TCS conjectures that were proved for primes and small values but then turned out to be false?
Are there any conjectures in theoretical computer science that involve some parameter n and were proved for small values of n AND for primes but later turned out to be false?
In number theory such problems do exist, eg. as Aaron Meyerowitz points…
domotorp
- 13,931
- 37
- 93
17
votes
2 answers
An extension of the noise operator
In a problem I am currently working on, an extension of the noise operator arises naturally, and I was curious whether there has been prior work. First let me revise the basic noise operator $T_{\varepsilon}$ on real-valued Boolean functions. Given…
Amir
- 729
- 4
- 12
17
votes
3 answers
What is a practical non-von Neumann architecture?
Are there any practical applications for non-von Neumann programming models? What are the most widely adopted non-von Neumann programming languages?
Len Yabloko
- 173
- 1
- 5
17
votes
1 answer
Does Conway's PRIMEGAME generate all prime powers of 2?
Most sites I have visited reading on this interesting topic state something along the lines
"the only powers of two (other than 2 itself) that occur in this sequence are those with prime exponent" (MathWorld)
or
"After 2, this sequence contains…
The Vee
- 273
- 1
- 5
17
votes
1 answer
Why are perfect graphs called perfect?
Sorry, if this is a naive question, but I could not find the justification in any of the major text books like Bondy-Murty, Diestel or West. Perfect graphs have many beautiful properties, but what is the single reason they are called perfect? Or is…
Arindam Pal
- 1,591
- 12
- 23
17
votes
2 answers
Hardness of parameterized CLIQUE?
Let $0\le p\le 1$ and consider the decision problem
CLIQUE$_p$
Input: integer $s$, graph $G$ with $t$ vertices and $\lceil p\binom{t}{2} \rceil$ edges
Question: does $G$ contain a clique on at least $s$ vertices?
An instance of CLIQUE$_p$ contains…
András Salamon
- 19,000
- 3
- 64
- 150
17
votes
2 answers
similar matrices
Given two $n \times n$ matrices $A$ and $B$, the problem of deciding if there exist a permutation matrix $P$ such that $B = P^{-1}AP$ is equivalent to GI(Graph Isomorphism). But if we relax $P$ to be just an invertible matrix, then what is the…
DurgaDatta
- 1,281
- 6
- 18
17
votes
1 answer
Who introduced the complexity class AC?
I taught $AC^0$ lower bounds today, and one of the students asked about the reason for the name $AC$.
The official explanation is that the "A" stands for "Alternation".
I vaguely remember being told many years ago that Nick Pippenger Steve Cook…
Dana Moshkovitz
- 10,979
- 1
- 50
- 77
17
votes
3 answers
Properties of Random Directed Graphs with Fixed Out-Degree
I am interested in properties of random directed graphs with fixed out-degree $d$. I am imagining a random graph model where each vertex chooses d neighbors (say, with replacement) u.a.r.
Question: Is anything known about the stationary
…
Lev Reyzin
- 11,968
- 13
- 63
- 103
17
votes
4 answers
Hard Problems for higher genus graphs
Planar graphs have genus zero. Graphs embeddable on a torus have genus at most 1. My question is simple :
Are there any problems that are polynomially solvable on planar graphs but NP-hard on graphs of genus one ?
More generally are there any…
Shiva Kintali
- 10,578
- 41
- 74