My posts are related to various topics and open problems in Computational Complexity, Circuit Complexity, Communication Complexity, Algorithmic Game Theory, Polyhedral Combinatorics, Hardness of Approximation, Approximation Algorithms and Graph Theory.
Editor reviews are provided by professional editors who evaluate a blog based on the following criteria: Frequency of Updates, Relevance of Content, Site Design, and Writing Style.
Here are some open problems (that interest me) from FOCS 2009. If you want to share an open problem, please leave a comment.
Starting with my paper…….
1) Reducibility Among Fractional Stability Problems
Shiva Kintali, Laura Poplawski, Rajmohan...
Given an undirected graph G(V,E), how fast can we detect if G is triangle-free ? Cubic time is obvious. Let A be the adjacency matrix of G. We can detect triangle-freeness of G in the same complexity as multiplying two boolean matrices (AxA) (duh !!)....
Bertrand’s postulate states that for every positive integer n, there is always at least one prime psuch that n < p < 2n. This was proved by Chebyshev in 1850, Ramanujan in 1919 and Erdos in 1932.
Legendre’s conjecture states that there is a prime...
The class \aczero\ consists of all uniform families of circuits of constant depth and polynomial size, with unlimited-fanin AND and OR gates. NOT gates are allowed only at the inputs. The class \saczero\ is the semi-unbounded version of \aczero\ i.e.,...
I am back in Atlanta after attending an awesome Barriers Workshop. This workshop is mainly about the barriers in resolving P vs NP problem and possible techniques to overcome these barriers. It is a five day workshop covering circuits lower bounds,...
