44. FOCS 2003: Cambridge, MA, USA

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(m^1.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 Z_m 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 l₁. 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 Vempala:
  Logconcave Functions: Geometry and Efficient Sampling Algorithms. 640-649
  
• László Lovász, Santosh Vempala:
  Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm. 650-659
  

Last update Sat May 25 02:54:13 2013 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page