http://kintali.wordpress.com/2009/11/09 ... focs-2009/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 : d**k 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 O(n^3/(log^{2}n)) bound. Their use of Triangle removal lemma and Regularity lemma are particularly interesting.
Open Problems : Ryan mentioned the following open problems in his talk : (1) Can one construct a Weak Regular partition in O(n^{2.9}) time, deterministically ? (2) Can their techniques be applied to All Pairs Shortest Paths Problems ? (3) is there a Regularity concept that is better suited for Matrix Multiplication ?
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.
Βρήκα αυτό το άρθρο για κάποια ανοιχτα προβλήματα που ενδιαφέρουν τον blogger. Δεν είχα υπόψιν μου το FOCS ούτε ότι τα συγκεντρώνουν κάθε χρόνο.
