default search action
48th 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, ISBN 978-0-7695-3010-9
Tutorials
- Terence Tao:
Structure and Randomness in Combinatorics. 3-15 - Dan Boneh:
A Brief Look at Pairings Based Cryptography. 19-26 - Daniel A. Spielman:
Spectral Graph Theory and its Applications. 29-38
Regular Papers
- Andrej Bogdanov, Emanuele Viola:
Pseudorandom Bits for Polynomials. 41-51 - Zeev Dvir, Ariel Gabizon, Avi Wigderson:
Extractors and Rank Extractors for Polynomial Sources. 52-62 - Louay Bazzi:
Polylogarithmic Independence Can Fool DNF Formulas. 63-73 - Qi Cheng:
Derandomization of Sparse Cyclotomic Integer Zero Testing. 74-80 - Constantinos Daskalakis, Christos H. Papadimitriou:
Computing Equilibria in Anonymous Games. 83-93 - Frank McSherry, Kunal Talwar:
Mechanism Design via Differential Privacy. 94-103 - Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Kunal Talwar:
Balloon Popping With Applications to Ascending Auctions. 104-112 - Kousha Etessami, Mihalis Yannakakis:
On the Complexity of Nash Equilibria and Other Fixed Points (Extended Abstract). 113-123 - Xi Chen, Shang-Hua Teng:
Paths Beyond Local Search: A Tight Bound for Randomized Fixed-Point Computation. 124-134 - Philipp Hertel, Toniann Pitassi:
Exponential Time/Space Speedups for Resolution and the PSPACE-completeness of Black-White Pebbling. 137-149 - Stefan S. Dantchev, Barnaby Martin
, Stefan Szeider:
Parameterized Proof Complexity. 150-160 - Eyal Lubetzky, Uri Stav:
Non-Linear Index Coding Outperforming the Linear Optimum. 161-168 - Dániel Marx:
Can you beat treewidth? 169-179 - Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda:
Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. 183-193 - Antoine Gerschenfeld, Andrea Montanari:
Reconstruction for Models on Random Graphs. 194-204 - Yun Long, Asaf Nachmias, Yuval Peres:
Mixing Time Power Laws at Criticality. 205-214 - Jeong Han Kim, Ravi Montenegro, Prasad Tetali:
Near Optimal Bounds for Collision in Pollard Rho for Discrete Log. 215-223 - Stefan Dziembowski
Intrusion-Resilient Secret Sharing. 227-237 - Nishanth Chandran, Vipul Goyal, Rafail Ostrovsky, Amit Sahai:
Covert Multi-Party Computation. 238-248 - Ran Canetti, Rafael Pass, Abhi Shelat:
Cryptography from Sunspots: How to Use an Imperfect Reference String. 249-259 - Mihai Patrascu, Mikkel Thorup:
Planning for Fast Connectivity Updates. 263-271 - Guy E. Blelloch, Daniel Golovin:
Strongly History-Independent Hashing with Applications. 272-282 - Vladimir Braverman, Rafail Ostrovsky:
Smooth Histograms for Sliding Windows. 283-293 - Anna Gál, Parikshit Gopalan:
Lower Bounds on Streaming Algorithms for Approximating the Length of the Longest Increasing Subsequence. 294-304 - Per Austrin:
Towards Sharp Inapproximability For Any 2-CSP. 307-317 - Subhash Khot, Assaf Naor:
Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. 318-328 - Christoph Ambühl, Monaldo Mastrolilli, Ola Svensson:
Inapproximability Results for Sparsest Cut, Optimal Linear Arrangement, and Precedence Constrained Scheduling. 329-337 - Dániel Marx:
On the Optimality of Planar and Geometric Approximation Schemes. 338-348 - Parikshit Gopalan, Subhash Khot, Rishi Saket:
Hardness of Reconstructing Multivariate Polynomials over Finite Fields. 349-359 - 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 - Dorit Aharonov, Daniel Gottesman, Sandy Irani, Julia Kempe:
The Power of Quantum Systems on a Line. 373-383 - Oded Regev, Ben Toner:
Simulating Quantum Correlations with Finite Communication. 384-394 - Andrew M. Childs, Leonard J. Schulman, Umesh V. Vazirani:
Quantum Algorithms for Hidden Nonlinear Structures. 395-404 - Uriel Feige:
Refuting Smoothed 3CNF Formulas. 407-417 - Andrej Bogdanov, Muli Safra
Hardness Amplification for Errorless Heuristics. 418-426 - Emanuele Viola, Avi Wigderson:
One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. 427-437 - Ran Raz
A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. 438-448 - Arkadev Chattopadhyay:
Discrepancy and the Power of Bottom Fan-in in Depth-three Circuits. 449-458 - Uriel Feige, Vahab S. Mirrokni, Jan Vondrák:
Maximizing Non-Monotone Submodular Functions. 461-471 - Jonathan A. Kelner, Evdokia Nikolova
On the Hardness and Smoothed Complexity of Quasi-Concave Minimization. 472-482 - Sudipto Guha, Kamesh Munagala:
Approximation Algorithms for Partial-Information Based Stochastic Control with Markovian Rewards. 483-493 - Christos Koufogiannakis, Neal E. Young:
Beating Simplex for Fractional Packing and Covering Linear Programs. 494-504 - Nikhil Bansal, Niv Buchbinder, Joseph Naor:
A Primal-Dual Randomized Algorithm for Weighted Paging. 507-517 - Noga Alon, Michael R. Capalbo:
Finding Disjoint Paths in Expanders Deterministically and Online. 518-524 - Esther Ezra, Micha Sharir:
Almost Tight Bound for the Union of Fat Tetrahedra in Three Dimensions. 525-535 - Paul Bendich, David Cohen-Steiner, Herbert Edelsbrunner, John Harer, Dmitriy Morozov:
Inferring Local Homology from Sampled Stratified Spaces. 536-546 - Ilias Diakonikolas, Homin K. Lee, Kevin Matulef, Krzysztof Onak, Ronitt Rubinfeld, Rocco A. Servedio, Andrew Wan:
Testing for Concise Representations. 549-558 - Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith:
Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. 559-569 - Artur Czumaj, Christian Sohler
Testing Expansion in Bounded-Degree Graphs. 570-578 - Eldar Fischer, Arie Matsliah, Asaf Shapira:
Approximate Hypergraph Partitioning and Applications. 579-589 - Tali Kaufman, Madhu Sudan:
Sparse Random Linear Codes are Locally Decodable and Testable. 590-600 - Naveen Garg, Amit Kumar:
Minimizing Average Flow-time : Upper and Lower Bounds. 603-613 - Nikhil Bansal, Ho-Leung Chan, Rohit Khandekar, Kirk Pruhs, Clifford Stein, Baruch Schieber:
Non-Preemptive Min-Sum Scheduling with Resource Augmentation. 614-624 - Moses Charikar, Konstantin Makarychev, Yury Makarychev:
On the Advantage over Random for Maximum Acyclic Subgraph. 625-633 - Spyridon Antonakopoulos, Chandra Chekuri, F. Bruce Shepherd, Lisa Zhang:
Buy-at-Bulk Network Design with Protection. 634-644 - Dan Boneh, Craig Gentry, Michael Hamburg:
Space-Efficient Identity Based Encryption Without Pairings. 647-657 - Juan A. Garay, Jonathan Katz, Chiu-Yuen Koo, Rafail Ostrovsky:
Round Complexity of Authenticated Broadcast with a Dishonest Majority. 658-668 - 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 - Boaz Barak, Mohammad Mahmoody-Ghidary:
Lower Bounds on Signatures From Symmetric Primitives. 680-688 - Eden Chlamtac:
Approximation Algorithms Using Hierarchies of Semidefinite Programming Relaxations. 691-701 - 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 - Moses Charikar, Konstantin Makarychev, Yury Makarychev:
Local Global Tradeoffs in Metric Embeddings. 713-723 - Alexandr Andoni, Robert Krauthgamer:
The Computational Hardness of Estimating Edit Distance [Extended Abstract]. 724-734
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-24 17:03 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: