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 [pdf]
Shiva Kintali, Laura Poplawski, Rajmohan Rajaraman, Ravi Sundaram and Shang-Hua Teng.
Summary : We resolve the computational complexity of a number of outstanding open problems with practical applications and introduce a simple PPAD-complete game (the preference game). Here is the list of problems we show to be PPAD-complete, along with the domains of practical significance: 1) Fractional Stable Paths Problem (FSPP) – Internet routing; 2) Core of Balanced Games – Economics and Game theory; 3) Scarf’s Lemma – Combinatorics; 4) Hypergraph Matching – Social Choice and Preference Systems; 5) Fractional Bounded Budget Connection Games (FBBC) – Social networks; and 6) Strong Fractional Kernel – Graph Theory.
Open Problems : The complexity of Discrete Ham Sandwich Problem and Necklace Splitting Problem are open. These are shown to be in PPAD by Papadimitiou in 1994.
2) Linear systems over composite moduli [pdf]
Arkadev Chattopadhyay and Avi Wigderson.
Summary and Open Problems : Dick Lipton already summarized their result along with open problems.
3) Regularity Lemmas and Combinatorial Algorithms [pdf]
Nikhil Bansal, Ryan Williams
Summary : This paper presents new combinatorial algorithms for Boolean matrix multiplication (BMM) and preprocessing a graph to answer independent set queries. The authors give the first asymptotic improvements on “combinatorial” algorithms for dense BMM in many years, improving on the Four Russians 
Open Problems : Ryan mentioned the following open problems in his talk : (1) Can one construct a Weak Regular partition in 
4) Improved Approximation Algorithms for PRIZE-COLLECTING STEINER TREE and TSP [pdf]
Aaron Archer, MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Howard Karloff
Summary : They give a factor 1.990283 approximation algorithm for Prize-collecting TSP. This is the first result to break the barrier of 2 improving the primal-dual algorithm of Goemans and Williamson. Recently Goemans, presented a 1.91457-approximation algorithm for the prize-collecting travelling salesman problem.
Open Problem : Obvious open problem is to improve this approximation factor.
5) Blackbox Polynomial Identity Testing for Depth 3 Circuits [pdf]
Neeraj Kayal and Shubhangi Saraf.
Open Problems : This paper has a well-written open problems section with specific open problems. If you are interested in polynomial identity testing, I encourage you to read them.
, how fast can we detect if 
is triangle-free ?
and runs in time 
, where 
is the matrix multiplication exponent. This simple algorithm is the best known !! 
is 2.376. At 
. Using their techniques, the best value of 
?
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 
i.e., AND gates have constant fan-in. In the class 
both AND and OR gates have constant fan-in. The following strict hierarchy is known.
, ![NC^0 \subsetneq SAC^0 \subsetneq AC^0 \subsetneq AC^0[p] \subsetneq TC^0](http://s2.wordpress.com/latex.php?latex=NC%5E0+%5Csubsetneq+SAC%5E0+%5Csubsetneq+AC%5E0+%5Csubsetneq+AC%5E0%5Bp%5D+%5Csubsetneq+TC%5E0&bg=ffffff&fg=000000&s=0 "NC^0 \subsetneq SAC^0 \subsetneq AC^0 \subsetneq AC^0[p] \subsetneq TC^0")
.
is closed under complementation and 
is not.
is not closed under complementation.
be a directed simple graph (i.e., 
does not have self-loops or multi-edges) with 
and 
. Let 
represent the indegree of a vertex 
. Motivated by 
as follows :
= 
.
where each 
and 
is in 
encoded as binary strings. The meaning of 
is that there is a directed edge from 
to 
. We may assume that circuits computing 
will have 
binary inputs in a prespecified order.
.
variables, and
terms.
be a CNF circuit computing 
has some term 
that depends on less than 
variables. Then when all inputs to 
are 0, 
outputs 0. Consider the graph 
consisting of a cycle on 
vertices (say 
) and an isolated vertex 
. Note that 
. Let 
be the graph obtained by adding the edge 
to 
. Now 
for 
. If 
then 
, which is a contradiction.
consisting of a cycle on 
except 
) and an isolated vertex 
. 
. 
terms.
.
) computing 
while still computing 
times to obtain an 
.
. Oracle TMs are used in Turing-reducibility, a generalization of mapping-reducibility.
and 
are provably different and 
and 
are provably equal. That is P vs NP has different answers in different worlds !! Hence techniques such as diagonalization, cannot be used to resolve P versus NP. 
. An oracle B exists such that 
.
. The first and third containments are trivial and the second containment follows from Savitch’s theorem. Hence 
. Constructing A is a non-trivial task. Look at Sipser’s book (page 350) for details.
square matrix and q an n dimensional vector. Let LCP(q,M) be the following problem : Find two vectors w and z satisfying
the complementary conditions 
is equivalent to 
. There is an obvious exponential time algorithm to solve LCP. For every i, set either 
or 
and solve the resulting system of linear equations. If one of these linear systems has a solution then the corresponding LCP is solvable. Deciding if a given LCP has a solution is NP-complete. The following exercise shows that LCP is a generalization of LP.
, called petals, each of cardinality at most l, such that all pairs of sets in the family have the same intersection, called the core of the sunflower.
nonempty sets, each of cardinality l or less. Then Z must contain a sunflower.
.
nonempty sets that does not have a sunflower.
nonempty sets, each of cardinality l or less has a sunflower”. This conjecture is still open. It is open even for p=3.
for each edge 
, find a hamiltonian cycle of G with minimum cost. It is well-known that this problem is NP-Complete.
-approximation algorithm for TSP (for any 
) unless P=NP.
, 
. Metric-TSP is also NP-complete. Henceforth, we shall focus on metric TSP.
. Approximation algorithms with factor 2 (find a minimum spanning tree (MST) of 
, one for each edge 
. For a subset 
, 
denotes the edges incident to 
. Let 
denote the sum of values of 
. Frieze, Galbiati and Maffioli [FGM'82] gave a simple 
-approximation algorithm for ATSP in 1982, where n is the number of vertices. In the last eight years, this was improved to a guarantee of 0.999 
by Blaser [Blaser'02], and to 
Kaplan et al [KLSS'03] and to 
by Feige and Singh [FS'07]. So we have an approximation factor better than 
!!
to achieve an integrality gap of 
. Is there a polynomial-sized (in 
) instance achieving an integrality gap of 
and 
) with integers from 
to 
. Now label each edge with absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labeled 
through 
inclusive (with no number repeated).
is a fixed tree with 
edges, then complete graph on 
vertices decomposes into 
copies of 
.
