Conferences in DBLP
Oded Goldreich , Shafi Goldwasser On the Limits of Non-Approximability of Lattice Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Miklós Ajtai The Shortest Vector Problem in L2 is NP -hard for Randomized Reductions (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Dorit Aharonov , Alexei Kitaev , Noam Nisan Quantum Circuits with Mixed States. [Citation Graph (0, 0)][DBLP ] Conf ] Mark Huber Exact Sampling and Approximate Counting Techniques. [Citation Graph (0, 0)][DBLP ] Conf ] Assaf Natanzon , Ron Shamir , Roded Sharan A Polynomial Approximation Algorithm for the Minimum Fill-In Problem. [Citation Graph (0, 0)][DBLP ] Conf ] Gruia Calinescu , Howard J. Karloff , Yuval Rabani An Improved Approximation Algorithm for Multiway Cut. [Citation Graph (0, 0)][DBLP ] Conf ] Lov K. Grover A Framework for Fast Quantum Mechanical Algorithms. [Citation Graph (0, 0)][DBLP ] Conf ] Harry Buhrman , Richard Cleve , Avi Wigderson Quantum vs. Classical Communication and Computation. [Citation Graph (0, 0)][DBLP ] Conf ] David R. Karger , Matthew S. Levine Finding Maximum Flows in Undirected Graphs Seems Easier than Bipartite Matching. [Citation Graph (0, 0)][DBLP ] Conf ] Jacob Holm , Kristian de Lichtenberg , Mikkel Thorup Poly-Logarithmic Deterministic Fully-Dynamic Algorithms for Connectivity, Minimum Spanning Tree, 2-Edge, and Biconnectivity. [Citation Graph (1, 0)][DBLP ] Conf ] Uriel Feige Approximating the Bandwidth via Volume Respecting Embeddings (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Avrim Blum , Goran Konjevod , R. Ravi , Santosh Vempala Semi-Definite Relaxations for Minimum Bandwidth and other Vertex-Ordering Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Sanjeev Arora , Prabhakar Raghavan , Satish Rao Approximation Schemes for Euclidean k -Medians and Related Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Moses Charikar , Chandra Chekuri , Ashish Goel , Sudipto Guha Rounding via Trees: Deterministic Approximation Algorithms for Group Steiner Trees and k -Median. [Citation Graph (0, 0)][DBLP ] Conf ] Richard Beigel , Tirza Hirst One Help Bit Doesn't Help. [Citation Graph (0, 0)][DBLP ] Conf ] Ran Canetti , Daniele Micciancio , Omer Reingold Perfectly One-Way Probabilistic Hash Functions (Preliminary Version). [Citation Graph (0, 0)][DBLP ] Conf ] Giovanni Di Crescenzo , Yuval Ishai , Rafail Ostrovsky Non-Interactive and Non-Malleable Commitment. [Citation Graph (0, 0)][DBLP ] Conf ] Yael Gertner , Yuval Ishai , Eyal Kushilevitz , Tal Malkin Protecting Data Privacy in Private Information Retrieval Schemes. [Citation Graph (0, 0)][DBLP ] Conf ] Yair Bartal On Approximating Arbitrary Metrices by Tree Metrics. [Citation Graph (0, 0)][DBLP ] Conf ] Nathan Linial , Avner Magen , Michael E. Saks Trees and Euclidean Metrics. [Citation Graph (0, 0)][DBLP ] Conf ] Marcus Peinado , Thomas Lengauer Random Generation of Embedded Graphs and an Extension to Dobrushin Uniqueness (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Christos Levcopoulos , Giri Narasimhan , Michiel H. M. Smid Efficient Algorithms for Constructing Fault-Tolerant Geometric Spanners. [Citation Graph (0, 0)][DBLP ] Conf ] Amnon Ta-Shma Almost Optimal Dispersers. [Citation Graph (0, 0)][DBLP ] Conf ] Richard Beigel , Harry Buhrman , Lance Fortnow NP Might Not Be As Easy As Detecting Unique Solutions. [Citation Graph (0, 0)][DBLP ] Conf ] Ran Canetti , Oded Goldreich , Shai Halevi The Random Oracle Methodology, Revisited (Preliminary Version). [Citation Graph (0, 0)][DBLP ] Conf ] Dima Grigoriev Randomized Complexity Lower Bounds. [Citation Graph (0, 0)][DBLP ] Conf ] Orna Kupferman , Moshe Y. Vardi Weak Alternating Automata and Tree Automata Emptiness. [Citation Graph (0, 0)][DBLP ] Conf ] Denis Thérien , Thomas Wilke Over Words, Two Variables Are as Powerful as One Quantifier Alternation. [Citation Graph (0, 0)][DBLP ] Conf ] Mohammad Amin Shokrollahi , Hal Wasserman Decoding Algebraic-Geometric Codes Beyond the Error-Correction Bound. [Citation Graph (0, 0)][DBLP ] Conf ] Michael Luby , Michael Mitzenmacher , Mohammad Amin Shokrollahi , Daniel A. Spielman Analysis of Low Density Codes and Improved Designs Using Irregular Graphs. [Citation Graph (0, 0)][DBLP ] Conf ] Funda Ergün , Sampath Kannan , Ravi Kumar , Ronitt Rubinfeld , Mahesh Viswanathan Spot-Checkers. [Citation Graph (0, 0)][DBLP ] Conf ] Michael A. Bender , Antonio Fernández , Dana Ron , Amit Sahai , Salil P. Vadhan The Power of a Pebble: Exploring and Mapping Directed Graphs. [Citation Graph (0, 0)][DBLP ] Conf ] Adam L. Buchsbaum , Haim Kaplan , Anne Rogers , Jeffery Westbrook Linear-Time Pointer-Machine Algorithms for Least Common Ancestors, MST Verification, and Dominators. [Citation Graph (0, 0)][DBLP ] Conf ] Oded Goldreich , Dana Ron A Sublinear Bipartiteness Tester for Bunded Degree Graphs. [Citation Graph (0, 0)][DBLP ] Conf ] Luca Trevisan Recycling Queries in PCPs and in Linearity Tests (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Miklós Ajtai , Ronald Fagin , Larry J. Stockmeyer The Closure of Monadic NP (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Michael L. Fredman Information Theoretic Implications for Pairing Heaps. [Citation Graph (0, 0)][DBLP ] Conf ] Andrei Z. Broder , Moses Charikar , Alan M. Frieze , Michael Mitzenmacher Min-Wise Independent Permutations (Extended Abstract). [Citation Graph (1, 0)][DBLP ] Conf ] Sanjeev Arora The Approximability of NP-hard Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Moses Charikar , Samir Khuller , Balaji Raghavachari Algorithms for Capacitated Vehicle Routing. [Citation Graph (0, 0)][DBLP ] Conf ] William Aiello , Eyal Kushilevitz , Rafail Ostrovsky , Adi Rosén Adaptive Packet Routing for Bursty Adversarial Traffic. [Citation Graph (0, 0)][DBLP ] Conf ] Matthew Andrews , Lisa Zhang Stability Results for Networks with Input and Output Blocking. [Citation Graph (0, 0)][DBLP ] Conf ] Richard Cole , Bruce M. Maggs , Friedhelm Meyer auf der Heide , Michael Mitzenmacher , Andréa W. Richa , Klaus Schröder , Ramesh K. Sitaraman , Berthold Vöcking Randomized Protocols for Low Congestion Circuit Routing in Multistage Interconnection Networks. [Citation Graph (0, 0)][DBLP ] Conf ] Daniel R. Dooly , Sally A. Goldman , Stephen D. Scott TCP Dynamic Acknowledgment Delay: Theory and Practice (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Oded Goldreich , Amit Sahai , Salil P. Vadhan Honest-Verifier Statistical Zero-Knowledge Equals General Statistical Zero-Knowledge. [Citation Graph (0, 0)][DBLP ] Conf ] Cynthia Dwork , Moni Naor , Amit Sahai Concurrent Zero-Knowledge. [Citation Graph (0, 0)][DBLP ] Conf ] Mihir Bellare , Ran Canetti , Hugo Krawczyk A Modular Approach to the Design and Analysis of Authentication and Key Exchange Protocols (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Anna Gál A Characterization of Span Program Size and Improved Lower Bounds for Monotone Span Programs. [Citation Graph (0, 0)][DBLP ] Conf ] Daniel Lewin , Salil P. Vadhan Checking Polynomial Identities over any Field: Towards a Derandomization? [Citation Graph (0, 0)][DBLP ] Conf ] Amotz Bar-Noy , Sudipto Guha , Joseph Naor , Baruch Schieber Multicasting in Heterogeneous Networks. [Citation Graph (0, 0)][DBLP ] Conf ] Susanne Albers , Naveen Garg , Stefano Leonardi Minimizing Stall Time in Single and Parallel Disk Systems. [Citation Graph (1, 0)][DBLP ] Conf ] Sanjeev Khanna , Shiyu Zhou On Indexed Data Broadcast. [Citation Graph (0, 0)][DBLP ] Conf ] Jon M. Kleinberg , Christos H. Papadimitriou , Prabhakar Raghavan Segmentation Problems. [Citation Graph (0, 0)][DBLP ] Conf ] Nicolai Vorobjov Computing Local Dimension of a Semialgebraic Set. [Citation Graph (0, 0)][DBLP ] Conf ] Bernard Mourrain , Victor Y. Pan Asymptotic Acceleration of Solving Multivariate Polynomial Systems of Equations. [Citation Graph (0, 0)][DBLP ] Conf ] Ming-Deh A. Huang , Ashwin J. Rao A Black Box Approach to the Algebraic Set Decomposition Problem. [Citation Graph (0, 0)][DBLP ] Conf ] Hervé Fournier , Pascal Koiran Are Lower Bounds Easier over the Reals? [Citation Graph (0, 0)][DBLP ] Conf ] Zhi-Zhong Chen , Michelangelo Grigni , Christos H. Papadimitriou Planar Map Graphs. [Citation Graph (0, 0)][DBLP ] Conf ] Michael Molloy , Bruce A. Reed Further Algorithmic Aspects of the Local Lemma. [Citation Graph (0, 0)][DBLP ] Conf ] Jon M. Kleinberg Decision Algorithms for Unsplittable Flow and the Half-Disjoint Paths Problem. [Citation Graph (0, 0)][DBLP ] Conf ] Satish Rao , Warren D. Smith Approximating Geometrical Graphs via "Spanners" and "Banyans". [Citation Graph (0, 0)][DBLP ] Conf ] Uri Zwick Finding Almost-Satisfying Assignments. [Citation Graph (0, 0)][DBLP ] Conf ] Paul Beame , Richard M. Karp , Toniann Pitassi , Michael E. Saks On the Complexity of Unsatisfiability Proofs for Random k -CNF Formulas. [Citation Graph (0, 0)][DBLP ] Conf ] Michael H. Freedman K -sat on Groups and Undecidability.Citation Graph (0, 0)][DBLP ] Conf ] Dima Grigoriev , Marek Karpinski An Exponential Lower Bound for Depth 3 Arithmetic Circuits. [Citation Graph (0, 0)][DBLP ] Conf ] Nader H. Bshouty A New Composition Theorem for Learning Algorithms. [Citation Graph (0, 0)][DBLP ] Conf ] Peter Damaschke Adaptive versus Nonadaptive Attribute-Efficient Learning. [Citation Graph (0, 0)][DBLP ] Conf ] Pierluigi Crescenzi , Deborah Goldman , Christos H. Papadimitriou , Antonio Piccolboni , Mihalis Yannakakis On the Complexity of Protein Folding (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Piotr Indyk , Rajeev Motwani Approximate Nearest Neighbors: Towards Removing the Curse of Dimensionality. [Citation Graph (2, 0)][DBLP ] Conf ] Eyal Kushilevitz , Rafail Ostrovsky , Yuval Rabani Efficient Search for Approximate Nearest Neighbor in High Dimensional Spaces. [Citation Graph (0, 0)][DBLP ] Conf ] Uriel Feige , Christian Scheideler Improved Bounds for Acyclic Job Shop Scheduling (Extended Abstract). [Citation Graph (0, 0)][DBLP ] Conf ] Sanjeev Khanna , Vincenzo Liberatore On Broadcast Disk Paging. [Citation Graph (0, 0)][DBLP ] Conf ] Nathan Linial , Alex Samorodnitsky , Avi Wigderson A Deterministic Strongly Polynomial Algorithm for Matrix Scaling and Approximate Permanents. [Citation Graph (0, 0)][DBLP ] Conf ] Jayram S. Thathachar On Separating the Read-k-Times Branching Program Hierarchy. [Citation Graph (0, 0)][DBLP ] Conf ] Yair Frankel , Philip D. MacKenzie , Moti Yung Robust Efficient Distributed RSA-Key Generation. [Citation Graph (0, 0)][DBLP ] Conf ] László Babai , Thomas P. Hayes , Peter G. Kimmel The Cost of the Missing Bit: Communication Complexity with Help. [Citation Graph (0, 0)][DBLP ] Conf ] 