| [1] |
Scott Aaronson and Avi Wigderson. Algebrization: a new barrier in complexity theory. In STOC, pages 731-740, 2008. [ doi ] |
| [2] |
Eric Allender. Chipping away at p vs np: How far are we from proving circuit size lower bounds? In CATS, page 3, 2008. [ doi ] |
| [3] |
Eric Allender and Michal Koucký. Amplifying lower bounds by means of self-reducibility. In IEEE Conference on Computational Complexity, pages 31-40, 2008. [ doi ] |
| [4] |
Sanjeev Arora, Subhash Khot, Alexandra Kolla, David Steurer, Madhur Tulsiani, and Nisheeth K. Vishnoi. Unique games on expanding constraint graphs are easy: extended abstract. In STOC, pages 21-28, 2008. [ doi ] |
| [5] |
Kooshiar Azimian and Mario Szegedy. Parallel repetition of the odd cycle game. In LATIN, pages 676-686, 2008. [ doi ] |
| [6] |
Boaz Barak, Sharon Goldberg, and David Xiao. Protocols and lower bounds for failure localization in the internet. In EUROCRYPT, pages 341-360, 2008. [ doi ] |
| [7] |
Markus Bläser, Moritz Hardt, and David Steurer. Asymptotically optimal hitting sets against polynomials. In ICALP (1), pages 345-356, 2008. [ doi ] |
| [8] |
Guy E. Blelloch, Daniel Golovin, and Virginia Vassilevska. Uniquely represented data structures for computational geometry. In SWAT, pages 17-28, 2008. [ doi ] |
| [9] |
Guy E. Blelloch, Virginia Vassilevska, and Ryan Williams. A new combinatorial approach for sparse graph problems. In ICALP (1), pages 108-120, 2008. [ doi ] |
| [10] |
Moses Charikar, Howard J. Karloff, Claire Mathieu, Joseph Naor, and Michael E. Saks. Online multicast with egalitarian cost sharing. In SPAA, pages 70-76, 2008. [ doi ] |
| [11] |
Bernard Chazelle and Wolfgang Johann Heinrich Mulzer. Markov incremental constructions. In Symposium on Computational Geometry, pages 156-163, 2008. [ doi ] |
| [12] |
Xiaomin Chen, János Pach, Mario Szegedy, and Gábor Tardos. Delaunay graphs of point sets in the plane with respect to axis-parallel rectangles. In SODA, pages 94-101, 2008. [ doi ] |
| [13] |
Wei Dong, Moses Charikar, and Kai Li. Asymmetric distance estimation with sketches for similarity search in high-dimensional spaces. In SIGIR, pages 123-130, 2008. [ doi ] |
| [14] |
Zeev Dvir and Amir Shpilka. Noisy interpolating sets for low degree polynomials. In IEEE Conference on Computational Complexity, pages 140-148, 2008. [ doi ] |
| [15] |
Zeev Dvir, Amir Shpilka, and Amir Yehudayoff. Hardness-randomness tradeoffs for bounded depth arithmetic circuits. In STOC, pages 741-748, 2008. [ doi ] |
| [16] |
Alina Ene, William Horne, Nikola Milosavljevic, Prasad Rao, Robert Schreiber, and Robert Endre Tarjan. Fast exact and heuristic methods for role minimization problems. In SACMAT, pages 1-10, 2008. [ doi ] |
| [17] |
Sharon Goldberg, David Xiao, Eran Tromer, Boaz Barak, and Jennifer Rexford. Path-quality monitoring in the presence of adversaries. In SIGMETRICS, pages 193-204, 2008. [ doi ] |
| [18] |
Venkatesan Guruswami, James R. Lee, and Avi Wigderson. Euclidean sections of with sublinear randomness and error-correction over the reals. In APPROX-RANDOM, pages 444-454, 2008. [ doi ] |
| [19] |
Bernhard Haeupler, Telikepalli Kavitha, Rogers Mathew, Siddhartha Sen, and Robert Endre Tarjan. Faster algorithms for incremental topological ordering. In ICALP (1), pages 421-433, 2008. [ doi ] |
| [20] |
Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder. Trace reconstruction with constant deletion probability and related results. In SODA, pages 389-398, 2008. [ doi ] |
| [21] |
Russell Impagliazzo, Ragesh Jaiswal, Valentine Kabanets, and Avi Wigderson. Uniform direct product theorems: simplified, optimized, and derandomized. In STOC, pages 579-588, 2008. [ doi ] |
| [22] |
Subhash Khot and Ashok Kumar Ponnuswami. Minimizing wide range regret with time selection functions. In COLT, pages 81-86, 2008. [ doi ] |
| [23] |
Subhash Khot and Rishi Saket. On hardness of learning intersection of two halfspaces. In STOC, pages 345-354, 2008. [ doi ] |
| [24] |
Guy Kindler, Assaf Naor, and Gideon Schechtman. The ugc hardness threshold of the ℓ grothendieck problem. In SODA, pages 64-73, 2008. [ doi ] |
| [25] |
Troy Lee and Rajat Mittal. Product theorems via semidefinite programming. In ICALP (1), pages 674-685, 2008. [ doi ] |
| [26] |
Rajsekar Manokaran, Joseph Naor, Prasad Raghavendra, and Roy Schwartz. Sdp gaps and ugc hardness for multiway cut, 0-extension, and metric labeling. In STOC, pages 11-20, 2008. [ doi ] |
| [27] |
Manor Mendel and Assaf Naor. Markov convexity and local rigidity of distorted metrics. In Symposium on Computational Geometry, pages 49-58, 2008. [ doi ] |
| [28] |
Ran Raz and Amir Yehudayoff. Lower bounds and separations for constant depth multilinear circuits. In IEEE Conference on Computational Complexity, pages 128-139, 2008. [ doi ] |
| [29] |
Michael E. Saks and C. Seshadhri. Parallel monotonicity reconstruction. In SODA, pages 962-971, 2008. [ doi ] |
| [30] |
Virginia Vassilevska. Nondecreasing paths in a weighted graph or: how to optimally read a train schedule. In SODA, pages 465-472, 2008. [ doi ] |
| [31] |
Avi Wigderson. Randomness – a computational complexity perspective. In CSR, pages 1-2, 2008. [ doi ] |
