48. FOCS 2007:
Providence,
RI,
USA
48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007), October 20-23, 2007, Providence, RI, USA, Proceedings.
IEEE Computer Society 2007 BibTeX
Tutorials
Regular Papers
- Andrej Bogdanov, Emanuele Viola:
Pseudorandom Bits for Polynomials.
41-51
Electronic Edition (link) BibTeX
- Zeev Dvir, Ariel Gabizon, Avi Wigderson:
Extractors and Rank Extractors for Polynomial Sources.
52-62
Electronic Edition (link) BibTeX
- Louay Bazzi:
Polylogarithmic Independence Can Fool DNF Formulas.
63-73
Electronic Edition (link) BibTeX
- Qi Cheng:
Derandomization of Sparse Cyclotomic Integer Zero Testing.
74-80
Electronic Edition (link) BibTeX
- Constantinos Daskalakis, Christos H. Papadimitriou:
Computing Equilibria in Anonymous Games.
83-93
Electronic Edition (link) BibTeX
- Frank McSherry, Kunal Talwar:
Mechanism Design via Differential Privacy.
94-103
Electronic Edition (link) BibTeX
- Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Kunal Talwar:
Balloon Popping With Applications to Ascending Auctions.
104-112
Electronic Edition (link) BibTeX
- Kousha Etessami, Mihalis Yannakakis:
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract).
113-123
Electronic Edition (link) BibTeX
- Xi Chen, Shang-Hua Teng:
Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation.
124-134
Electronic Edition (link) BibTeX
- Philipp Hertel, Toniann Pitassi:
Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling.
137-149
Electronic Edition (link) BibTeX
- Stefan S. Dantchev, Barnaby Martin, Stefan Szeider:
Parameterized Proof Complexity.
150-160
Electronic Edition (link) BibTeX
- Eyal Lubetzky, Uri Stav:
Non-Linear Index Coding Outperforming the Linear Optimum.
161-168
Electronic Edition (link) BibTeX
- Dániel Marx:
Can you beat treewidth?
169-179
Electronic Edition (link) BibTeX
- Daniel Stefankovic, Santosh Vempala, Eric Vigoda:
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting.
183-193
Electronic Edition (link) BibTeX
- Antoine Gerschenfeld, Andrea Montanari:
Reconstruction for Models on Random Graphs.
194-204
Electronic Edition (link) BibTeX
- Yun Long, Asaf Nachmias, Yuval Peres:
Mixing Time Power Laws at Criticality.
205-214
Electronic Edition (link) BibTeX
- Jeong Han Kim, Ravi Montenegro, Prasad Tetali:
Near Optimal Bounds for Collision in Pollard Rho for Discrete Log.
215-223
Electronic Edition (link) BibTeX
- Stefan Dziembowski, Krzysztof Pietrzak:
Intrusion-Resilient Secret Sharing.
227-237
Electronic Edition (link) BibTeX
- Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai:
Covert Multi-Party Computation.
238-248
Electronic Edition (link) BibTeX
- Ran Canetti, Rafael Pass, Abhi Shelat:
Cryptography from Sunspots: How to Use an Imperfect Reference String.
249-259
Electronic Edition (link) BibTeX
- Mihai Patrascu, Mikkel Thorup:
Planning for Fast Connectivity Updates.
263-271
Electronic Edition (link) BibTeX
- Guy E. Blelloch, Daniel Golovin:
Strongly History-Independent Hashing with Applications.
272-282
Electronic Edition (link) BibTeX
- Vladimir Braverman, Rafail Ostrovsky:
Smooth Histograms for Sliding Windows.
283-293
Electronic Edition (link) BibTeX
- Anna Gál, Parikshit Gopalan:
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence.
294-304
Electronic Edition (link) BibTeX
- Per Austrin:
Towards Sharp Inapproximability For Any 2-CSP.
307-317
Electronic Edition (link) BibTeX
- Subhash Khot, Assaf Naor:
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies.
318-328
Electronic Edition (link) BibTeX
- Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson:
Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling.
329-337
Electronic Edition (link) BibTeX
- Dániel Marx:
On the Optimality of Planar and Geometric Approximation Schemes.
338-348
Electronic Edition (link) BibTeX
- Parikshit Gopalan, Subhash Khot, Rishi Saket:
Hardness of Reconstructing Multivariate Polynomials over Finite Fields.
349-359
Electronic Edition (link) BibTeX
- Andris Ambainis, Andrew M. Childs, Ben Reichardt, Robert Spalek, Shengyu Zhang:
Any AND-OR Formula of Size N can be Evaluated in time N1/2+o(1) on a Quantum Computer.
363-372
Electronic Edition (link) BibTeX
- Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe:
The Power of Quantum Systems on a Line.
373-383
Electronic Edition (link) BibTeX
- Oded Regev, Ben Toner:
Simulating Quantum Correlations with Finite Communication.
384-394
Electronic Edition (link) BibTeX
- Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani:
Quantum Algorithms for Hidden Nonlinear Structures.
395-404
Electronic Edition (link) BibTeX
- Uriel Feige:
Refuting Smoothed 3CNF Formulas.
407-417
Electronic Edition (link) BibTeX
- Andrej Bogdanov, Muli Safra:
Hardness Amplification for Errorless Heuristics.
418-426
Electronic Edition (link) BibTeX
- Emanuele Viola, Avi Wigderson:
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications.
427-437
Electronic Edition (link) BibTeX
- Ran Raz, Amir Shpilka, Amir Yehudayoff:
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits.
438-448
Electronic Edition (link) BibTeX
- Arkadev Chattopadhyay:
Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits.
449-458
Electronic Edition (link) BibTeX
- Uriel Feige, Vahab S. Mirrokni, Jan Vondrák:
Maximizing Non-Monotone Submodular Functions.
461-471
Electronic Edition (link) BibTeX
- Jonathan A. Kelner, Evdokia Nikolova:
On the Hardness and Smoothed Complexity of Quasi-Concave Minimization.
472-482
Electronic Edition (link) BibTeX
- Sudipto Guha, Kamesh Munagala:
Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards.
483-493
Electronic Edition (link) BibTeX
- Christos Koufogiannakis, Neal E. Young:
Beating Simplex for Fractional Packing and Covering Linear Programs.
494-504
Electronic Edition (link) BibTeX
- Nikhil Bansal, Niv Buchbinder, Joseph Naor:
A Primal-Dual Randomized Algorithm for Weighted Paging.
507-517
Electronic Edition (link) BibTeX
- Noga Alon, Michael R. Capalbo:
Finding Disjoint Paths in Expanders Deterministically and Online.
518-524
Electronic Edition (link) BibTeX
- Esther Ezra, Micha Sharir:
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions.
525-535
Electronic Edition (link) BibTeX
- Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov:
Inferring Local Homology from Sampled Stratified Spaces.
536-546
Electronic Edition (link) BibTeX
- Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan:
Testing for Concise Representations.
549-558
Electronic Edition (link) BibTeX
- Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam Smith:
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem.
559-569
Electronic Edition (link) BibTeX
- Artur Czumaj, Christian Sohler:
Testing Expansion in Bounded-Degree Graphs.
570-578
Electronic Edition (link) BibTeX
- Eldar Fischer, Arie Matsliah, Asaf Shapira:
Approximate Hypergraph Partitioning and Applications.
579-589
Electronic Edition (link) BibTeX
- Tali Kaufman, Madhu Sudan:
Sparse Random Linear Codes are Locally Decodable and Testable.
590-600
Electronic Edition (link) BibTeX
- Naveen Garg, Amit Kumar:
Minimizing Average Flow-time : Upper and Lower Bounds.
603-613
Electronic Edition (link) BibTeX
- Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, Baruch Schieber:
Non-Preemptive Min-Sum Scheduling with Resource Augmentation.
614-624
Electronic Edition (link) BibTeX
- Moses Charikar, Konstantin Makarychev, Yury Makarychev:
On the Advantage over Random for Maximum Acyclic Subgraph.
625-633
Electronic Edition (link) BibTeX
- Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang:
Buy-at-Bulk Network Design with Protection.
634-644
Electronic Edition (link) BibTeX
- Dan Boneh, Craig Gentry, Michael Hamburg:
Space-Efficient Identity Based Encryption Without Pairings.
647-657
Electronic Edition (link) BibTeX
- Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky:
Round Complexity of Authenticated Broadcast with a Dishonest Majority.
658-668
Electronic Edition (link) BibTeX
- Iftach Haitner, Jonathan J. Hoch, Omer Reingold, Gil Segev:
Finding Collisions in Interactive Protocols - A Tight Lower Bound on the Round Complexity of Statistically-Hiding Commitments.
669-679
Electronic Edition (link) BibTeX
- Boaz Barak, Mohammad Mahmoody-Ghidary:
Lower Bounds on Signatures From Symmetric Primitives.
680-688
Electronic Edition (link) BibTeX
- Eden Chlamtac:
Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations.
691-701
Electronic Edition (link) BibTeX
- Konstantinos Georgiou, Avner Magen, Toniann Pitassi, Iannis Tourlakis:
Integrality gaps of 2 - o(1) for Vertex Cover SDPs in the Lovész-Schrijver Hierarchy.
702-712
Electronic Edition (link) BibTeX
- Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Local Global Tradeoffs in Metric Embeddings.
713-723
Electronic Edition (link) BibTeX
- Alexandr Andoni, Robert Krauthgamer:
The Computational Hardness of Estimating Edit Distance [Extended Abstract].
724-734
Electronic Edition (link) BibTeX
Copyright © Sat May 16 23:12:28 2009
by Michael Ley (ley@uni-trier.de)
