SPAA 2007 Program: ================== Friday, June 8: 07:00 - 09:00 pm: SPAA reception, Tiki Pavillion -------------------------- Saturday, June 9: 08:00 - 08:45: Breakfast 08:45 - 10:00: Network Theory Pierre Fraigniaud, Cyril Gavoille, Adrian Kosowski, Emmanuelle Lebhar and Zvi Lotker Universal Augmentation Schemes for Network Navigability: Overcoming the $\sqrt n$-Barrier (SPAA Best Paper Award) Robert Krauthgamer On Triangulation of Simple Networks Ittai Abraham, Cyril Gavoille, Dahlia Malkhi and Udi Wieder Strongly-Bounded Sparse Decompositions of Minor Free Graphs 10:00 - 10:30: Morning Break 10:30 - 11:45: Scheduling Guolong Lin and Rajmohan Rajaraman Approximation Algorithms for Multiprocessor Scheduling under Uncertainty Michael A. Bender and Cynthia Phillips Scheduling DAGs on Asynchronous Processors Susanne Albers, Fabian Müller and Swen Schmelzer Speed Scaling on Parallel Processors 11:45 - 12:00: Small Break 12:00 - 12:30: Brief Announcements I: Parallel and Multicore Systems Ganapathy Senthilkumar, Murali Velamati, Naresh Jayam, Arun Thondapu, Pallav Baruah, Ashok Srinivasan, Raghunath Sharma and Shakthi Kapoor Brief Announcement: Feasibility Study of MPI implementation on the Heterogeneous Multi-Core Cell BE Architecture Srinivas Sridharan, Arun Rodrigues and Peter Kogge Brief Announcement: Evaluating Synchronization Techniques for Light-weight Multithreaded/Multicore Architectures Woongki Baek, JaeWoong Chung, Chi Cao Minh, Christos Kozyrakis and Kunle Olukotun Brief Announcement: Towards Soft Optimization Techniques for Parallel Cognitive Applications 12:30 - 01:50: Lunch Break 01:50 - 03:30: Cache-Oblivious/Cache-Aware Algorithms Elias Vicari, Riko Jacob, Michael A. Bender, Gerth S. Brodal and Rolf Fagerberg Optimal Sparse Matrix Dense Vector Multiplication in the I/O-Model Rezaul Chowdhury and Vijaya Ramachandran The Cache-Oblivious Gaussian Elimination Paradigm: Theoretical Framework, Parallelization and Experimental Evaluation Michael A. Bender, Martin Farach-Colton, Jeremy T. Fineman, Yonatan R. Fogel, Bradley C. Kuszmaul and Jelani Nelson Cache-Oblivious Streaming B-trees Kamen Yotov, Tom Roeder, Keshav Pingali, John Gunnels and Fred Gustavson An Experimental Comparison of Cache-oblivious and Cache-aware Programs 03:30 - 04:00: Afternoon Break 04:00 - 05:40: Multicore Architectures and Algorithms Shimin Chen, Phillip Gibbons, Michael Kozuch, Vasileios Liaskovitis, Anastassia Ailamaki, Guy Blelloch, Babak Falsafi, Limor Fix, Nikos Hardavellas, Todd Mowry and Chris Wilkerson Scheduling Threads for Constructive Cache Sharing on CMPs Ernie Chan, Enrique S. Quintana-Orti, Gregorio Quintana-Orti and Robert van de Geijn SuperMatrix Out-of-Order Scheduling of Matrix Operations for SMP and Multi-Core Architectures Jeffery A Brown, Rakesh Kumar and Dean Tullsen Proximity-Aware Directory-based Coherence for Multi-core Processor Architectures Guangming Tan, Ninghui Sun and Guangrong Gao A Parallel Dynamic Programming Algorithm on a Multi-core Architecture -------------------------- Sunday, June 10: 08:00 - 08:45: Breakfast 08:45 - 10:00: Distributed Network Algorithms Fabian Kuhn, Thomas Locher and Roger Wattenhofer Tight Bounds for Distributed Selection (SPAA Best Paper Award) Pierre Fraigniaud, Amos Korman and Emmanuelle Lebhar Local MST Computation with Short Advice Fabian Kuhn and Thomas Moscibroda Distributed Approximation of Capacitated Dominating Sets 10:00 - 10:30: Morning Break 10:30 - 11:45: Packing, Coloring and Load Balancing Piotr Berman, Jieun Jeong , Shiva Kasiviswanathan and Bhuvan Urgaonkar Packing to Angles and Sectors Deepak Ajwani, Khaled Elbassioni, Sathish Govindarajan and Saurabh Ray Conflict-Free Coloring for Rectangle Ranges Using $\tO(n^{.382+\epsilon})$ Colors Udi Wieder Balanced Allocations with Heterogeneous Bins 11:45 - 12:00: Small Break 12:00 - 12:30: Brief announcements II: Diverse Algorithms Amotz Bar-Noy, Panagiotis Cheilaris, Svetlana Olonetsky and Shakhar Smorodinsky Brief Announcement: Weakening the Online Adversary Just Enough to Get Optimal Conflict-free Colorings for Intervals Eric Angel, Evripidis Bampis, Fanny Pascual and Alex-Ariel Tchetgnia Brief Announcement: On the Trade-off between Truthfulness and Approximation for Scheduling Selfish Tasks Anton Lokhmotov and Alan Mycroft Brief Announcement: Optimal Bit-reversal Using Vector Permutations 12:30 - 01:50: Lunch Break 01:50 - 03:30: Concurrent Programming Michel Raynal and Gadi Taubenfeld The Notion of a Timed Register and its Application to Indulgent Synchronization Michael Spear, Arrvindh Shriraman, Luke Dalessandro, Sandhya Dwarkadas and Michael Scott Nonblocking Transactions Without Indirection Using Alert-on-Update Torvald Riegel, Christof Fetzer and Pascal Felber Time-based Transactional Memory with Scalable Time Bases Shivali Agarwal, Rajkishore Barik, Dan Bonachea, Vivek Sarkar, Rudrapatna K. Shyamasundar and Katherine Yelick Deadlock-Free Scheduling of X10 Computations with Bounded Resources 03:30 - 04:00: Afternoon Break 04:00 - 05:15: Algorithms for Wireless Networks Joseph Wun-Tat Chan, Francis Y. L. Chin, Deshi Ye and Yong Zhang Online Frequency Allocation in Cellular Networks Petra Berenbrink, Colin Cooper and Zengjian Hu Energy Efficient Randomized Communication in Unknown AdHoc Networks Miroslaw Dynia, Jaroslaw Kutylowski, Friedhelm Meyer auf der Heide and Jonas Schrieb Local Strategies for Maintaining a Chain of Relay Stations between an Explorer and a Base Station 05:45 - 07:00: Turing Award Lecture (FCRC Plenary Session) 07:00 - 10:00: SPAA Banquet and Business Meeting, Pacific 3 -------------------------- Monday, June 11: 08:00 - 08:45: Breakfast 08:45 - 10:00: Latency and Makespan John Douceur, Jay Lorch and Thomas Moscibroda Maximizing Total Upload in Latency-Sensitive P2P Applications Jack J. Dongarra, Emmanuel Jeannot, Erik Saule and Zhiao Shi Bi-objective Scheduling Algorithms for Optimizing Makespan and Reliability on Heterogeneous Systems Erik D. Demaine, Mohammad Ghodsi, MohammadTaghi Hajiaghayi, Amin S. Sayedi-Roshkhar and Morteza Zadimoghaddam Scheduling to Minimize Gaps and Power Consumption 10:00 - 10:30: Morning Break 10:30 - 11:00: Brief Announcements III: Parallel Computing Bradley C. Kuszmaul Brief Announcement: Cilk Provides the Best Overall Productivity for High Performance Computing (and Won the HPC Challenge Award to Prove It) Xingzhi Wen and Uzi Vishkin Brief Announcement: PRAM on Chip: First Commitment to Silicon Craig Zilles and Ravi Rajwar Brief Announcement: Transactional Memory and the Birthday Paradox 11:00 - 11:30: Small Break 11:30 - 12:30: Keynote Speech (FCRC Plenary Session) 12:30 - 01:50: Lunch Break 01:50 - 03:30: Online Algorithms and Games Adi Rosen and Gabriel Scalosub Rate vs. Buffer Size - Greedy Information Gathering on the Line Baruch Awerbuch and Thomas P. Hayes Online Collaborative Filtering with Nearly Optimal Dynamic Regret Yossi Azar, Iftah Gamzu and Shai Gutner Truthful Unsplittable Flow for Large Capacity Networks Angelo Fanelli, Michele Flammini and Luca Moscardelli On the Convergence of Multicast Games in Directed Networks 03:30 - 04:00: Afternoon Break 04:00 - 05:15: Algorithms and Architectures Benoit Hudson, Gary Miller and Todd Phillips Sparse Parallel Delaunay Mesh Refinement Timothy Furtak, José Nelson Amaral and Robert Niewiadomski Using SIMD Registers and Instructions to Enable Instruction-Level Parallelism in Sorting Algorithms Koji Kobayashi, Shuichi Miyazaki and Yasuo Okabe A Tight Bound on Online Buffer Management for Two-port Shared-Memory Switches