Guy Blelloch: Publications

Guy E. Blelloch: Publications

A probably more complete list of papers, along with full bibliographical information can be found at the University of Trier Computer Science Bibliography database.

2008

Daniel Spoonhower, Guy E. Blelloch, Robert Harper, Phillip B. Gibbons
Space Profiling for Parallel Functional Programs.
ACM International Conference on Functional Programming (ICFP), September 2008.

Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, Duru Trkoglu
Robust Kinetic Convex Hulls in 3D.
European Symposium on Algorithms (ESA), September 2008.

Guy E. Blelloch, Virginia Vassilevska, Ryan Williams
A New Combinatorial Approach for Sparse Graph Problems.
International Colloquium on Automata, Languages and Programming (ICALP), July 2008.

Guy E. Blelloch, Phillip B. Gibbons, S. Harsha Vardhan
Combinable Memory-Block Transactions.
Proc. ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 2008.

Guy E. Blelloch, Daniel Golovin, Virginia Vassilevska
Uniquely Represented Data Structures for Computational Geometry.
Proc. Scandinavian Workshop on Algorithm Theory (SWAT), July 2008.

Srinath Sridhar, Fumei Lam, Guy E. Blelloch, R. Ravi, Russell Schwartz
Mixed Integer Linear Programming for Maximum-Parsimony Phylogeny Inference.
ACM/IEEE Transactions on Computational Biology and Bioinformatics (TCBB), July 2008.

Daniel K. Blandford and Guy E. Blelloch.
Compact Dictionaries for Variable-Length Keys and Data, with applications.
ACM Transactions on Algorithms, May 2008.

Guy E. Blelloch
Space-Efficient Dynamic Orthogonal Point Location, Segment Intersection, and Range Reporting.
SIAM/ACM Symposium on Discrite Algortithms (SODA), January 2008.
Rezaul A. Chowdhury, Vijaya Ramachandran, Guy E. Blelloch, Phillip B. Gibbons, Shimin Chen and Michael Kozuch.
Provably Good Multicore Cache Performance for Divide-and-Conquer Algorithms.
SIAM/ACM Symposium on Discrite Algortithms (SODA), January 2008.

2007

Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi and Russell Schwartz
Algorithms for Efficient Near-Perfect Phylogenetic Tree Reconstruction in Theory and Practice.
ACM/IEEE Transactions on Computational Biology and Bioinformatics (TCBB), October 2007.
Guy E. Blelloch and Daniel Golovin.
Strongly History-Independent Hashing with Applications
IEEE Symposium on Foundations of Computer Science (FOCS), October 2007.
Shimin Chen, Phillip B. Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia Ailamaki, Guy E. Blelloch, Babak Falsafi, Limor Fix, Nikos Hardavellas, Todd C. Mowry, and Chris Wilkerson.
Scheduling threads for constructive cache sharing on CMPs.
Proc. ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 2007.
Umut A. Acar, Guy E. Blelloch, and Kanat Tangwongsan.
Kinetic 3D convex hulls via self-adjusting computation. (Video presentation, Short description)
Proc. ACM Symposium on Computational Geometry (SoCG), June 2007.
Srinath Sridhar, Fumei Lam, Guy Blelloch, R. Ravi and Russell Schwartz.
Efficiently Finding the Most Parsimonious Phylogenetic Tree via Linear Programming.
Proc. International Symposium on Bioinformatics Research and Applications. (ISBRA), Best Paper Award, May 2007.

2006

Umut Acar, Guy Blelloch, and Robert Harper.
Adaptive Functional Programming.
ACM Transactions on Programming Languages and Systems (TOPLAS), November 2006.
Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, and Jorge L. Vittes.
Kinetic Algorithms via Self-Adjusting Computation.
European Symposium on Algorithms (ESA), September 2006.
Srinath Sridhar, Guy E. Blelloch, R. Ravi, and Russell Schwartz.
Optimal Imperfect Phylogeny Reconstruction and Haplotyping (IPPH).
Computational Systems Bioinformatics (CSB) Conference, August 2006.
Guy E. Blelloch, Kedar Dhamdhere, Eran Halperin, R. Ravi, Russell Schwartz, and Srinath Sridhar.
Fixed Parameter tractability of Binary Near-Perfect Phylogenetic Tree Reconstruction.
International Colloquium on Automata, Languages and Programming (ICALP), July 2006.
See journal version
Daniel K. Blandford, Guy E. Blelloch, and Clemens Kadow.
Engineering a Compact Parallel Delaunay Algorithm in 3D.
ACM Symposium on Computational Geometry (SoCG), June 2006.
Umut A. Acar, Guy E. Blelloch, Matthias Blume, and Kanat Tangwongsan.
An Experimental Analysis of Self-Adjusting Computation.
ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), June 2006.
Srinath Sridhar, Kedar Dhamdhere, Guy E. Blelloch, Eran Halperin, R. Ravi, and Russell Schwartz.
Simple Reconstruction of Binary Near-Perfect Phylogenetic Trees.
International Workshop on Bioinformatics Research and Applications (IWBRA), May 2006.
See journal version

2005

Umut Acar, Guy Blelloch, Matthias Blume, Robert Harper, and Kanat Tangwongsan.
A Library for Self-Adjusting Computation.
ACM SIGPLAN Workshop on ML, September 2005.
Daniel Spoonhower, Guy Blelloch, and Robert Harper.
Objects and their collection: Using page residency to balance tradeoffs in tracing garbage collection
ACM/USENIX international conference on Virtual execution environments, June 2005.
Daniel K. Blandford, Guy E. Blelloch, David E. Cardoze, and Clemens Kadow.
Compact representations of simplicial meshes in two and three dimensions.
International Journal of Computational Geometry and Applications, February 2005.
Daniel K. Blandford and Guy E. Blelloch.
Dictionaries using variable-length keys and data, with applications.
SIAM/ACM Symposium on Discrite Algortithms (SODA), January 2005.
See journal version
Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes.
An Experimental Analysis of Change Propagation in Dynamic Trees
Workshop on Algorithms Engineering and Experiments (ALENEX), January 2005.

2004

Guy E. Blelloch, and Phillip B. Gibbons
Effectively Sharing a Cache Among Threads
ACM Symposium on Parallelism in Algorithms and Architecture (SPAA), June 2004.
Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, and Shan Leung Maverick Woo
Dynamizing Static Algorithms, with Applications to Dynamic Trees and History Independence
ACM/SIAM Symposium on Discrete Algorithms (SODA), January 2004.
Daniel K. Blandford and Guy E. Blelloch.
Compact Representations of Ordered Sets
ACM/SIAM Symposium on Discrete Algorithms (SODA), January 2004.
Daniel Blandford, Guy E. Blelloch, and Ian Kash.
An Experimental Analysis of a Compact Graph Representation
Workshop on Algorithms Engineering and Experiments (ALENEX), January 2004.

2003

Aleksandar Nanevski, Guy Blelloch, Robert Harper.
Automatic Generation of Staged Geometric Predicates
Higher-Order and Symbolic Computation, 16(4), December 2003.
Guy E. Blelloch, Perry Cheng, and Phillip B. Gibbons.
Scalable Room Synchronizations
Theory of Computing Systems (TCS), 36(5), September 2003.
Daniel K. Blandford, Guy E. Blelloch, David E. Cardoze, and Clemens Kadow.
Compact Representations of Simplicial Meshes in Two and Three Dimensions
International Meshing Roundtable (IMR), September 2003.
Umut A. Acar, Guy E. Blelloch and, Robert Harper.
Selective Memoization
ACM Symposium on Principles of Programming Languages (POPL), January 2003.
Daniel Blandford, Guy E. Blelloch, and Ian Kash.
Compact Representations of Separable Graphs.
ACM/SIAM Symposium on Discrete Algorithms (SODA), January 2003.
Guy E. Blelloch, Bruce Maggs, and Maverick Woo.
Space-Efficient Finger Search on Degree-Balanced Search Trees.
ACM/SIAM Symposium on Discrete Algorithms (SODA), January 2003.

2002

Umut Acar, Guy Blelloch, and Robert Blumofe.
The Data Locality of Work Stealing.
Theory of Computing Systems (TCS), 35(3), May 2002.
Daniel Blandford and Guy E. Blelloch.
Index Compression through Document Reordering.
IEEE Data Compression Conference (DCC), April 2002.
Umut Acar, Guy Blelloch, and Robert Harper.
Adaptive Functional Programming.
ACM Symposium on Principles of Programming Languages (POPL), January 2002.
See journal version

2001

Guy Blelloch, Hal Burch, Karl Crary, Robert Harper, Gary Miller, Noel Walkington.
Persistent Triangulations.
Journal of Functional Programming (JFP), 11(5), September 2001.
Aleksandar Nanevski, Guy Blelloch, and Robert Harper.
Automatic Generation of Staged Geometric Predicates.
ACM International Conference on Functional Programming (ICFP), September 2001.
Perry Cheng and Guy E. Blelloch.
A Parallel, Real-Time Garbage Collector.
ACM SIGPLAN Symposium on Programming Language Design and Implementation (PLDI), June 2001.
Guy E. Blelloch, Perry Cheng and Phillip B. Gibbons.
Room synchronizations
ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 2001.

2000

James F. Antaki, Guy E. Blelloch, Omar Ghattas, Ivan Malcevic, Gary L. Miller, and Noel Walkington.
A Parallel Dynamic-Mesh Lagrangian Method for Simulation of Flows with Dynamic Interfaces.
Supercomputing 2000, November 2000.

1999

Guy E. Blelloch and Perry Cheng.
On Bounding Time and Space for Multiprocessor Garbage Collection.
ACM SIGPLAN Symposium on Programming Language Design and Implementation (PLDI), May 1999.
G. E. Blelloch, P. Gibbons and Y. Matias.
Provably Efficient Scheduling for Languages with Fine-Grained Parallelism.
Journal of the ACM (JACM), 46(2), March 1999.
Guy E. Blelloch, Jonathan C. Hardwick, Gary L. Miller, and Dafna Talmor.
Design and Implementation of a Practical Parallel Delaunay Algorithm.
Algorithmica, 24(3/4), 1999.
Girija J. Narlikar and Guy E. Blelloch.
Space-Efficient Implementation of Nested Parallelism
ACM Transactions on Programming Languages and Systems (TOPLAS), 21(1), January 1999.
John Greiner and Guy E. Blelloch.
A Provably Time-Efficient Parallel Implementation of Full Speculation
ACM Transactions on Programming Languages and Systems (TOPLAS), 21(2), March 1999.
Guy E. Blelloch and Margaret Reid-Miller.
Pipelining with Futures
Theory of Computing Systems (TCS), 32(3), 1999.

1998

Guy E. Blelloch and Margaret Reid-Miller.
Fast Set Operations Using Treaps.
ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 1998.

1997 and before

Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, and Girija Narlikar.
Space-Efficient Scheduling of Parallelism with Synchronization Variables
ACM Symposium on Parallel Algorithms and Architectures (SPAA), June 1997.
Guy Blelloch and Girija Narlikar.
A Practical Comparison of N-Body Algorithms.
Proceedings DIMACS implementation challenge, 1997.
Guy E. Blelloch and Gary.~L. Miller and Dafna Talmor.
Developing a practical projection-based parallel Delaunay algorithm.
Proceedings ACM Symposium on Computational Geometry (SCG), May 1996.
Guy E. Blelloch and John Greiner.
A Provable Time and Space Efficient Implementation of NESL
ACM International Conference on Functional Programming (ICFP), May 1996.
Guy Blelloch.
Programming Parallel Algorithms.
Communications of the ACM (CACM), 39(3), March 1996.
John Greiner and Guy E. Blelloch.
A Provably Efficient Parallel Implementation of Full Speculation
ACM Symposium on Principles of Programming Languages (POPL), January 1996.
Guy E. Blelloch, Phillip B. Gibbons, Yossi Matias, and Marco Zagha .
Accounting for Memory Bank Contention and Delay in High-Bandwidth Multiprocessors.
ACM Symposium on Parallel Algorithms and Architectures (SPAA), July 1995.
Guy E. Blelloch and John Greiner.
Parallelism in Sequential Functional Languages
ACM Symposium on Functional Programming and Computer Architecture (FPCA), June 1995.
Guy E. Blelloch, Siddhartha Chatterjee, and Marco Zagha.
Solving Linear Recurrences with Loop Raking.
Journal of Parallel and Distributed Computing (JPDC), February 1995.
Guy E. Blelloch, Siddhartha Chatterjee, Jonathan C. Hardwick, Jay Sipelstein, and Marco Zagha.
Implementation of a Portable Nested Data-Parallel Language.
Journal of Parallel and Distributed Computing (JPDC), 21(1), April 1994.
Guy E. Blelloch.
Prefix Sums and Their Applications.
In "Synthesis of Parallel Algorithms", Edited by John H. Reif, Morgan Kaufmann, 1991.
Marco Zagha and Guy E. Blelloch.
Radix Sort for Vector Multiprocessors.
Supercomputing '91, November 1991.
Guy E. Blelloch, Charles E. Leiserson, Bruce M. Maggs, C. Gregory Plaxton, Stephen J. Smith, and Marco Zagha.
A Comparison of Sorting Algorithms for the Connection Machine CM-2.
ACM Symposium on Parallel Algorithms and Architectures (SPAA), 1991.
Siddhartha Chatterjee, Guy E. Blelloch, Marco Zagha.
Scan primitives for vector computers.
Supercomputing 1990. November 1990.
Guy Blelloch.
Vector Models for Data-Parallel Computing.
MIT Press. ISBN 0-262-02313-X. 1990.
(Thanks to John Owens for getting the 16 year old LaTeX running to make this work.)