Conferences in DBLP
Moses Charikar , Sudipto Guha , Éva Tardos , David B. Shmoys A Constant-Factor Approximation Algorithm for the k -Median Problem (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Kevin D. Wayne A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow. [Citation Graph (0, 0)][DBLP ] Conf ] Venkatesan Guruswami , Sanjeev Khanna , Rajmohan Rajaraman , F. Bruce Shepherd , Mihalis Yannakakis Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Irit Dinur , Eldar Fischer , Guy Kindler , Ran Raz , Shmuel Safra PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. [Citation Graph (0, 0)][DBLP ] Conf ] Funda Ergün , Ravi Kumar , Ronitt Rubinfeld Fast Approximate PCPs. [Citation Graph (0, 0)][DBLP ] Conf ] Marcos A. Kiwi , Frédéric Magniez , Miklos Santha Approximate Testing with Relative Error. [Citation Graph (0, 0)][DBLP ] Conf ] Uri Zwick All Pairs Lightest Shortest Paths. [Citation Graph (0, 0)][DBLP ] Conf ] Harold N. Gabow , Haim Kaplan , Robert Endre Tarjan Unique Maximum Matching Algorithms. [Citation Graph (0, 0)][DBLP ] Conf ] Yuval Ishai , Eyal Kushilevitz Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Amos Beimel , Yuval Ishai , Eyal Kushilevitz , Tal Malkin One-Way Functions Are Essential for Single-Server Private Information Retrieval. [Citation Graph (0, 0)][DBLP ] Conf ] Moses Charikar , Ravi Kumar , Prabhakar Raghavan , Sridhar Rajagopalan , Andrew Tomkins On targeting Markov segments. [Citation Graph (0, 0)][DBLP ] Conf ] Edith Cohen , Haim Kaplan Exploiting Regularities in Web Traffic Patterns for Cache Replacement. [Citation Graph (0, 0)][DBLP ] Conf ] Gen-Huey Chen , Ming-Yang Kao , Yuh-Dauh Lyuu , Hsing-Kuo Wong Optimal Buy-and-Hold Strategies for Financial Markets with Bounded Daily Returns. [Citation Graph (0, 0)][DBLP ] Conf ] Noam Nisan , Amir Ronen Algorithmic Mechanism Design (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Luca Trevisan Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Ran Raz , Omer Reingold , Salil P. Vadhan Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. [Citation Graph (0, 0)][DBLP ] Conf ] Ran Raz , Omer Reingold On Recycling the Randomness of States in Space Bounded Computation. [Citation Graph (0, 0)][DBLP ] Conf ] Giovanni Di Crescenzo , Russell Impagliazzo Security-Preserving Hardness-Amplification for Any Regular One-Way Function. [Citation Graph (0, 0)][DBLP ] Conf ] Jeff Edmonds Scheduling in the Dark. [Citation Graph (0, 0)][DBLP ] Conf ] Ashish Goel , Monika Rauch Henzinger , Serge A. Plotkin , Éva Tardos Scheduling Data Transfers in a Network and the Set Scheduling Problem. [Citation Graph (0, 0)][DBLP ] Conf ] Baruch Awerbuch , Yossi Azar , Stefano Leonardi , Oded Regev Minimizing the Flow Time Without Migration. [Citation Graph (0, 0)][DBLP ] Conf ] David Gamarnik Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. [Citation Graph (0, 0)][DBLP ] Conf ] Christian Scheideler , Berthold Vöcking From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols. [Citation Graph (0, 0)][DBLP ] Conf ] Oded Goldreich , Dana Ron , Madhu Sudan Chinese Remaindering with Errors. [Citation Graph (0, 0)][DBLP ] Conf ] Vadim Olshevsky , Mohammad Amin Shokrollahi A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes. [Citation Graph (0, 0)][DBLP ] Conf ] Moni Naor , Benny Pinkas Oblivious Transfer and Polynomial Evaluation. [Citation Graph (0, 0)][DBLP ] Conf ] Ran Canetti , Rafail Ostrovsky Secure Computation with Honest-Looking Parties: What If Nobody Is Truly Honest? (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Yefim Dinitz , Shlomo Moran , Sergio Rajsbaum Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Fang Chen , László Lovász , Igor Pak Lifting Markov Chains to Speed up Mixing. [Citation Graph (0, 0)][DBLP ] Conf ] László Lovász , Ravi Kannan Faster Mixing via Average Conductance. [Citation Graph (0, 0)][DBLP ] Conf ] Leonard J. Schulman , Vijay V. Vazirani Majorizing Estimators and the Approximation of #P-Complete Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Paul Beame , Faith E. Fich Optimal Bounds for the Predecessor Problem. [Citation Graph (0, 0)][DBLP ] Conf ] Amit Chakrabarti , Bernard Chazelle , Benjamin Gum , Alexey Lvov A Lower Bound on the Complexity of Approximate Nearest-Neighbor Searching on the Hamming Cube. [Citation Graph (0, 0)][DBLP ] Conf ] Allan Borodin , Rafail Ostrovsky , Yuval Rabani Lower Bounds for High Dimensional Nearest Neighbor Search and Related Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Leonard J. Schulman , Umesh V. Vazirani Molecular Scale Heat Engines and Scalable Quantum Computation. [Citation Graph (0, 0)][DBLP ] Conf ] Lisa Hales , Sean Hallgren Quantum Fourier Sampling Simplified. [Citation Graph (0, 0)][DBLP ] Conf ] Alexander Russell , Michael E. Saks , David Zuckerman Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. [Citation Graph (0, 0)][DBLP ] Conf ] Anna Gál , Adi Rosén A Theorem on Sensitivity and Applications in Private Computation. [Citation Graph (0, 0)][DBLP ] Conf ] Ran Raz Exponential Separation of Quantum and Classical Communication Complexity. [Citation Graph (0, 0)][DBLP ] Conf ] Masami Amano , Kazuo Iwama Undecidability on Quantum Finite Automata. [Citation Graph (0, 0)][DBLP ] Conf ] Andris Ambainis , Ashwin Nayak , Amnon Ta-Shma , Umesh V. Vazirani Dense Quantum Coding and a Lower Bound for 1-Way Quantum Automata. [Citation Graph (0, 0)][DBLP ] Conf ] Ashwin Nayak , Felix Wu The Quantum Query Complexity of Approximating the Median and Related Statistics. [Citation Graph (0, 0)][DBLP ] Conf ] Klaus Jansen , Roberto Solis-Oba , Maxim Sviridenko Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme. [Citation Graph (0, 0)][DBLP ] Conf ] Martin Skutella , Gerhard J. Woeginger A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines. [Citation Graph (0, 0)][DBLP ] Conf ] Klaus Jansen , Lorant Porkolab Improved Approximation Schemes for Scheduling Unrelated Parallel Machines. [Citation Graph (0, 0)][DBLP ] Conf ] Jianer Chen , Antonio Miranda A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Piotr Indyk Sublinear Time Algorithms for Metric Space Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Allan Borodin , Rafail Ostrovsky , Yuval Rabani Subquadratic Approximation Algorithms for Clustering Problems in High Dimensional Spaces. [Citation Graph (0, 0)][DBLP ] Conf ] V. S. Anil Kumar , H. Ramesh Covering Rectilinear Polygons with Axis-Parallel Rectangles. [Citation Graph (0, 0)][DBLP ] Conf ] S. Muthukrishnan , Mike Paterson , Süleyman Cenk Sahinalp , Torsten Suel Compact Grid Layouts of Multi-Level Networks. [Citation Graph (0, 0)][DBLP ] Conf ] Tomás Feder , Pavol Hell , Sulamita Klein , Rajeev Motwani Complexity of Graph Partition Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Ming Li , Bin Ma , Lusheng Wang Finding Similar Regions in Many Strings. [Citation Graph (0, 0)][DBLP ] Conf ] Paolo Ferragina , S. Muthukrishnan , Mark de Berg Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Valerie King , Garry Sagert A Fully Dynamic Algorithm for Maintaining the Transitive Closure. [Citation Graph (0, 0)][DBLP ] Conf ] Stephen Alstrup , Amir M. Ben-Amram , Theis Rauhe Worst-Case and Amortised Optimality in Union-Find (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Victor Y. Pan , Zhao Q. Chen The Complexity of the Matrix Eigenproblem. [Citation Graph (0, 0)][DBLP ] Conf ] Eli Ben-Sasson , Avi Wigderson Short Proofs are Narrow - Resolution Made Simple. [Citation Graph (0, 0)][DBLP ] Conf ] J. Maurice Rojas On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Madhu Sudan , Luca Trevisan , Salil P. Vadhan Pseudorandom Generators Without the XOR Lemma (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Samuel R. Buss , Dima Grigoriev , Russell Impagliazzo , Toniann Pitassi Linear Gaps Between Degrees for the Polynomial Calculus Modulo Distinct Primes. [Citation Graph (0, 0)][DBLP ] Conf ] Matthew Andrews , Lisa Zhang Packet Routing with Arbitrary End-to-End Delay Requirements. [Citation Graph (0, 0)][DBLP ] Conf ] Gopal Pandurangan , Eli Upfal Static and Dynamic Evaluation of QoS Properties. [Citation Graph (0, 0)][DBLP ] Conf ] Sudipto Guha , Anna Moss , Joseph Naor , Baruch Schieber Efficient Recovery from Power Outage (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Uriel Feige Nonmonotonic Phenomena in Packet Routing. [Citation Graph (0, 0)][DBLP ] Conf ] Marcus Schaefer Graph Ramsey Theory and the Polynomial Hierarchy. [Citation Graph (0, 0)][DBLP ] Conf ] Stephen Ponzio , Jaikumar Radhakrishnan , Srinivasan Venkatesh The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. [Citation Graph (0, 0)][DBLP ] Conf ] Edith Cohen , Haim Kaplan , Uri Zwick Connection Caching. [Citation Graph (0, 0)][DBLP ] Conf ] Amotz Bar-Noy , Sudipto Guha , Joseph Naor , Baruch Schieber Approximating the Throughput of Multiple Machines Under Real-Time Scheduling. [Citation Graph (0, 0)][DBLP ] Conf ] Miklós Ajtai Determinism versus Non-Determinism for Linear Time RAMs (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Leslie G. Valiant Robust Logics. [Citation Graph (0, 0)][DBLP ] Conf ] Eugene M. Luks Hypergraph Isomorphism and Structural Equivalence of Boolean Functions. [Citation Graph (0, 0)][DBLP ] Conf ] Adam Klivans , Dieter van Melkebeek Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. [Citation Graph (0, 0)][DBLP ] Conf ] David R. Karger , Philip N. Klein , Clifford Stein , Mikkel Thorup , Neal E. Young Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. [Citation Graph (0, 0)][DBLP ] Conf ] Uri Zwick Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Sanjeev Arora , George Karakostas Approximation Schemes for Minimum Latency Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Anupam Gupta Embedding Tree Metrics Into Low Dimensional Euclidean Spaces. [Citation Graph (0, 0)][DBLP ] Conf ] Rocco A. Servedio Computational Sample Complexity and Attribute-Efficient Learning. [Citation Graph (0, 0)][DBLP ] Conf ] Johannes Blömer , Jean-Pierre Seifert On the Complexity of Computing Short Linearly Independent Vectors and Short Bases in a Lattice. [Citation Graph (0, 0)][DBLP ] Conf ] Wojciech Plandowski Satisfiability of Word Equations with Constants is in NEXPTIME. [Citation Graph (0, 0)][DBLP ] Conf ] Jin-yi Cai , Ajay Nerurkar , D. Sivakumar Hardness and Hierarchy Theorems for Probabilistic Quasi-Polynomial Time. [Citation Graph (0, 0)][DBLP ] Conf ] Piotr Indyk Inerpolation of Symmetric Functions and a New Type of Combinatorial Design. [Citation Graph (0, 0)][DBLP ] Conf ] Michael R. Capalbo , S. Rao Kosaraju Small Universal Graphs. [Citation Graph (0, 0)][DBLP ] Conf ] Yevgeniy Dodis , Sanjeev Khanna Design Networks with Bounded Pairwise Distance. [Citation Graph (0, 0)][DBLP ] Conf ] Gilles Schaeffer Random Sampling of Large Planar Maps and Convex Polyhedra. [Citation Graph (0, 0)][DBLP ] Conf ] Sanjiv Kapoor Efficient Computation of Geodesic Shortest Paths. [Citation Graph (0, 0)][DBLP ] Conf ] Amir M. Ben-Amram , Holger Petersen Backing Up in Singly Linked Lists. [Citation Graph (0, 0)][DBLP ] Conf ] 