Papers, Aladdin Center

Papers

Alan M. Frieze, Edge-disjoint paths in expander graphs, (1). SODA 2000: 717-725 ; (2). SIAM J. Comput. 30(6): 1790-1801 (2000), 2000.
Alan M. Frieze, On the number of perfect matchings and Hamilton cycles in epsilon-regular non-bipartite graphs, Electronic Journal of Combinatorics 7, R57., 2000.
Alan M. Frieze, L. Zhao, Optimal Construction of Edge-Disjoint Paths in Random Regular Graphs, Combinatorics, Probability and Computing 9, 241-264., 2000.
Alan M. Frieze, M.Ruszinko, L.Thoma, A note on random minimum length spanning trees, Electronic Journal of Combinatorics 7, R41., 2000.
Alexander Gray, Andrew Moore, 'N-Body' Problems in Statistical Learning. Advances in Neural Information, Processing Systems 13. (Submitted May 2000, Proceedings published May 2001), 2000.
Andrew W. Moore, The Anchors Hierarchy: Using the Triangle Inequality to Survive High Dimensional Data, In proceedings of UAI-2000: The Sixteenth Conference on Uncertainty in Artificial Intelligence, 2000.
Andrew W. Moore et al, Cached Sufficient Statistics: What are they? A short white paper, , 2000.
Avrim Blum, Adam Kalai, Hal Wasserman, Noise-tolerant learning, the parity problem, and the statistical query model, STOC 2000: 435-440, 2000.
Avrim Blum, Carl Burch, On-line Learning and the Metrical Task System Problem, Machine Learning 39(1): 35-58 (2000), 2000.
Avrim Blum, Goran Konjevod, R. Ravi, Santosh Vempala, Semi-definite relaxations for minimum bandwidth and other vertex-ordering problems, TCS 235(1): 25-42 (2000), 2000.
Avrim Blum, Howard J. Karloff, Yuval Rabani, Michael E. Saks, A Decomposition Theorem for Task Systems and Bounds for Randomized Server Problems, SIAM J. Comput. 30(5): 1624-1661 (2000), 2000.
Avrim Blum, Prasad Chalasani, An Online Algorithm for Improving Performance in Navigation, SIAM J. Comput. 29(6): 1907-1938 (2000), 2000.
B.Bollobas, C.Cooper, T.I.Fenner, Alan M. Frieze, On Hamilton cycles in sparse random graphs with minimum degree at least k, Journal of Graph Theory 34, John Wiley and Sons, 42-59., 2000.
Bianca Schroeder, Mor Harchol-Balter, Evaluation of Task Assignment Policies for Supercomputing Servers: The Case for Load Unbalancing and Fairness, 9th IEEE Symposium on High Performance Distributed Computing (HPDC '00) , Pittsburgh, Pennsylvania, August 2000., 2000.
C.Cooper, Alan M. Frieze, Hamilton cycles in random graphs and directed graphs, Random Structures and Algorithms 16,John Wiley and Sons,369-401., 2000.
C.Cooper, M.E.Dyer, Alan M. Frieze, R.Rue, Mixing properties of the Swendsen-Wang process on classes of graphs II, Journal of Mathematical Physics 4, 1499-1527., 2000.
Christopher A. Stone, Robert Harper, Deciding Type Equivalence with Singleton Kinds, POPL 2000: 214-227, 2000.
Colin Cooper, Alan M. Frieze, Kurt Mehlhorn, Volker Priebe, Average-case complexity of shortest-paths problems in the vertex-potential model, Random Structures and Algorithms 16(1): 33-46 (2000), 2000.
Dan Pelleg, Andrew Moore, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, International Conference on Machine Learning, 2000 (ICML2000), 2000.
Dannie Durand, Steve R. White, Trading Accuracy for Speed in Parallel Simulated Annealing Algorithms, Parallel Computing 26, Jan 2000, p. 135-150, 2000.
Edmund M. Clarke, Somesh Jha, Wilfredo R. Marrero, Partial Order Reductions for Security Protocol Verification, TACAS 2000: 503-518, 2000.
Edmund M. Clarke, Somesh Jha, Wilfredo R. Marrero, Verifying security protocols with Brutus, TOSEM 9(4): 443-487 (2000), 2000.
Geoff Gordon, Andrew Moore, Learning Filaments, International Conference on Machine Learning, 2000 (ICML2000), 2000.
George Biros, Omar Ghattas, Parallel Lagrange-Newton-Krylov-Schur Methods for PDE-Constrained Optimization. Part I: The Krylov-Schur Solver, Technical Report, Laboratory for Mechanics, Algorithms, and Computing, Carnegie Mellon University, 2000., 2000.
George Biros, Omar Ghattas, Parallel Lagrange-Newton-Krylov-Schur Methods for PDE-Constrained Optimization. Part II: The Lagrange-Newton Solver, and its Application to Optimal Control of Steady Viscous Flows., Technical Report, Laboratory for Mechanics, Algorithms, and Computing, Carnegie Mellon University, 2000, 2000.
George Biros, Omar Ghattas, A Lagrange-Newton-Krylov-Schur Method for PDE-Constrained Optimization., SIAG/OPT News and Views (the newsletter of the SIAM Activity Group on Optimization), Vol. 11, No. 2, August 2000, 2000.
Goran Konjevod, R. Ravi, An approximation algorithm for the covering Steiner problem, SODA 2000: 338-344, 2000.
Haim Kaplan, Chris Okasaki, Robert Endre Tarjan, Simple Confluently Persistent Catenable Lists, SIAM J. Comput. 30(3): 965-977 (2000), 2000.
Herbert Edelsbrunner, Xiang-Yang Li, Gary L. Miller, Andreas Stathopoulos, Dafna Talmor, Shang-Hua Teng, Alper Üngör, Noel Walkington, Smoothing and cleaning up slivers, STOC 2000: 273-277, 2000.
James F. Antaki, Guy E. Blelloch, Omar Ghattas, Ivan Malcevic, Gary L. Miller, Noel Walkington, A Parallel Dynamic-Mesh Lagrangian Method for Simulation of Flows with Dynamic Interfaces, SC 2000., 2000.
Jochen Könemann, R. Ravi, A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees, STOC 2000: 537-546, 2000.
John Lafferty, Dan Rockmore, Codes and iterative decoding on algebraic expander graphs, In International Symposium on Information Theory and its Applications, 2000., 2000.
Joseph O'Sullivan, Avrim Blum, John Langford, Rich Caruana, FeatureBoost: A Meta Learning Algorithm that Improves Model Robustness, ICML '00, 2000.
Leaf Petersen, Perry Cheng, Robert Harper, Chris Stone, Implementing the TILT Internal Language, Carnegie Mellon University Computer Science Department Technical Report CMU-CS-00-180, December, 2000., 2000.
Lisa Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics 13(4): 505-520 (2000), 2000.
Lisa Fleischer, Recent Progress in Submodular Function Minimization OPTIMA, Mathematical Programming Society Newsletter. September 2000, no.64, 1-11., 2000.
Lisa Fleischer, Bruce Hendrickson, Ali Pinar, On Identifying Strongly Connected Components in Parallel, IPDPS Workshops 2000: 505-511, 2000.
Lisa Fleischer, Robert D. Carr, Vitus J. Leung, Cynthia A. Phillips, Strengthening Integrality Gaps for Capacitated Network Design and Covering Problems, Proceedings of the 11th ACM/SIAM Symposium on Discrete Algorithms, January 2000., 2000.
Lisa Fleischer, Satoru Iwata, A Push-Relabel Framework for Submodular Function Minimization and Applications to Parametric Optimization, Accepted to Discrete Applied Mathematics (to appear), 2000.
Lisa Fleischer, Satoru Iwata, Improved algorithms for submodular function minimization and submodular flow, STOC 2000: 107-116, 2000.
Lisa Fleischer, Satoru Iwata, Satoru Fujishige, A Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions, Proceedings of the 32nd ACM Symposium on Theory of Computing , May, 2000. To appear in Journal of the ACM., 2000.
Martin A. Riedmiller, Andrew Moore, Jeff Schneider, Reinforcement Learning for Cooperating and Communicating Reactive Agents in Electrical Power Grids, Balancing Reactivity and Social Deliberation in Multi-Agent Systems 2000: 137-149, 2000.
Matthew Andrews, Antonio Fernández, Mor Harchol-Balter, Frank Thomson Leighton, Lisa Zhang, General Dynamic Routing with Per-Packet Delay Guarantees of O(Distance + 1/Session Rate), SIAM J. Comput. 30(5): 1594-1623 (2000), 2000.
Mor Harchol-Balter, Task Assignment with Unknown Duration, ICDCS 2000: 214-224, 2000.
Mor Harchol-Balter, Nikhil Bansal, Bianca Schroeder, Mukesh Agrawal, Implementation of SRPT Scheduling in Web Servers, Technical report Number CMU-CS-00-170, includes Flash results and Later technical report version including Apache results and Abstract, 2000.
Naveen Garg, Goran Konjevod, R. Ravi, A Polylogarithmic Approximation Algorithm for the Group Steiner Tree Problem, J. Algorithms 37(1): 66-84 (2000), 2000.
Paul Komarek, Andrew Moore, A Dynamic Adaptation of AD-trees for Efficient Machine Learning on Large Data Sets, International Conference on Machine Learning, 2000 (ICML2000)., 2000.
Poul Frederick Williams, Armin Biere, Edmund M. Clarke, Anubhav Gupta, Combining Decision Diagrams and SAT Procedures for Efficient Symbolic Model Checking, CAV 2000: 124-138, 2000.
Randal E. Bryant, Pankay Chauhan, Edmund M. Clarke, Amit Goel, A Theory of Consistency for Modular Synchronous Systems, FMCAD 2000: 486-504, 2000.
Refael Hassin, R. Ravi, F. S. Salman, Approximation algorithms for a capacitated network design problem, APPROX 2000: 167-176, 2000.
Remi Munos, Andrew Moore, Rates of Convergence for Variable Resolution Schemes in Optimal Control, International Conference on Machine Learning, 2000 (ICML2000)., 2000.
Robert Harper, Proof-Directed Debugging, Journal of Functional Programming, 2000., 2000.
Robert Harper, Benjamin C. Pierce, Advanced module systems: a guide for the perplexed (abstract of invited talk), ICFP 2000: 130, 2000.
Robert Harper, Chris Stone, A Type-Theoretic Interpretation of Standard ML, Milner Festschrifft. 2000., 2000.
Satoru Iwata, Lisa Fleischer, Satoru Fujishige, A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions, STOC 2000: 97-106, 2000.
Scott Davies, Andrew Moore, Mix-nets: Factored Mixtures of Gaussians in Bayesian Networks with Mixed Continuous and Discrete Variables, In proceedings of UAI-2000: The Sixteenth Conference on Uncertainty in Artificial Intelligence, 2000.
Swarup Acharya, Phillip B. Gibbons, Viswanath Poosala, Congressional Samples for Approximate Answering of Group-By Queries., SIGMOD Conference 2000: 487-498., 2000.
Sérgio Vale Aguiar Campos, Edmund M. Clarke, Orna Grumberg, Selective Quantitative Analysis and Interval Model Checking: Verifying Different Facets of a System, Formal Methods in System Design 17(2): 163-192 (2000)3, 2000.
T. Bohman, Alan M. Frieze, M.Ruszinko, L.Thoma, A Note on Sparse Random Graphs and Cover Graphs, Electronic Journal of Combinatorics 7, R19, 2000.
T. Bohman, C.Cooper,and Alan M. Frieze, Min-Wise independent linear permutations, Electronic Journal of Combinatorics 7, R26, 2000.
Umut A. Acar, Guy E. Blelloch, Robert D. Blumofe, The data locality of work stealing., SPAA 2000: 1-12., 2000.
Vicky Hartonas-Garmhausen, Sérgio Vale Aguiar Campos, Alessandro Cimatti, Edmund M. Clarke, Fausto Giunchiglia, Verification of a safety-critical railway interlocking system with real-time constraints, Science of Computer Programming 36(1): 53-64 (2000), 2000.
Yuan Lu, Jawahar Jain, Edmund M. Clarke, Masahiro Fujita, Efficient variable ordering using aBDD based sampling, DAC 2000: 687-692, 2000.
A. L. Coates, H. S. Baird, and R.J. Fateman, Pessimal Print: A Reverse Turing Test, Proceedings of ICDAR 2001 International Conference on Document Analysis and Recognition, Seattle, WA., 2001.
Alan M. Frieze, Hamilton cycles in the union of random permutations, Random Structures and Algorithms 18, John Wiley and Sons, 83-94, 2001.
Alan M. Frieze, Bjarni V. Halldórsson, Optimal sequencing by hybridization in rounds, RECOMB 2001: 141-148, 2001.
Alan M. Frieze, Gregory B. Sorkin, The probabilistic relationship between the assignment and asymmetric traveling salesman problems, SODA 2001: 652-660, 2001.
Aleksandar Nanevski, Guy Blelloch, Robert Harper, Automatic Generation of Staged Geometric Predicates, International Conference on Functional Programming, Florence, September, 2001, 2001.
Andrei Z. Broder, Alan M. Frieze, Eli Upfal, A general approach to dynamic packet routing with bounded buffers, JACM 48(2): 324-349 (2001), 2001.
Avrim Blum, Adam Kalai, Jon M. Kleinberg, Admission Control to Minimize Rejections, WADS 2001: 155-164, 2001.
Avrim Blum, Shuchi Chawla, Learning from Labeled and Unlabeled Data using Graph Mincuts, ICML '01, 2001.
Bjarni V. Halldórsson, Magnús M. Halldórsson, R. Ravi, On the Approximability of the Minimum Test Collection Problem, ESA 2001: 158-169, 2001.
Boaz Barak, Oded Goldreich, Russell Impagliazzo, Steven Rudich, Amit Sahai, Salil P. Vadhan, Ke Yang, On the (Im)possibility of Obfuscating Programs, CRYPTO 2001: 1-18, 2001.
C. R. Palmer, G. Siganos, M. Faloutsos, C. Faloutsos, Phillip B. Gibbons, The connectivity and fault-tolerance of the internet topology, NRDM'01 Workshop, 2001.
C. R. Palmer, Phillip B. Gibbons, C. Faloutsos, Fast approximation of the neighbourhood function for massive graphs, 2001, 2001.
Chengxiang Zhai, John Lafferty, Model-based Feedback in the Language Modeling Approach to Information Retrieval, CIKM 2001: 403-410, 2001.
Chengxiang Zhai, John Lafferty, A Study of Smoothing Methods for Language Models Applied to Ad Hoc Information Retrieval, SIGIR 2001: 334-342, 2001.
Christopher Colby, Karl Crary, Robert Harper, Peter Lee, Frank Pfenning, Automated Techniques for Provably Safe Mobile Code, To appear, Theoretical Computer Science, 2001, 2001.
Colin Cooper, Alan M. Frieze, A General Model of Undirected Web Graphs, ESA 2001: 500-511, 2001.
Colin Cooper, Martin E. Dyer, Alan M. Frieze, On Markov Chains for Randomly H-Coloring a Graph, J. Algorithms 39(1): 117-134 (2001), 2001.
Dan Pelleg, Andrew Moore: Mixtures of Rectangles, Interpretable Soft Clustering, International Conference on Machine Learning, 2001 (ICML2001), 2001.
Derek Dreyer, Robert Harper, Karl Crary, Toward a Practical Type Theory for Recursive Modules, Carnegie Mellon University Computer Science Department Technical Report CMU-CS-01-112, March, 2001., 2001.
Edmund M. Clarke, Armin Biere, Richard Raimi, Yunshan Zhu, Bounded Model Checking Using Satisfiability Solving., Formal Methods in System Design 19(1): 7-34 (2001), 2001.
Edmund M. Clarke, Orna Grumberg, Somesh Jha, Yuan Lu, Helmut Veith, Progress on the State Explosion Problem in Model Checking, Informatics 2001: 176-194, 2001.
Edoardo Biagioni, Robert Harper, Peter Lee, A Network Protocol Stack in Standard ML, To appear, Journal of Higher Order and Symbolic Computation, 2001., 2001.
Fred B. Schneider, J. Gregory Morrisett, Robert Harper, X-means: Extending K-means with Efficient Estimation of the Number of Clusters, International Conference on Machine Learning, 2000 (ICML2000), 2001.
Goran Konjevod, R. Ravi, F. S. Salman, On approximating planar metrics by tree metrics, Information Processing Letters 80(4): 213-219 (2001), 2001.
Guy Blelloch, Hal Burch, Karl Crary, Robert Harper, Gary Miller, Noel Walkington, Persistent Triangulations, Journal of Functional Programming, volume 2, part 5, September, 2001, 2001.
Guy E. Blelloch, Perry Cheng, Phillip B. Gibbons, Room synchronizations, SPAA 2001: 122-133, 2001.
Guy Lebanon, John Lafferty, Boosting and maximum likelihood for exponential models, Technical Report CMU-CS-01-144, School of Computer Science, CMU, 2001. Shorter version to appear in Advances in Neural Information Processing Systems (NIPS), 14, 2001, 2001.
Haim Kaplan, Robert Endre Tarjan, Kostas Tsioutsiouliklis, Faster kinetic heaps and their use in broadcast scheduling, SODA 2001: 836-844, 2001.
Hongwei Xi, Robert Harper, A Dependently Typed Assembly Language, International Conference on Functional Programming, Florence, September, 2001, 2001.
John Lafferty, Chengxiang Zhai, Probabilistic IR models based on document and query generation, Abstract in the Proceedings of the Workshop on Language Modeling and Information Retrieval, Carnegie Mellon University, 2001, 2001.
John Lafferty, Chengxiang Zhai, Document Language Models, Query Models, and Risk Minimization for Information Retrieval, SIGIR 2001: 111-119, 2001.
John Lafferty, Fernando Pereira, Andrew McCallum, Conditional random fields: Probabilistic models for segmenting and labeling sequence data, International Conference on Machine Learning (ICML'01), 2001, 2001.
John Lafferty, Larry Wasserman, Iterative Markov chain Monte Carlo computation of reference priors and minimax risk, Uncertainty in Artificial Intelligence (UAI'01), 2001, 2001.
Joseph Y. Halpern, Robert Harper, Neil Immerman, Phokion Kolaitis, Moshe Y. Vardi, Victor Vianu, On the Unusual Effectiveness of Logic in Computer Science, To appear, Bulletin of the Association for Symbolic Logic, 2001, 2001.
Kelly Easton, George L. Nemhauser, Michael Trick, The Traveling Tournament Problem Description and Benchmarks, CP 2001: 580-584, 2001.
Lisa Fleischer, A 2-Approximation for Minimum Cost {0, 1, 2} Vertex Connectivity, IPCO 2001: 115-129, 2001.
Lisa Fleischer, Kamal Jain, David Williamson, An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem, 42nd Annual Symposium of the Foundations of Computer Science, October 2001, 2001.
Lisa Fleischer, Satoru Iwata, S. Thomas McCormick, A Faster Capacity Scaling Algorithm for Minimum Cost Submodular Flow, Accepted to Math. Programming. (to appear), 2001.
Malcolm Strens, Andrew Moore, Direct Policy Search using Paired Statistical Tests, International Conference on Machine Learning, 2001 (ICML2001), 2001.
Manuel Blum and Nicholas J. Hopper, Secure Human Identification Protocols, Proceedings of Asiacrypt 2001, 2001.
Mor Harchol-Balter, Job Placement with Unknown Duration and No Preemption, Performance Evaluation Review Volume 28, No. 4, March 2001. Invited paper, 2001.
Naveen Garg, Rohit Khandekar, Goran Konjevod, R. Ravi, F. S. Salman, Amitabh Sinha: , On the Integrality Gap of a Natural Formulation of the Single-Sink Buy-at-Bulk Network Design Problem, IPCO 2001: 170-184, 2001.
Nicholas J. Hopper, Manuel Blum, Secure Human Identification Protocols, ASIACRYPT 2001: 52-66, 2001.
Nikhil Bansal, Mor Harchol-Balter, Analysis of SRPT scheduling: investigating unfairness, SIGMETRICS/Performance 2001: 279-290, 2001.
P. Keskinocak, R. Ravi, S. Tayur, Scheduling and Reliable Lead Time Quotation for Orders with Availability Intervals and Lead Time Sensitive Revenues, Management Science, February 2001, 2001.
Pankay Chauhan, Edmund M. Clarke, Somesh Jha, James H. Kukula, Helmut Veith, Dong Wang, Using Combinatorial Optimization Methods for Quantification Scheduling, CHARME 2001: 293-309, 2001.
Perry Cheng, Guy E. Blelloch, A Parallel, Real-Time Garbage Collector, PLDI 2001: 125-136, 2001.
Peter Sand, Andrew Moore, Repairing Faulty Mixture Models using Density Estimation, International Conference on Machine Learning, 2001 (ICML2001), 2001.
Phillip B. Gibbons, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, VLDB 2001: 541-550, 2001.
Phillip B. Gibbons, Srikanta Tirthapura, Estimating simple functions on the union of data streams, SPAA 2001: 281-291, 2001.
R. Ravi, Madhav V. Marathe, S. S. Ravi, Daniel J. Rosenkrantz, Harry B. Hunt III, Approximation Algorithms for Degree-Constrained Minimum-Cost Network-Design Problems, Algorithmica 31(1): 58-78 (2001), 2001.
Robert Harper, Frank Pfenning, On Equivalence and Canonical Forms in the LF Type Theory, Submitted for publication, October, 2001, 2001.
S. A. Seshia, G. E. Blelloch, R. W. Harper, A Performance Comparison of Interval Arithmetic and Error Analysis for Geometric Predicates, Technical Report. 2001, 2001.
Shimin Chen, Phillip B. Gibbons, Todd C. Mowry, Improving Index Performance through Prefetching, SIGMOD Conference 2001, 2001.
Stephen Della Pietra, Vincent Della Pietra, John Lafferty, Duality and auxiliary functions for Bregman distances, Technical Report CMU-CS-01-109, School of Computer Science, CMU, 2001, 2001.
Sérgio Vale Aguiar Campos, Edmund M. Clarke, The Verus language: representing time efficiently with BDDs, TCS 253(1): 95-118 (2001), 2001.
T. Bohman, Alan M. Frieze, Arc-Disjoint Paths in Expander Digraphs, Proceedings of FOCS 2001, 558-567, 2001.
T.Bohman, A. Frieze, M.Ruszinko, L.Thoma, Vertex covers by edge disjoint cliques, Combinatorica 2001 21 171-197, 2001.
T.Bohman, A. Frieze, M.Ruszinko, L.Thoma, G-intersecting families, Combinatorics, Probability and Computing 2001, 10, 367-384, 2001.
Tom Bohman, Alan M. Frieze, Avoiding a giant component, Random Structures and Algorithms 19(1): 75-85 (2001), 2001.
V. Akcelik, B. Jaramaz, O, Ghattas, Nearly Orthogonal Two-Dimensional Grid Generation with Aspect Ratio Control, Journal of Computational Physics, 171(2):805-821, 2001., 2001.
Mor Harchol-Balter, Karl Sigman, and Adam Wierman, Asymptotic Convergence of Scheduling Policies with respect to Slowdown, Performance Evaluation. Volume 49, September 2002, 2002.
Alan Frieze, On random symmetric travelling salesman problems, to appear in FOCS 2002, 2002.
Alan Frieze and J.Yukich, The traveling salesman problem and its variations, G. Gutin and A.P. Punnen (Eds.), Kluwer Academic Publisher, 2002.
Alan Frieze and M.Krivelevich, Hamilton Cycles in Random Subgraphs of Pseudo-Random Graphs, Discrete Mathematics 256, 137-150, 2002.
Alan Frieze and R.J. Gould, M. Karonski, F. Pfender, On graph irregularity strength, Journal of Graph Theory 41, 120-137, 2002.
Alan Frieze, J.Yukich, Probabilistic analysis of the Traveling Salesman Problem.The traveling salesman problem and its variations, G. Gutin and A.P. , Kluwer Academic Publisher, 257-308, 2002, 2002.
Alan Frieze, N.C. Wormald, Random k-SAT: A tight threshold for moderately growing k, Proceedings of the Fifth International Symposium on Theory and Applications of Satisfiability Testing, 2002, 1-6, 2002.
Avrim Blum, John Dunagan, Smoothed Analysis of the Perceptron Algorithm, SODA 2002, 2002.
Avrim Blum, Shuchi Chawla, Adam Kalai, Static Optimality and Dynamic Search-Optimality in Lists and Trees, SODA 2002, 2002.
Avrim Blum, Tuomas Sandholm, Martin Zinkevich, Online Algorithms for Market Clearing, SODA 2002, 2002.
Benny Pinkas and Tomas Sander, Securing Passwords Against Dictionary Attacks, Proceedings of the ACM Computer and Security Conference (CCS' 02). ACM Press, November 2002, 2002.
C.Cooper, Alan Frieze, Crawling on web graphs, STOC 2002, 2002.
C.Cooper, Alan Frieze, Multi-coloured Hamilton cycles in randomly coloured random graphs Combinatorics, Probability and Computing 2002, 11, 129--134, 2002.
C.Cooper, Alan Frieze, B.Reed, Random regular graphs of non-constant degree: connectivity and Hamilton cycles, Combinatorics, Probability and Computing 11, 249-262, 2002, 2002.
C.Cooper, Alan Frieze, G. Sorkin, A note on random 2-SAT with prescribed literal degrees, SODA 2002, 316-320, 2002.
Daniel Blanford, Guy Blelloch, Index Compression Through Document Reordering, Data Compression Conference 2002 (DCC 2002), p. 342, 2002.
Daniel Sleator, Muralidhar Talupur, Optimal Binary Search Trees in Online Algorithms, CMU Computer Science Department Technical Report, vol. 148, (2002), p. 1, 2002.
Dannie Durand, D. Sankoff, Test for Gene Clustering, RECOMB2002, Sixth Annual International Conference on Computational Molecular Biology, Apr. 2002 , 2002.
E. Drinea, Alan Frieze, M. Mitzenmacher, Balls and Bins Models with Feedback, SODA 2002, 308-315, 2002.
Haim Kaplan, Nira Shafrir and Robert E. Tarjan, Meldable Heaps and Boolean Union-Find, The 34th Annual Symposium on the Theory of Computing (STOC), vol. 34, (2002), p. 573, 2002.
J. Konemann, Y. Li, O. Parekh, and A. Sinha, Approximation Algorithms for Edge-Dilation k-Center Problems, In proceedings of SWAT 2002, 2002.
Mor Harchol-Balter, Karl Sigman, and Adam Wierman, Understanding the Slowdown of Large Jobs in an M/GI/1 System, MAMA 2002, 2002.
Mor Harchol-Balter, Nikhil Bansal, Bianca Schroeder, Mukesh Agrawal, Size-based Scheduling to Improve Web Performance, Currently being reviewed, 2002.
Nicholas J. Hopper, John Langford, Luis von Ahn, Provably Secure Steganography, Crypto 2002, 2002.
Nikhil Bansal, Avrim Blum, and Shuchi Chawla, Correlation Clustering, Symp. on Foundations of Computer Science (FOCS) 2002, pages 238-247, 2002.
S. Chawla, D. Kitchin, U. Rajan, R. Ravi, and A. Sinha, Profit Maximizing Mechanisms for the Extended Multicasting Game, To appear in ACM-EC 2003; also CMU CS Technical Report CMU-CS-02-164, 2002, 2002.
S. Chawla, D. Kitchin, U. Rajan, R. Ravi, and A. Sinha, Profit Maximizing Mechanisms for the Extended Multicasting Game, To appear in ACM-EC 2003; also CMU CS Technical Report CMU-CS-02-164, 2002, 2002.
Sanjeev Arora, Alan Frieze, H.Kaplan, A New Rounding Procedure for the Assignment Problem with Applications to Dense Graph Arrangement Problems, Mathematical Programming 2002, A 92, 1-36, 2002.
Umut Acar, Guy Blelloch, Robert Harper, Adaptive Functional Programming, POPL 2002, 2002.
Adam Wierman, Nikhil Bansal, and Mor Harchol-Balter , A Note Comparing Response Times in the M/GI/1/FB and M/GI/1/PS Queues , To appear in Operations Research Letters, 2003.
A. Flaxman, T. Fenner, and Alan Frieze, High degree vertices and eigenvalues in the preferential attachment graph, Proceedings of RANDOM 2003, 2003.
Adam Meyerson, Online Algorithms for Network Design, CMU-CS-03-115, February 2003. Submitted to FOCS 2003, 2003.
Adam Meyerson and Ryan Williams, General k-Anonymization is Hard, Technical Report, Carnegie Mellon University, CMU-CS-03-113, March 2003, 2003.
Adam Wierman, Julia Salzman, Michael Jablonski, and Anant Godbole, An Improved Upper Bound for the Pebbling Threshold of the n-Path, To appear in Discrete Mathematics, 2003.
Adam Wierman, Mor Harchol-Balter, Classifying Scheduling Policies with Respect to Unfairness in an M/GI/1, SIGMETRICS 2003, Technical Report CMU-CS-02-187, 2003.
Adam Wierman, Takayuki Osogami, Mor Harchol-Balter, Alan Scheller-Wolf, Analyzing the Effect of Prioritized Background Tasks in Multiserver Systems, Technical Report CMU-CS-03-213, 2003, 2003.
Adam Wierman, Takayuki Osogami, and Jorgen Olsen, Modeling TCP-Vegas under On/Off Traffic, MAMA 2003, 2003.
Adam Wierman, Takayuki Osogami, and Jorgen Olsen, Modeling TCP-Vegas under On/Off Traffic, To appear in Performance Evaluation Review. MAMA workshop at SIGMETRICS 2003, 2003.
Alan Frieze and B. Pittel, Perfect matchings in random graphs with prescribed minimal degree, Proceedings of SODA 2003, 148-157, 2003.
Alan Frieze and M.Molloy, The satisfiability threshold for randomly generated binary constraint satisfaction problems, Proceedings of RANDOM 2003, 2003.
Andrew Bortz, Nick Hopper, and Luis Von-Ahn, K-Anonymous Message Transmission, ACM Conference on Computer and Communications Security (CCS), October 2003, 2003.
Avrim Blum, Shuchi Chawla, David R. Karger, Terran Lane, Adam Meyerson, and Maria Minkoff, Approximation Algorithms for Orienteering and Discounted-Reward TSP, CMU-CS-03-121, March 2003, 2003.
Baruch Awerbuch, Yossi Azar, and Adam Meyerson, Reducing Truth-Telling Online Mechanisms to Online Optimization, ACM Symposium on Theory of Computing (STOC) 2003, 2003.
Bianca Schroeder and Mor Harchol-Balter, Web servers under overload: How scheduling can help, To appear in 18th International Teletraffic Congress. Berlin, Germany. September 2003. (Original Technical report Number CMU-CS-02-143), 2003.
Blandford, Daniel K., Guy E. Blelloch, David E. Cardoze and Clemens Kadow, Compact representations of simplicial meshes in two and three dimensions, Proceedings, 12th International Meshing Roundtable, Sandia National Laboratories, pp.135-146, Sept. 2003, 2003.
C. Cooper and Alan Frieze, On a general model of web graphs, Random Structures and Algorithms 22, John Wiley and Sons, 311-335, 2003.
C. Cooper and Alan Frieze, The cover time of sparse random graphs, Proceedings of SODA 2003, 140-147, 2003.
Daniel K. Blandford, Guy E. Blelloch, Ian A. Kash, Compact representations of separable graphs, ACM/SIAM Symposium on Discrete Algorithms (SODA), vol. 14, (2003), p. 679, 2003.
G. Even, N. Garg, J. Konemann, R. Ravi, and A. Sinha, Min-Max Payoffs of a Location Game, CMU CS Technical report CMU-CS-03-143; submitted to Games and Economic Behavior, 2003, 2003.
Guy Blelloch, Bruce Maggs, Shan Leung Maverick Woo, Space-Efficient Finger Search on Degree-Balanced Search Trees, ACM/SIAM Symposium on Discrete Algorithms (SODA), vol. 14, (2003), p. 679, 2003.
Guy Blelloch, Perry Cheng, Phil Gibbons, Scalable Room Synchronization, Theory of Computing Systems, vol. 36, (2003), p. 397, 2003.
H. Kaplan, N.Shafrir, R.E. Tarjan, Union-find with Deletions, The 13th Annual Symposium on Discrete Algorithms (SODA), vol. 13, (2002), p. 19, 2003.
I. Koutis, On the Hardness of Approximate Multivariate Integration, APPROX 2003, 2003.
J. Konemann, A. Levin and A. Sinha, Approximating the Degree-Bounded Minimum Diameter Spanning Tree Problem, APPROX 2003, vol. 6, (2003), p. 109, 2003.
Kedar Dhamdhere, Anupam Gupta, and R. Ravi, Approximating Average Distortion of Embeddings into Line, DIMACS Workshop on Discrete Metric Spaces and their Algorithmic Applications, 2003.
Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Ramesh K. Sitaraman, Designing Overlay Multicast Networks For Streaming, SPAA 2003, 2003.
Konstantin Andreev, Bruce Maggs, Adam Meyerson, and Ramesh Sitaraman, Designing Overlay Multicast Networks for Streaming, ACM Symposium in Parallelism in Algorithms and Architectures (SPAA) 2003, 2003.
Luis von Ahn, Manuel Blum, Nicholas J. Hopper, and John Langford, CAPTCHA: Using Hard AI Problems For Security, Eurocrypt 2003, 2003.
Luis von Ahn, Manuel Blum, and John Langford, Secure Human Identification Protocols, To appear in Communications of the ACM, 2003.
M.E. Dyer, Alan Frieze, and M. Molloy, A probabilistic analysis of randomly generated binary constraint satisfaction problems, Theoretical Computer Science 290, 1815-1828, 2003.
M.E. Dyer, Alan M. Frieze, Randomly colouring graphs with lower bounds on girth and maximum degree, Random Structures and Algorithms 23, 167-179, 2003.
Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, Cycle Stealing under Immediate Dispatch Task Assignment, SPAA 2003, 2003.
Mor Harchol-Balter, Cuihong Li, Takayuki Osogami, Alan Scheller-Wolf, and Mark Squillante, Cycle Stealing under Immediate Dispatch Task Assignment, To appear in Fifteenth ACM Annual Symposium on Parallel Algorithms and Architectures. San Diego, CA. June, 2003, 2003.
Nikhil Bansal, Breaking the 1/µ(1-rho) Barrier: Sojourn Time under SRPT, MAMA 2003, 2003.
Nikhil Bansal and Kirk Pruhs, Server Scheduling in the Lp Norm: A Rising Tide Lifts All Boat, STOC 2003, 2003.
Nikhil Bansal, Avrim Blum, Shuchi Chawla, and Adam Meyerson, Online Oblivious Routing, ACM Symposium in Parallelism in Algorithms and Architectures (SPAA) 2003, 2003.
Nikhil Bansal, Kedar Dhamdhere, J. Konemann, Amitabh Sinha, Non-Clairvoyant Scheduling for Minimizing Mean Slowdown, 20th Annual Symposium on Theoretical Aspects of Computer Science (STACS), vol. 20, (2003), p. 260, 2003.
Nikhil Basal, Avrim Blum, Shuchi Chawla, and Kedar Dhamdhere, Scheduling for Flow-Time with Admission Control, European Symposium on Algorithms, 2003, 2003.
Ryan Williams, On Computing k-CNF Formula Properties, SAT 2003, 2003.
Ryan Williams, Carla Gomes, and Bart Selman, On the connections between backdoors, restarts, and heavy-tailedness in combinatorial search, SAT 2003, 2003.
S. Chawla, U. Rajan, R. Ravi and A. Sinha, Min-Max Payoffs of a Location Game, CMU CS Technical report CMU-CS-03-143, (2003), p. 190, 2003.
S. Chawla, U. Rajan, R. Ravi, and A. Sinha, Min-Max Payoffs of a Location Game, CMU CS Technical report CMU-CS-03-143; submitted to Games and Economic Behavior, 2003, 2003.
S.Chawla, D. Kitchin, U. Rajan, R. Ravi and A. Sinha, Profit guaranteeing mechanisms for multicast networks, ACM Conference on Electronic Commerce, vol. 4, (2003), p. 190, 2003.
Stuart Haber, Bill Horne, Joe Pato, Thomas Sander, and Robert Endre Tarjan, If Piracy Is the Problem, Is DRM the Answer?, Digital Rights Management, vol. , (2003), p. 224, 2003.
T. Bohman and Alan Frieze, Arc-Disjoint Paths in Expander Digraphs, SIAM Journal on Computing 32, 326-344, 2003.
T. Bohman, Alan Frieze and R. Martin, How many random edges make a dense graph Hamiltonian?, Random Structures and Algorithms 22, 33-42, 2003.
T. Bohman, C.Cooper, Alan Frieze, R. Martin, and M. Ruszinko, On Randomly Generated Intersecting Hypergraphs, Electronic Journal on Combinatorics, R29, 2003.
Takayuki Osogami and Mor Harchol-Balter, Necessary and sufficient conditions for representing general distributions by Coxians, To appear in 13th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation (Tools 03), 2003.
Takayuki Osogami and Mor Harchol-Balter, A closed-form solution for mapping general distributions to minimal PH distributions, To appear in 13th International Conference on Modelling Techniques and Tools for Computer Performance Evaluation (Tools 03), 2003.
Takayuki Osogami, Adam Wierman, Mor Harchol-Balter, How many servers are best in a dual-priority FCFS system?, Technical Report CMU-CS-03-201, 2003, 2003.
Takayuki Osogami, Mor Harchol-Balter, Alan Scheller-Wolf, Analysis of Cycle Stealing with Switching Cost, SIGMETRICS 2003, 2003.
Umut A. Acar, Guy E. Blelloch, and Robert Harper, Selective memoization, ACM Symposium on Principles of Programming Languages, 2003, 2003.
Xiaojin Zhu, John Lafferty, and Zoubin Ghahramani, Combining active learning and semi-supervised learning using Gaussian fields and harmonic functions, ICML 2003 Workshop on The Continuum from Labeled to Unlabeled Data in Machine Learning and Data Mining, 2003.
Xiaojin Zhu, Zoubin Ghahramani, and John Lafferty, Semi-supervised learning using Gaussian fields and harmonic functions, Twentieth International Conference on Machine Learning (ICML-2003), 2003.
A. Flaxman, A. M. Frieze, and J. Vera, A geometric preferential attachment model of networks, Third Workshop on Algorithms and Models for the Web-Graph WAW2004, 2004.
Adam Meyerson and Ryan Williams, On the Complexity of Optimal k-Anonymity, ACM Symposium on Principles of Database System, (2004), 2004.
Adam Meyerson and Ryan Williams, On the Complexity of Optimal k-Anonymity, ACM Symposium on Principles of Database System, (2004), 2004.
Alan Frieze, M.Krivelevich, and R. Martin, The emergence of a giant component in a random subgraph of pseudo-random graphs, Random Structures and Algorithms 24, 42-50, 2004.
Avrim Blum, John Lafferty, Mugizi Robert Rwebangira, and Rajashekar Reddy, Semi-Supervised Learning Using Randomized Mincuts, Proceedings of the 21st International Conference on Machine Learning (ICML), 2004.
C. Cooper, A.M. Frieze, and J. Vera, Random deletions in a scale free random graph process, To appear in Internet Mathematics 2004, 2004.
Daniel K. Blandford and Guy Blelloch, Compact Representations of Ordered Sets, ACM/SIAM Symposium on Discrete Algorithms (SODA), vol. 15, (2004), p. 11, 2004.
David Cardoze, Alexandre Cunha, Gary L. Miller, Todd Phillips, and Noel Walkington, A Bezier-based Approach to Unstructured Moving Mesh Simulations, ACM Symposium on Computational Geometry, (2004), 2004.
David McWherter, Bianca Schroeder, Natassa Ailamaki, and Mor Harchol-Balter, Priority Mechanisms for OLTP and Transactional Web Applications, In 20th International Conference on Data Engineering, (2004), p. 535, 2004.
David McWherter, Bianca Schroeder, Natassa Ailamaki, and Mor Harchol-Balter, Priority Mechanisms for OLTP and Transactional Web Applications, In 20th International Conference on Data Engineering, (2004), p. 535, 2004.
Guy Blelloch and Phillip B. Gibbons, Effectively Sharing a Cache Among Threads, ACM Symposium on Parallelism in Algorithms and Architecture (SPAA), vol. , (2004), 2004.
Guy Blelloch, Bruce Maggs, Shan Leung Maverick Woo, Space-Efficient Finger Search on Degree-Balanced Search Trees, Workshop on Algorithms Engineering and Experiments (ALENEX), (2004), p. 50, 2004.
John Lafferty, Xiaojin Zhu, and Yan Liu, Kernel conditional random fields: Representation and clique selection, Proceedings of the 21st International Conference on Machine Learning (ICML), 2004, 2004.
Juan A. Garay, Philip MacKenzie, and Ke Yang, Efficient and Universally Composable Committed Oblivious Transfer and Applications, Theory of Cryptography Conference (TCC 2004), Cambridge, MA, LNCS 2951, pp. 297-316, 2004, 2004.
Kedar Dhamdhere, Approximating additive distortion of embeddings into line metrics, APPROX'04, 2004.
Luis von Ahn and Laura Dabbish, Labeling Images with a Computer Game, ACM CHI 2004, 2004.
Luis von Ahn and Nicholas Hopper, Public-Key Steganography, Eurocrypt 2004, 2004.
Luis von Ahn, Manuel Blum and John Langford, How Lazy Cryptographers do AI, Communications of the ACM, Feb. 2004, 2004.
Luis von Ahn, Nicholas Hopper, and John Langford, Covert Two-Party Computation, Submitted to CRYPTO, 2004, 2004.
Maria Florina Balcan and Avrim Blum, A PAC-style Model for Learning from Labeled and Unlabeled Data, TBD, 2004.
Philip MacKenzie, Michael K. Reiter, and Ke Yang, Alternatives to Non-Malleability: Definitions, Constructions and Applications, Theory of Cryptography Conference (TCC 2004), Cambridge, MA, LNCS 2951, pp. 171-190, 2004, 2004.
R. Ravi and Amitabh Sinha, Hedging Uncertainty: Approximation Algorithms for Stochastic Optimization Problems, Proceedings of the Conference on Integer Programming and Combinatorial Ortimization (IPCO), (2004), 2004.
R. Ravi and Amitabh Sinha, Boosted Sampling: Approximation Algorithms for Stochastic Optimization, Proceedings of the ACM Symposium on the Theory of Computing (STOC), vol. , (2004), p. 417, 2004.
Ran Mendelson, Robert Endre Tarjan, Mikkel Thorup, and Uri Zwick, Melding Priority Queues, SWAT, (2004), p. 223, 2004.
Ryan Williams, A New Algorithm For Optimal Constraint Satisfaction and Its Implications, Submitted to Theoretical Computer Science. Earlier version in International Colloquium on Automata, Languages, and Programming (ICALP), 2004.
Shuchi Chawla, Uday Rajan, R. Ravi, and Amitabh Sinha, Worst-Case Payoffs of a Location Game, Proceedings of the ACM Conference on Electronic Commerce, (2004), p. 244, 2004.
Takayuki Osogami, Mor Harchol-Balter, Alan Scheller-Wolf, and Li Zhang, An Adaptive Threshold-Based Policy for Sharing Servers with Affinities, Submitted to the Technical Report CMU-CS-04-112, 2004, 2004.
Umut A. Acar, Guy Blelloch, and Robert Harper, Adaptive Memoization, ACM SIGPLAN - SIGACT Symposium on Principles of Programming Languages, (2004), 2004.
Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Maverick Woo, Dynamizing Static Algorithms with Applications to Dynamic Trees and History Independence, ACM/SIAM Symposium on Discrete Algorithms (SODA), January 2004, 2004.
Vittorio Bilo, Vineet Goyal, R. Ravi, and Mohit Singh, On the Crossing Spanning Tree Problem, APPROX'04, 2004.
Abraham D. Flaxman, Adam Tauman Kalai, H. Brendan McMahan, Online convex optimization in the bandit setting: gradient descent without a gradient, SODA 2005, 2005.
Abraham D. Flaxman, Alan Frieze, On the random 2-stage minimum spanning tree, SODA 2005, 2005.
Abraham D. Flaxman, Alan M. Frieze, Juan C. Vera, On the Average Case Performance of Some Greedy Approximation Algorithms For the Uncapacitated Facility Location Problem, Stock 2005, 2005.
Daniel K. Blandford, Guy E. Blelloch, Dictionaries Using Variable-Length Keys and Data, with Applications, SODA 2005, 2005.
Hubert T-H. Chan, Anupam Gupta, Bruce M. Maggs, Shuheng Zhou, On Hierarchical Routing in Doubling Metrics, SODA 2005, 2005.
Kedar Dhamdhere, R. Ravi, and Mohit Singh, On Two-Stage Stochastic Minimum Spanning Trees, IPCO 2005, 2005.
Kevin Chen, Dannie Durand, Notung: A Program for Dating Gene Duplications and Optimizing Gene Family Trees, RECOMB 2005, 2005.
Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Raecke, Oblivious Routing in Directed Graphs with Random Demands, Stock 2005, 2005.
Shuchi Chawla, Anupam Gupta, Harald Raecke, Embeddings of Negative-type Metrics and An Improved Approximation to Generalized Sparsest Cut, SODA 2005, 2005.
Shuchi Chawla, Anupam Gupta, Harald Raecke, An Experimental Analysis of Change Propagation in Dynamic Trees, Workshop on Algorithm Engineering and Experiments (ALENEX), January 2005, 2005.
Shuchi Chawla, Robert Krauthgamer Ravi Kumar, Yuval Rabani, D. Sivakumar, On the Hardness of Approximating Multicut and Sparsest-Cut, Conference on Computational Complexity 2005, 2005.
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, R. Ravi and Russell Schwartz, Comparison of Haplotype Motif and Block Models using the Principle of Minimum Description, Genomic Studies and the HapMap, March 15-18, 2005, University of Oxford, UK, 2005.
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, R. Ravi and Russell Schwartz, Comparison of Haplotype Motif and Block Models using the Principle of Minimum Description, CMU-CS-166, 2005.
Avrim Blum, T-H. Hubert Chan, Mugizi Robert Rwebangira, A Random-Surfer Web-Graph Model, SIAM Workshop on Analytic Algorithmics and Combinatorics (ANALCO), January 2006, 2006.
Chengwen Chris Wang, Jonathan Derryberry, Daniel Dominic Sleator, O(log log n)-Competitive Dynamic Binary Search Trees, ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006, 2006.
Chengwen Chris Wang, Jonathan Derryberry, Daniel Dominic Sleator, O(log log n)-Competitive Dynamic Binary Search Trees, ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006, 2006.
Daniel Golovin, Viswanath Nagarajan, Mohit Singh, Approximating the k-Multicut Problem, ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006, 2006.
David Tolliver and Gary Miller, Graph Partitioning by Spectral Rounding: Applications in Image Segmentation and Clustering, 2006 IEEE Conference on Computer Vision and Pattern Recognition, 1:1053-1060, 2006.
Erik D. Demaine, Uriel Feige, Mohammad Taghi Hajiaghayi, Mohammad R. Salavatipour, Combination Can Be Hard: Approximability of the Unique Coverage Problem, ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006, 2006.
Kanat Tangwongsan, Guy Blelloch, Active Data Structures and Applications to Dynamic and Kinetic Algorithms, Senior Thesis, Carnegie Mellon University, May 5, 2006, 2006.
Luis von Ahn, Mihir Kedia, and Manuel Blum, Verbosity: A Game for Collecting Common-Sense Facts, ACM CHI Notes, April 2006, 2006.
Luis von Ahn, Ruoran Liu, and Manuel Blum, Peekaboom: A Game for Locating Objects in Images, Proceedings of ACM CHI, April 2006, 2006.
Luis von Ahn, Shiry Ginosar, Mihir Kedia, Ruoran Liu, and Manuel Blum, Improving Accessibility of the Web with a Computer Game, ACM CHI Notes, April 2006, 2006.
Mohammad T. Hajiaghayi, Robert D. Kleinberg, Tom Leighton, Harald Raecke, New Lower Bounds for Oblivious Routing in Undirected Graphs, ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006, 2006.
Mohammad Taghi Hajiaghayi, Kamal Jain, Lap Chi Lau, Ion I. Mandoiu, Alexander Russell, Vijay V. Vazirani, Minimum Multicolored Subgraph Problem in Multiplex PCR Primer Set Selection and Population Haplotyping, International Conference on Computational Science (2) 2006: 758-766, 2006.
T-H. Hubert Chan, Anupam Gupta, Small Hop-diameter Sparse Spanners for Doubling Metrics, ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006, 2006.
Virginia Vassilevska, Ryan Williams, Shan Leung Maverick Woo, Confronting Hardness Using a Hybrid Approach, ACM-SIAM Symposium on Discrete Algorithms (SODA), January 2006, 2006.