default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID44th FOCS 2003: Cambridge, MA, USA
- 44th Symposium on Foundations of Computer Science, FOCS 2003, Cambridge, MA, USA, October 11-14, 2003, Proceedings. IEEE Computer Society 2003, ISBN 0-7695-2040-5
Tutorial 1
- Avrim Blum:
Machine Learning: My Favorite Results, Directions, and Open Problems. 2-
Tutorial 2
- Dana Randall:
Mixing. 4-15
Tutorial 3
- Eli Upfal
:
Performance Analysis of Dynamic Network Processes. 18
Session 1
- Gérard Cornuéjols, Xinming Liu, Kristina Vuskovic:
A Polynomial Algorithm for Recognizing Perfect Graphs. 20-27 - Milena Mihail, Christos H. Papadimitriou, Amin Saberi:
On Certain Connectivity Properties of the Internet Topology. 28-35 - Kamalika Chaudhuri, Brighten Godfrey, Satish Rao, Kunal Talwar:
Paths, Trees, and Minimum Latency Tours. 36-45 - Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, Maria Minkoff:
Approximation Algorithms for Orienteering and Discounted-Reward TSP. 46-55 - Haim Kaplan, Moshe Lewenstein, Nira Shafrir, Maxim Sviridenko:
Approximation Algorithms for Asymmetric TSP by Decomposing Directed Regular Multigraphs. 56-65
Session 2
- Oded Goldreich, Shafi Goldwasser, Asaf Nussboim:
On the Implementation of Huge Random Objects. 68-79 - Silvio Micali, Michael O. Rabin, Joe Kilian:
Zero-Knowledge Sets. 80-91 - Jesse Kamp, David Zuckerman:
Deterministic Extractors for Bit-Fixing Sources and Exposure-Resilient Cryptography. 92-101 - Shafi Goldwasser, Yael Tauman Kalai:
On the (In)security of the Fiat-Shamir Paradigm. 102-113
Session 3
- László Babai, Amir Shpilka, Daniel Stefankovic:
Locally Testable Cyclic Codes. 116-125 - Luca Trevisan:
List-Decoding Using The XOR Lemma. 126-135 - Elchanan Mossel, Amir Shpilka, Luca Trevisan:
On e-Biased Generators in NC0. 136-145 - Adi Akavia, Shafi Goldwasser, Shmuel Safra:
Proving Hard-Core Predicates Using List Decoding. 146-157
Session 4
- Rajat Bhattacharjee, Ashish Goel:
Instability of FIFO at Arbitrarily Low Rates in the Adversarial Queueing Model. 160-167 - Chandra Nair, Balaji Prabhakar, Mayank Sharma:
Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem. 168-178 - Alon Orlitsky, Narayana P. Santhanam, Junan Zhang:
Always Good Turing: Asymptotically Optimal Probability Estimation. 179-188 - Nader H. Bshouty, Elchanan Mossel, Ryan O'Donnell, Rocco A. Servedio:
Learning DNF from Random Walks. 189-198
Session 5
- Scott Aaronson, Andris Ambainis:
Quantum Search of Spatial Regions. 200-209 - Dorit Aharonov, Oded Regev:
A Lattice Problem in Quantum NP. 210-219 - Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen:
A Lower Bound for the Bounded Round Quantum Communication Complexity of Set Disjointness. 220-229 - Andris Ambainis:
Polynomial Degree vs. Quantum Query Complexity. 230-239
Session 6
- Gianni Franceschini, Viliam Geffert:
An In-Place Sorting with O(n log n) Comparisons and O(n) Moves. 242-250 - Wing-Kai Hon, Kunihiko Sadakane, Wing-Kin Sung:
Breaking a Time-and-Space Barrier in Constructing Full-Text Indices. 251-260 - Lars Arge, Norbert Zeh:
I/O-Efficient Strong Connectivity and Depth-First Search for Directed Planar Graphs. 261-270 - Michael A. Bender, Gerth Stølting Brodal, Rolf Fagerberg, Dongdong Ge, Simai He, Haodong Hu, John Iacono, Alejandro López-Ortiz:
The Cost of Cache-Oblivious Searching. 271-282 - Piotr Indyk, David P. Woodruff:
Tight Lower Bounds for the Distinct Elements Problem. 283-288
Session 7
- Subhash Khot:
Hardness of Approximating the Shortest Vector Problem in High Lp Norms. 290-297 - Michael Alekhnovich:
More on Average Case vs Approximation Complexity. 298-307 - Andrej Bogdanov, Luca Trevisan:
On Worst-Case to Average-Case Reductions for NP Problems. 308-317 - Josh Buresh-Oppenheim, Nicola Galesi, Shlomo Hoory, Avner Magen, Toniann Pitassi:
Rank Bounds and Integrality Gaps for Cutting Planes Procedures Joshua. 318-327
Session 8
- Michael Molloy, Mohammad R. Salavatipour:
The Resolution Complexity of Random Constraint Satisfaction Problems. 330-339 - Fahiem Bacchus, Shannon Dalmao, Toniann Pitassi:
Algorithms and Complexity Results for #SAT and Bayesian Inference. 340-351 - Michael Alekhnovich, Eli Ben-Sasson:
Linear Upper Bounds for Random Walk on Small Density Random 3-CNF. 352-361 - Dimitris Achlioptas, Assaf Naor, Yuval Peres:
On the Maximum Satisfiability of Random Formulas. 362-370
Session 9
- Russell Impagliazzo, Bruce M. Kapron:
Logics for Reasoning about Cryptographic Constructions. 372-383 - Boaz Barak, Yehuda Lindell, Salil P. Vadhan:
Lower Bounds for Non-Black-Box Zero Knowledge. 384-393 - Yehuda Lindell:
General Composition and Universal Composability in Secure Multi-Party Computation. 394-403 - Rafael Pass, Alon Rosen:
Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds. 404-413
Session 10
- Daniel A. Spielman, Shang-Hua Teng:
Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m1.31). 416-427 - Amos Beimel, Enav Weinreb:
Separating the Power of Monotone Span Programs over Different Fields. 428-437 - Henry Cohn, Christopher Umans:
A Group-Theoretic Approach to Fast Matrix Multiplication. 438-449 - Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
Symmetric Polynomials over Zm and Simultaneous Communication Protocol. 450-459
Session 11
- Luca Becchetti, Stefano Leonardi, Alberto Marchetti-Spaccamela, Guido Schäfer, Tjark Vredeveld:
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. 462-471 - Aris Anagnostopoulos, Adam Kirsch, Eli Upfal:
Stability and Efficiency of a Random Local Load Balancing Protocol. 472-481 - David Kempe, Alin Dobra, Johannes Gehrke:
Gossip-Based Computation of Aggregate Information. 482-491 - Artur Czumaj, Wojciech Rytter:
Broadcasting Algorithms in Radio Networks with Unknown Topology. 492-501 - Gagan Aggarwal, Rajeev Motwani, Devavrat Shah, An Zhu:
Switch Scheduling via Randomized Edge Coloring. 502-512
Session 12
- Bo Brinkman, Moses Charikar:
On the Impossibility of Dimension Reduction in l1. 514-523 - Moses Charikar, Venkatesan Guruswami, Anthony Wirth:
Clustering with Qualitative Information. 524-533 - Anupam Gupta, Robert Krauthgamer, James R. Lee:
Bounded Geometries, Fractals, and Low-Distortion Embeddings. 534-543 - Timothy M. Chan:
On Levels in Arrangements of Curves, II: A Simple Inequality and Its Consequences. 544-550
Session 13
- Martin Grohe:
The Complexity of Homomorphism and Constraint Satisfaction Problems Seen from the Other Side. 552-561 - Andrei A. Bulatov, Víctor Dalmau:
Towards a Dichotomy Theorem for the Counting Constraint Satisfaction Problem. 562-571
Session 14
- Ron Lavi, Ahuva Mu'alem, Noam Nisan:
Towards a Characterization of Truthful Combinatorial Auctions. 574-583 - Martin Pál, Éva Tardos:
Group Strategyproof Mechanisms via Primal-Dual Algorithms. 584-593 - Robert D. Kleinberg, Frank Thomson Leighton:
The Value of Knowing a Demand Curve: Bounds on Regret for Online Posted-Price Auctions. 594-605 - Anupam Gupta, Amit Kumar, Martin Pál, Tim Roughgarden:
Approximation Via Cost-Sharing: A Simple Approximation Algorithm for the Multicommodity Rent-or-Buy Problem. 606-615
Session 15
- Thomas P. Hayes, Eric Vigoda:
A Non-Markovian Coupling for Randomly Sampling Colorings. 618-627 - Fabio Martinelli, Alistair Sinclair, Dror Weitz:
The Ising Model on Trees: Boundary Conditions and Mixing Time. 628-639 - László Lovász, Santosh S. Vempala:
Logconcave Functions: Geometry and Efficient Sampling Algorithms. 640-649 - László Lovász, Santosh S. Vempala:
Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm. 650-659
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-12-12 23:04 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:
