default search action
44th FOCS 2003: Cambridge, MA, USA
- 44th Symposium on Foundations of Computer Science (FOCS 2003), 11-14 October 2003, Cambridge, MA, USA, 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
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
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
Locally Testable Cyclic Codes. 116-125 - Luca Trevisan
List-Decoding Using The XOR Lemma. 126-135 - Elchanan Mossel, Amir Shpilka
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
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
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
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
Logics for Reasoning about Cryptographic Constructions. 372-383 - Boaz Barak, Yehuda Lindell
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
Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds. 404-413
Session 10
- Daniel A. Spielman
Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m1.31). 416-427 - Amos Beimel
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
Average Case and Smoothed Competitive Analysis of the Multi-Level Feedback Algorithm. 462-471 - Aris Anagnostopoulos
Stability and Efficiency of a Random Local Load Balancing Protocol. 472-481 - David Kempe, Alin Dobra
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
On the Impossibility of Dimension Reduction in l1. 514-523 - Moses Charikar
Clustering with Qualitative Information. 524-533 - Anupam Gupta, Robert Krauthgamer
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
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 2024-11-13 23:36 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: