Some open problems from FOCS2009

Ενημέρωση και συζήτηση πάνω σε ερευνητικά θέματα και πανεπιστημιακά νέα.
Post Reply
User avatar
Wow! Terabyte level
Wow! Terabyte level
Posts: 4917
Joined: Mon Oct 02, 2006 11:37 am
Academic status: Alumnus/a
Location: στη φωλιά μου κοιτώντας ένα χωράφι με στάρι...

Some open problems from FOCS2009

Post by sandra » Tue Nov 10, 2009 8:06 pm

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. ... focs-2009/

Βρήκα αυτό το άρθρο για κάποια ανοιχτα προβλήματα που ενδιαφέρουν τον blogger. Δεν είχα υπόψιν μου το FOCS ούτε ότι τα συγκεντρώνουν κάθε χρόνο.
Από εδώ κι εμπρός θα είσαι για πάντα υπεύθυνος για εκείνο που έχεις ημερώσει.
Είσαι υπεύθυνος για το τριαντάφυλλο σου...
User avatar
Mbyte level
Mbyte level
Posts: 984
Joined: Sat Sep 24, 2005 1:07 am
Academic status: Alumnus/a
Location: Running from the weak side to the low post

Re: Some open problems from FOCS2009

Post by Theofaman » Sun Nov 15, 2009 7:54 pm

Millennium Problems

In order to celebrate mathematics in the new millennium, The Clay Mathematics Institute of Cambridge, Massachusetts (CMI) has named seven Prize Problems. The Scientific Advisory Board of CMI selected these problems, focusing on important classic questions that have resisted solution over the years. The Board of Directors of CMI designated a $7 million prize fund for the solution to these problems, with $1 million allocated to each.
Theo(pame na)fam(e mprizoles)an!
Post Reply

Return to “Ακαδημαϊκά Νέα”