Having problems with message search?
- Accepted Papers
- Accepted Papers with Abstracts
- Accepted Papers with available PDF links (Shiva Kintali)
- Algorithmic Game Theory (Noam Nisan)
- Geometry and Topology (Jeff Erickson)
- Streaming (Muthu Muthukrishnan)
Here are a few of the many interesting looking papers that caught my eye.
- David Doty. Randomized Self-Assembly for Exact Shapes
- You just don't see many STOC/FOCS papers on self-assembly or from Iowa State.
- Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco Servedio and Emanuele Viola. Bounded Independence Fools Halfspaces
- I like results that just sound neat and can be fully stated in the title.
- Zeev Dvir, Swastik Kopparty, Shubhangi Saraf and Madhu Sudan. Extensions to the Method of Multiplicities, with applications to Kakeya sets and Mergers
- And better randomness extractors too.
- Or Meir. Combinatorial PCPs with efficient verifiers
- Sounds interesting and the only FOCS paper that cites one of my papers in the abstract.
- Rahul Jain, Sarvagya Upadhyay and John Watrous. Two-message quantum interactive proofs are in PSPACE
- QIP is known to sit in between PSPACE and EXP and it's an interesting open question which way it goes. This paper makes some progress in resolving that.
- Neeraj Kayal and Shubhangi Saraf. Blackbox Polynomial Identity Testing for Depth 3 Circuit
- Makes progress on deterministic polynomial identity testing, one of the few remaining probabilistic algorithms to derandomize.
- Ravindran Kannan. A new probability inequality using typical moments and concentration results
- Looks like something we will all need to add to our toolboxes. The accepted papers list dropped the word "inequality" which made the paper seem unreal.
- Alexander Sherstov. The Intersection of Two Halfspaces Has High Threshold Degree
- An exciting result in its own right. The Complexity class analogue goes the other way: Beigel, Reingold and Spielman showed the class PP is closed under intersections.
--
Posted By Lance to Computational Complexity at 7/03/2009 06:35:00 AM
Offline 
Send Email