Communications of the ACM

Technical Perspective: The Ray-Tracing Engine That Could

Matt Pharr

It has been an open question whether it is possible to build GPU-targeted high-performance software systems that are themselves...

GPU Ray Tracing

Steven G. Parker, Heiko Friedrich, David Luebke, Keith Morley, James Bigler, Jared Hoberock, David McAllister, Austin Robison, Andreas Dietrich, Greg Humphreys, Morgan McGuire, Martin Stich

The NVIDIA OptiX ray tracing engine builds on the key observation that most ray tracing algorithms can be implemented using a...

Discriminative Learning with Latent Variables for Cluttered Indoor Scene Understanding

Huayan Wang, Stephen Gould, Daphne Roller

We address the problem of understanding an indoor scene from a single image in terms of recovering the room geometry (floor,...

Technical Perspective: Understanding Pictures of Rooms

David Forsyth

The rich world is getting older, so we will see many efforts to build robots that can provide some in-home care for frail people...

Technical Perspective: Video Quality Assessment in the Age of Internet Video

David Oran

With video delivery, it appears that once again "the Internet changes everything." In this changed environment, what measures...

Understanding the Impact of Video Quality on User Engagement

Florin Dobrian, Asad Awan, Dilip Joseph, Aditya Ganjam, Jibin Zhan, Vyas Sekar, Ion Stoica, Hui Zhang

As Internet-based videos become mainstream, user expectation for high quality is constantly increasing. In this context, it is...

Technical Perspective: Is Dark Silicon Real?

Pradip Bose

The microprocessor chip R&D community has been well aware of the so-called "power wall" challenge for over a decade. The following...

Power Challenges May End the Multicore Era

Hadi Esmaeilzadeh, Emily Blem, Renée St. Amant, Karthikeyan Sankaralingam, Doug Burger

Tthe microprocessor industry has shifted to multicore scaling as its principal strategy for continuing performance growth. However...

Technical Perspective: Visualization, Understanding, and Design

Doug DeCarlo, Matthew Stone

Photographs capture the moment; paintings convey perception, impression, and feeling; illustrations tell stories. Computer graphics...

Technical Perspective: Finding People in Depth

James M. Rehg

The following article by Shotton et al. describes a landmark computer vision system that takes a single depth image containing...

Real-Time Human Pose Recognition in Parts from Single Depth Images

Jamie Shotton, Toby Sharp, Alex Kipman, Andrew Fitzgibbon, Mark Finocchio, Andrew Blake, Mat Cook, Richard Moore

We propose a new method to quickly and accurately predict human pose — the 3-D positions of body joints — from a single depth...

Illustrating How Mechanical Assemblies Work

Niloy J. Mitra, Yong-Liang Yang, Dong-Ming Yan, Wilmot Li, Maneesh Agrawala

How-things-work visualizations use a variety of visual techniques to depict the operation of complex mechanical assemblies. We...

Technical Perspective: High-Level Data Structures

Yannis Smaragdakis

This lifting of data structure thinking to the relational level has long inspired computer scientists. In "An Introduction to...

Technical Perspective: Natural Algorithms in a Networked World

Ali Jadbabaie

How do birds flock and fish school? How do individuals in a social network reach agreement, even though they are often only influenced...

Natural Algorithms and Influence Systems

Bernard Chazelle

Algorithms lay the grounds for numerical simulations and, crucially, provide a powerful framework for their analysis. The new...

An Introduction to Data Representation Synthesis

Peter Hawkins, Martin Rinard, Alex Aiken, Mooly Sagiv, Kathleen Fisher

We consider the problem of specifying combinations of data structures with complex sharing in a manner that is declarative and...

Technical Perspective: The Realities of Home Broadband

Henning Schulzinne

Buying residential broadband services seems relatively simple: pick among a small number of plans, and then compare similar plans...

Measuring Home Broadband Performance

Srikanth Sundaresan, Walter de Donato, Nick Feamster, Renata Teixeira, Sam Crawford, Antonio Pescapè

We present the results from the first study of Internet access link performance measured directly from home routers. Our findings...

Technical Perspective: Open Platforms for Computational Photography

Richard Szeliski

A fundamental impediment to the widespread development and deployment of in-camera algorithms is the lack of a clean open architecture...

The Frankencamera: An Experimental Platform for Computational Photography

Andrew Adams, David E. Jacobs, Jennifer Dolson, Marius Tico, Kari Pulli, Eino-Ville Talvala, Boris Ajdin, Daniel Vaquero, Hendrik P. A. Lensch, Mark Horowitz, Sung Hee Park, Natasha Gelfand, Jongmin Baek, Wojciech Matusik, Marc Levoy

Progress in computational photography has been hampered by the lack of a portable, programmable camera with sufficient image...

Technical Perspective: Graph Embeddings and Linear Equations

Bruce Hendrickson

Algorithmic advances can come from the most unexpected places. The following paper describes an emerging approach to solving...

A Fast Solver for a Class of Linear Systems

Ioannis Koutis, Gary L. Miller, Richard Peng

The solution of linear systems is a problem of fundamental theoretical importance but also one with a myriad of applications...

Technical Perspective: A High-Dimensional Surprise

Rocco A. Servedio

High-dimensional space is a counterintuitive place, where natural geometric intuitions from the familiar three-dimensional world...

Spherical Cubes: Optimal Foams from Computational Hardness Amplification

Guy Kindler, Anup Rao, Ryan O'Donnell, Avi Wigderson

Foam problems are about how to best partition space into bubbles of minimal surface area. We investigate the case where one unit...

The Word-Gesture Keyboard: Reimagining Keyboard Interaction

Shumin Zhai, Per Ola Kristensson

As computing technologies expanded beyond the confines of the desktop, the need for effective text entry methods alternative...

Technical Perspective: SQL on an Encrypted Database

Dan Suciu

There is some risk in trusting the cloud providers with sensitive data. Why not encrypt the data stored in cloud services?

CryptDB: Processing Queries on an Encrypted Database

Raluca Ada Popa, Catherine M. S. Redfield, Nickolai Zeldovich, Hari Balakrishnan

An ideal solution to satisfying the dual goals of protecting data confidentiality and running computations is to enable a server...

Technical Perspective: Innovative Interaction: From Concept to the Wild

William A. Buxton

The history of the relationship between writing systems and technology is as long as it is varied. Likewise, the challenge of...

Technical Perspective: Example-Driven Program Synthesis for End-User Programming

Martin C. Rinard

As information technology has come to permeate our society, broader classes of users have developed the need for more sophisticated...

Spreadsheet Data Manipulation Using Examples

Sumit Gulwani, William R. Harris, Rishabh Singh

Millions of computer end users need to perform tasks over large spreadsheet data, yet lack the programming knowledge to do such...

Technical Perspective: Proving Programs Continuous

Andreas Zeller

Proving a program's correctness is usually an all-or-nothing game.

Continuity and Robustness of Programs

Swarat Chaudhuri, Sumit Gulwani, Roberto Lublinerman

Computer scientists have long believed that software is different from physical systems in one fundamental way: while the latter...

Technical Perspective: For Better or Worse, Benchmarks Shape a Field

David Patterson

Like other IT fields, computer architects initially reported incomparable results. We quickly saw the folly of this approach....

Looking Back and Looking Forward: Power, Performance, and Upheaval

Hadi Esmaeilzadeh, Ting Cao, Xi Yang, Stephen M. Blackburn, Kathryn S. McKinley

The past 10 years have delivered two significant revolutions. Microprocessor design has been transformed — leading to multicore...

Technical Perspective: Reconstructing the Unknown, Balancing Structure and Uncertainty

Pablo A. Parrilo

The problem of estimating or reconstructing an unknown structured object from incomplete, partial, noisy measurements is a fundamental...

Exact Matrix Completion via Convex Optimization

Emmanuel Candès, Benjamin Recht

Suppose that one observes an incomplete subset of entries selected from a low-rank matrix. When is it possible to complete the...

Technical Perspective: Why Study the Price of Anarchy?

Amos Fiat

In 1999, Elias Koutsoupias and Christos Papadimitriou initiated the study of "How much worse off are we due to selfishness?"...

Intrinsic Robustness of the Price of Anarchy

Tim Roughgarden

The price of anarchy, defined as the ratio of the worst-case objective function value of a Nash equilibrium of a game and that...

Technical Perspective: The Fox and the Hedgehog

Peter Lee

"The fox knows many things, but the hedgehog knows one big thing." Philosophers have used this line, attributed to the ancient...

Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs

Tiark Rompf, Martin Odersky

Good software engineering practice demands generalization and abstraction, whereas high performance demands specialization and...

Technical Perspective: An Experiment in Determinism

Steven Hand

It is widely held that parallel programming is far more difficult and error prone than writing sequential code. In particular...

Efficient System-Enforced Deterministic Parallelism

Amittai Aviram, Shu-Chun Weng, Sen Hu, Bryan Ford

We introduce a new parallel programming model addressing the issues facing current methods of executing parallel programs deterministically...

A Massively Parallel Adaptive Fast Multipole Method on Heterogeneous Architectures

Ilya Lashuk, Aparna Chandramowlishwaran, Harper Langston, Tuan-Anh Nguyen, Rahul Sampath, Aashay Shringarpure, Richard Vuduc, Lexing Ying, Denis Zorin, George Biros

We describe a parallel fast multipole method for highly nonuniform distributions of particles. We employ both distributed memory...

Technical Perspective: Best Algorithms + Best Computers = Powerful Match

William Gropp

Say you want to simulate the motion over time of the stars in a galaxy to learn about how galaxies formed and why the universe...

Technical Perspective: Who Knows?: Searching for Expertise on the Social Web

Ed H. Chi

It is difficult to remember what people had to do to find the answer to a question before the Web. One option might be to call...

Searching the Village: Models and Methods for Social Search

Damon Horowitz, Sepandar D. Kamvar

With Aardvark, a social search engine, users ask a question, either by IM, e-mail, Web input, text message, or voice. Aardvark...

Technical Perspective: Building Robust Dynamical Simulation Systems

Dinesh Manocha

Computational power has been widely used to predict the behavior of dynamical systems using computer simulations, which are often...

Asynchronous Contact Mechanics

David Harmon, Etienne Vouga, Breannan Smith, Rasmus Tamstorf, Eitan Grinspun

Physicists have long observed physical phenomena and developed mathematical models to describe them. The advent of computers...

Technical Perspective: A New Way to Search Game Trees

Michael L. Littman

Researchers in artificial intelligence know that computers still lag far behind human levels of play in many games of strategy...

The Grand Challenge of Computer Go: Monte Carlo Tree Search and Extensions

Sylvain Gelly, Levente Kocsis, Marc Schoenauer, Michèle Sebag, David Silver, Csaba Szepesvári, Olivier Teytaud

The ancient oriental game of Go has long been considered a grand challenge for artificial intelligence. However, computer Go...

Technical Perspective: The Benefits of Capability-Based Protection

Steven D. Gribble

Affordable personal computing hardware and the usable GUI-based PC operating systems made the vision of "a computer on every...

A Taste of Capsicum: Practical Capabilities for UNIX

Robert N. M. Watson, Jonathan Anderson, Ben Laurie, Kris Kennaway

Capsicum is a lightweight operating system capability and sandbox framework planned for inclusion in FreeBSD 9. Capsicum extends...

Technical Perspective: Compiling What to How

Rastislav Bodik

The following paper by Viktor Kuncak et al. integrates declarative programming into a general-purpose language, allowing one...

Software Synthesis Procedures

Viktor Kuncak, Mikaël Mayer, Ruzica Piskac, Philippe Suter

Automated synthesis of program fragments from specifications can make programs easier to write and easier to reason about. To...

Technical Perspective: Modeling High-Dimensional Data

Santosh S. Vempala

Data in high dimension is difficult to visualize and understand. This has always been the case and is even more apparent now...

Disentangling Gaussians

Adam Tauman Kalai, Ankur Moitra, Gregory Valiant

The Gaussian mixture model is one of the oldest and most widely used statistical models. Our work focuses on the case where the...

Technical Perspective: Safety First!

Xavier Leroy

Software misbehaves all too often. This is a truism, but also the driving force behind many computing techniques intended to...

Safe to the Last Instruction: Automated Verification of a Type-Safe Operating System

Jean Yang, Chris Hawblitzel

High-level computer applications build on services provided by lower-level software layers. Unfortunately, today's low-level...

Technical Perspective: Content-Centric Networking

Jim Kurose

Much has changed in the 50 years since the invention of packet switching and the early network designs and deployments that would...

Networking Named Content

Van Jacobson, Diana K. Smetters, James D. Thornton, Michael Plass, Nick Briggs, Rebecca Braynard

Current network use is dominated by content distribution and retrieval yet current networking protocols are designed for conversations...

Technical Perspective: Where Do People Draw Lines?

Frédo Durand

Computer graphics once focused exclusively on realism. The field eventually broadened to include other pictorial styles. The...

Where Do People Draw Lines?

Forrester Cole, Aleksey Golovinskiy, Alex Limpaecher, Heather Stoddart Barros, Adam Finkelstein, Thomas Funkhouser, Szymon Rusinkiewicz

This paper presents the results of a study in which artists made line drawings intended to convey specific 3D shapes.

Technical Perspective: Making Untrusted Code Useful

Butler Lampson

The following paper combines two important themes in secure computing: assurance and information flow control. For high assurance...

Making Information Flow Explicit in HiStar

Nickolai Zeldovich, Silas Boyd-Wickizer, Eddie Kohler, David Mazières

Features of the new HiStar operating system permit several novel applications, including privacy-preserving, untrusted virus...

Technical Perspective: Anonymity Is Not Privacy

Vitaly Shmatikov

We live in an era of data abundance. Every aspect of our online and offline behavior is captured and analyzed. The companies...

Wherefore Art Thou R3579X?: Anonymized Social Networks, Hidden Patterns, and Structural Steganography

Lars Backstrom, Cynthia Dwork, Jon Kleinberg

In a social network, nodes correspond to people or other social entities, and edges correspond to social links between them....

Technical Perspective: A Perfect 'Match'

William T. Freeman

In a breakthrough contribution, the authors of the paper that follows have developed an efficient way to find approximate nearest...

The PatchMatch Randomized Matching Algorithm for Image Manipulation

Connelly Barnes, Dan B. Goldman, Eli Shechtman, Adam Finkelstein

This paper presents a new randomized algorithm for quickly finding approximate nearest neighbor matches between image patches...

Technical Perspective: Visual Reconstruction

Carlo Tomasi

Nearly 460,000 Flickr pictures were used to create detailed three-dimensional geometry and colors of famous landmarks and monuments...

Building Rome in a Day

Sameer Agarwal, Yasutaka Furukawa, Noah Snavely, Ian Simon, Brian Curless, Steven M. Seitz, Richard Szeliski

We present a system that can reconstruct 3D geometry from large, unorganized collections of photographs. Our experimental results...

Technical Perspective: A Better Way to Learn Features

Geoffrey E. Hinton

A typical machine learning program uses weighted combinations of features to discriminate between classes or to predict real-valued...

Unsupervised Learning of Hierarchical Representations with Convolutional Deep Belief Networks

Honglak Lee, Roger Grosse, Rajesh Ranganath, Andrew Y. Ng

There has been much interest in unsupervised learning of hierarchical generative models such as deep belief networks (DBNs);...

Technical Perspective: Power Efficiency as the #1 Design Constraint

Charles Moore

Moore's Law, and associated observations by Bob Dennard, describe key technical foundations  of the semiconductor industry. Taking...

Understanding Sources of Ineffciency in General-Purpose Chips

Rehan Hameed, Wajahat Qadeer, Megan Wachs, Omid Azizi, Alex Solomatnikov, Benjamin C. Lee, Stephen Richardson, Christos Kozyrakis, Mark Horowitz

To better understand what improvement in processor efficiency is possible, we quantify the performance and energy overheads of...

Technical Perspective: Making Browser Extensions Secure

Christopher Kruegel

Vulnerabilities in browsers and their extensions have become the primary venue through which cyber criminals compromise the security...

Vetting Browser Extensions for Security Vulnerabilities with VEX

Sruthi Bandhakavi, Nandit Tiku, Wyatt Pittman, Samuel T. King, P. Madhusudan, Marianne Winslett

The browser has become the de facto platform for everyday computation and a popular target for attackers of computer systems....

Technical Perspective: Abstracting Abstract Machines

Olivier Danvy, Jan Midtgaard

Semanticss-based program analysis requires one to (1) start from a "friendly" semantics; (2) design a "congenial" lattice of...

Abstracting Abstract Machines: A Systematic Approach to Higher-Order Program Analysis

David Van Horn, Matthew Might

Predictive models are fundamental to engineering reliable software systems. However, designing conservative, computable approximations...

Technical Perspective: Skintroducing the Future

Scott Klemmer

Two critical goals for mobile devices seem intrinsically in conflict. For carrying, the smaller the better. Yet for interacting...

Skinput: Appropriating the Skin as an Interactive Canvas

Chris Harrison, Desney Tan, Dan Morris

Skinput is a technology that appropriates the skin as an input surface by analyzing mechanical vibrations that propagate through...

Technical Perspective: Sketches Get Sketchier

Peter J. Haas

Are data synopses — such as the hash-based sketches discussed by Li and König — still needed for querying massive datasets? The...

Theory and Applications of b-Bit Minwise Hashing

Ping Li, Arnd Christian König

Efficient (approximate) computation of set similarity in very large datasets is a common task with many applications in information...

Technical Perspective: Is Scale Your Enemy, Or Is Scale Your Friend?

John Ousterhout

Scale has been the single most important force driving changes in system software over the last decade. Its impact is most obvious...

Debugging in the (Very) Large: Ten Years of Implementation and Experience

Kinshuman Kinshumann, Kirk Glerum, Steve Greenberg, Gabriel Aul, Vince Orgovan, Greg Nichols, David Grant, Gretchen Loihle, Galen Hunt

Windows Error Reporting (WER) is a distributed system that automates the processing of error reports coming from an installed...

Technical Perspective: FAWN: A Fast Array of Wimpy Nodes

Luiz André Barroso

The emergence of wimpy processors and FLASH met a promising deployment scenario in the field of large-scale data centers. The...

FAWN: A Fast Array of Wimpy Nodes

David G. Andersen, Jason Franklin, Michael Kaminsky, Amar Phanishayee, Lawrence Tan, Vijay Vasudevan

This paper presents a fast array of wimpy nodes — FAWN — an approach for achieving low-power data-intensive data-center computing...

Technical Perspective: Markov Meets Bayes

Fernando Pereira

The history of probabilistic sequence models dates back to Markov at the turn of the last century. Though informed by decades...

The Sequence Memoizer

Frank Wood, Jan Gasthaus, Cédric Archambeau, Lancelot James, Yee Whye Teh

The sequence memoizer is a new hierarchical Bayesian model for discrete sequence data that captures long range dependencies and...

Technical Perspective: The Quest for a Logic for Polynomial-Time Computation

Phokion G. Kolaitis

The interaction between computation and logic goes back to the beginnings of computer science with the development of computability...

From Polynomial Time Queries to Graph Structure Theory

Martin Grohe

We give a logical characterization of the polynomial-time properties of graphs with excluded minors.

Technical Perspective: Images Everywhere Looking for Models

Guillermo Sapiro

About 5,000 images per minute are uploaded to the photo-sharing site http://www.flickr.com/; over 7,000,000 a day. Such images...

Self-Similarity-based Image Denoising

Antoni Buades, Bartomeu Coll, Jean-Michel Morel

The search for efficient image denoising methods is still a valid challenge at the crossing of functional analysis and statistics...

Technical Perspective: Data Analysis at Astonishing Speed

Michael J. Franklin

The importance of data analysis has never been clearer. Globe-spanning scientific collaborations are exploring data-intensive...

Dremel: Interactive Analysis of Web-Scale Datasets

Sergey Melnik, Andrey Gubarev, Jing Jing Long, Geoffrey Romer, Shiva Shivakumar, Matt Tolton, Theo Vassilakis

Dremel is a scalable, interactive ad hoc query system for analysis of read-only nested data. By combining multilevel execution...

Technical Perspective: Patterns Hidden from Simple Algorithms

Madhu Sudan

Is the number 9021960864034418159813 random? To my limited mind, the string  appears random. Is there a way to use some formal...

Poly-logarithmic Independence Fools Bounded-Depth Boolean Circuits

Mark Braverman

The question of determining which (weak) forms of randomness "fool" (or seem totally random to) a given algorithm is a basic...

Technical Perspective: Concerto for Violin and Markov Model

Juan Bello, Yann LeCun, Robert Rowe

In the opening of Sibelius' Violin Concerto, a soloist plays delicately. The orchestra responds in kind. As the piece progresses...

The Informatics Philharmonic

Christopher Raphael

A system for musical accompaniment is presented in which a computer-driven orchestra follows and learns from a soloist in a concerto...

Technical Perspective: Complex Financial Products: Caveat Emptor

David C. Parkes

CDOs are examples of financial derivatives, with a value that depends on the underlying assets with which they are linked. These...

Computational Complexity and Information Asymmetry in Financial Products

Sanjeev Arora, Boaz Barak, Markus Brunnermeier, Rong Ge

Securitization of cash flows using financial derivatives transformed the financial industry over the last three decades. Derivatives...

Technical Perspective: VL2

Jennifer Rexford

The Internet is increasingly a platform for online services running on rack after rack of servers. With the advent of large data...

VL2: A Scalable and Flexible Data Center Network

Albert Greenberg, James R. Hamilton, Navendu Jain, Srikanth Kandula, Changhoon Kim, Parantap Lahiri, David A. Maltz, Parveen Patel, Sudipta Sengupta

VL2 is a practical network architecture that scales to support huge data centers with uniform high capacity between servers,...

Technical Perspective: Liability Issues in Software Engineering

Daniel M. Berry

The paper by LeMétayer et al. addresses one technical issue in a large and serious problem in the production of mass-market software...

Liability Issues in Software Engineering: The Use of Formal Methods to Reduce Legal Uncertainties

Daniel Le Métayer, Manuel Maarek, Eduardo Mazza, Marie-Laure Potet, Stéphane Frénot, Valérie Viet Triem Tong, Nicolas Craipeau, Ronan Hardouin

This paper reports on the results of a multidisciplinary project involving lawyers and computer scientists with the aim to put...

Technical Perspective: DRAM Errors in the Wild

Norman P. Jouppi

In order to advance the field, knowledge of the types of memory errors at the system level, their frequencies, and conditions...

DRAM Errors in the Wild: A Large-Scale Field Study

Bianca Schroeder, Eduardo Pinheiro, Wolf-Dietrich Weber

While a large body of work exists on DRAM in lab conditions, little has been reported on real DRAM failures in large production...

Technical Perspective: Sora Promises Lasting Impact

Dina Katabi

The objective of Sora is to build a software defined radio that combines the performance and fidelity of hardware platforms with...

Sora: High-Performance Software Radio Using General-Purpose Multi-Core Processors

Kun Tan, He Liu, Jiansong Zhang, Yongguang Zhang, Ji Fang, Geoffrey M. Voelker

Sora, a fully programmable software radio platform on commodity PC architectures, combines the performance and fidelity of hardware...

Technical Perspective: Multipath, A New Control Architecture for the Internet

Damon Wischik

Multipath transmission for the Internet—that is, allowing users to send some of their packets along one path and others along...

Path Selection and Multipath Congestion Control

Peter Key, Laurent Massoulié, Don Towsley

This paper studies data transfers under two classes of multipath control, coordinated control where the rates over the paths...

Technical Perspective: Iterative Signal Recovery From Incomplete Samples

Michael Elad, Raja Giryes

You are given a large set of data values, and you are requested to compress, clean, recover, recognize, and/or predict it. Sounds...

CoSaMP: Iterative Signal Recovery From Incomplete and Inaccurate Samples

Deanna Needell, Joel A. Tropp

Compressive sampling (CoSa) is a new paradigm for developing data sampling technologies. The main computational challenge in...

Technical Perspective: QIP = PSPACE Breakthrough

Scott Aaronson

It is now clear that for a wide range of problems, quantum computers offer little or no advantage over their classical counterparts...

QIP = PSPACE

Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, John Watrous

The collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable...

Technical Perspective: Data Races are Evil with No Exceptions

Sarita Adve

Exploiting parallelism has become the primary means to higher performance. Shared memory is a pervasively used programming model...

Goldilocks: A Race-Aware Java Runtime

Tayfun Elmas, Shaz Qadeer, Serdar Tasiran

GOLDILOCKS is a Java runtime that monitors program executions and throws a DataRaceException when a data race is about to occur...

FastTrack: Efficient and Precise Dynamic Race Detection

Cormac Flanagan, Stephen N. Freund

Multithreaded programs are notoriously prone to race conditions. Prior work developed precise dynamic race detectors that never...

Technical Perspective: A VM 'Engine' That Makes a Difference

Carl Waldspurger

The past decade has witnessed a renaissance in server virtualization. Diwaker Gupta et al. present a novel approach for significantly...

Difference Engine: Harnessing Memory Redundancy in Virtual Machines

Diwaker Gupta, Sangmin Lee, Michael Vrable, Stefan Savage, Alex C. Snoeren, George Varghese, Geoffrey M. Voelker, Amin Vahdat

Virtual machine monitors are a popular platform for Internet hosting centers and cloud-based compute services. But main memory...

Technical Perspective: Belief Propagation

Yair Weiss, Judea Pearl

Nearly every modern tracking system is based on the seminal work of Rudolf Kalman who developed the optimal fusion algorithm...

Nonparametric Belief Propagation

Erik B. Sudderth, Alexander T. Ihler, Michael Isard, William T. Freeman, Alan S. Willsky

Probabilistic graphical models and algorithms for approximate inference have proven to be powerful tools in a wide range of applications...

Technical Perspective: Programming With Differential Privacy

Johannes Gehrke

Government agencies worldwide release statistical information about population, education, and health, crime, and economic activities...

Privacy Integrated Queries: An Extensible Platform for Privacy-Preserving Data Analysis

Frank McSherry

Privacy Integrated Queries (PINQ) is an extensible data analysis platform designed to provide unconditional privacy guarantees...

Technical Perspective: Constraint Satisfaction Problems and Computational Complexity

Mark Jerrum

It takes little imagination to come up with a wealth of problems in scheduling and planning that can be expressed as Constraint...

Constraint Satisfaction Problems and Global Cardinality Constraints

Andrei A. Bulatov, Dániel Marx

In a constraint satisfaction problem (CSP) the goal is to find an assignment of a given set of variables subject to specified...

Technical Persepctive: Attacks Target Web Server Logic and Prey on XCS Weaknesses

Helen Wang

A system is secure only if the entire system is secure. While this may sound obvious, achieving total security throughout a system...

The Emergence of Cross Channel Scripting

Hristo Bojinov, Elie Bursztein, Dan Boneh

Lightweight, embedded Web servers are soon about to outnumber regular Internet Web servers. We reveal a series of attacks that...

Technical Persepctive: Large-Scale Sound and Precise Program Analysis

Fritz Henglein

You are given a program. Will it crash? Is it subject to a spoofing, buffer overflow, or injection attack? Is this part of it...

Reasoning About the Unknown in Static Analysis

Isil Dillig, Thomas Dillig, Alex Aiken

Static program analysis techniques cannot know certain values, such as the value of user input or network state, at analysis...

Technical Perspective: A Solid Foundation for x86 Shared Memory

Hans-J. Boehm

Multithreaded programs that communicate through shared memory are pervasive. Today they are the most obvious route to using multiple...

x86-TSO: A Rigorous and Usable Programmer's Model for x86 Multiprocessors

Peter Sewell, Susmit Sarkar, Scott Owens, Francesco Zappa Nardelli, Magnus O. Myreen

Exploiting the multiprocessors that have recently become ubiquitous requires high-performance and reliable concurrent systems...

Technical Perspective: Technology Scaling Redirects Main Memories

Mary Jane Irwin

As predicted by Intel's Gordon Moore in 1965, the number of transistors that can be integrated on one die continues to double...

Phase Change Memory Architecture and the Quest for Scalability

Benjamin C. Lee, Engin Ipek, Onur Mutlu, Doug Burger

Memory scaling is in jeopardy as charge storage and sensing mechanisms become less reliable for prevalent memory technologies...

Technical Perspective: Building Confidence in Multicore Software

Vivek Sarkar

Surprises may be fun in real life, but not so in software. One approach to avoiding surprises in software is to establish its...

Asserting and Checking Determinism for Multithreaded Programs

Jacob Burnim, Koushik Sen

The trend towards processors with more and more parallel cores is increasing the need for software that can take advantage of...

seL4: Formal Verification of an Operating-System Kernel

Gerwin Klein, June Andronick, Kevin Elphinstone, Gernot Heiser, David Cock, Philip Derrin, Dhammika Elkaduwe, Kai Engelhardt, Rafal Kolanski, Michael Norrish, Thomas Sewell, Harvey Tuch, Simon Winwood

We report on the formal, machine-checked verification of the seL4 microkernel from an abstract specification down to its C implementation...

Technical Perspective: Learning To Do Program Verification

K. Rustan M. Leino

When you decide to use a piece of software, how do you know it will do what you need it to do? Will it be safe to run? Will it...

Technical Perspective: Learning to Act in Uncertain Environments

Peter L. Bartlett

The problem of decision making in an uncertain environment arises in many diverse contexts. The key issue in effectively solving...

Censored Exploration and the Dark Pool Problem

Kuzman Ganchev, Yuriy Nevmyvaka, Michael Kearns, Jennifer Wortman Vaughan

The success and proliferation of dark pool stock exchanges have created challenging and interesting problems in algorithmic trading—in...

Technical Perspective: Automated Patching Techniques: The Fix Is In

Mark Harman

Finding bugs is technically demanding and yet economically vital. How much more difficult yet valuable would it be to automatically...

Automatic Program Repair With Evolutionary Computation

Westley Weimer, Stephanie Forrest, Claire Le Goues, ThanhVu Nguyen

There are many methods for detecting and mitigating software errors but few generic methods for automatically repairing errors...

Technical Perspective: New Bar Set for Intelligent Vehicles

Leslie Pack Kaelbling

Sebastian Thrun gives us a glimpse into the design and implementation of two winning DARPA grand challenge entries.

Toward Robotic Cars

Sebastian Thrun

Recent challenges organized by DARPA have induced a significant advance in technology for autopilots for cars; similar to those...

Technical Perspective: A First Glimpse of Cryptography's Holy Grail

Daniele Micciancio

We all know how to protect our private or most valuable data from unauthorized access: encrypt it. Still, the use of encryption...

Computing Arbitrary Functions of Encrypted Data

Craig Gentry

Suppose that you want to delegate the ability to process your data, without giving away access to it. This separation is possible...

Technical Perspective: Seeing the Trees, the Forest, and Much More

Pietro Perona

Bristling with cameras, microphones, and other sensors, today's portable phones are nevertheless essentially deaf and blind....

Using the Forest to See the Trees: Exploiting Context for Visual Object Detection and Localization

A. Torralba, K. P. Murphy, W. T. Freeman

Recognizing objects in images is an active area of research in computer vision. However, most of the algorithms for detecting...

Technical Perspective: Strange Effects in High Dimension

Sanjoy Dasgupta

In studying the genetic basis of a disease, it is now common to select a set of relevant genes G, and to measure how strongly...

Faster Dimension Reduction

Nir Ailon, Bernard Chazelle

Data represented geometrically in high-dimensional vector spaces can be found in many applications. The need to manipulate such...

Technical Perspective: Want to be a Bug Buster?

Shekhar Y. Borkar

Microprocessor performance has increased exponentially. These chips with ever increasing complexity are not always fully functional...

Post-Silicon Bug Localization for Processors Using IFRA

Sung-Boem Park, Subhasish Mitra

IFRA overcomes major challenges associated with a very expensive step in post-silicon validation of processors — pinpointing...

Technical Perspective: Native Client: A Clever Alternative

Dan Wallach

Google's Native Client is an intriguing new system that allows untrusted x86 binaries to run safely on bare metal.

Native Client: A Sandbox for Portable, Untrusted x86 Native Code

Bennet Yee, David Sehr, Gregory Dardyk, J. Bradley Chen, Robert Muth, Tavis Ormandy, Shiki Okasaka, Neha Narula, Nicholas Fullagar

Native Client is a sandbox for untrusted x86 native code. It aims to give browser-based applications the computational performance...

Technical Perspective: Schema Mappings: Rules for Mixing Data

Alon Halevy

When you search for products on Amazon.com, you are seeing results from thousands of vendor databases that were developed before...

Structural Characterizations of Schema-Mapping Languages

Balder ten Cate, Phokion G. Kolaitis

Information integration is a key challenge faced by all major organizations, business and governmental ones alike. Two research...

Technical Perspective: Design Tools for the Rest of Us

James A. Landay

There are many who believe we are on the verge of the biggest change in the way products are made since the Industrial Revolution...

Designing Plush Toys With a Computer

Yuki Igarashi, Takeo Igarashi

We introduce Plushie, an interactive system that allows nonprofessional users to design their own original plush toys. We successfully...

Technical Perspective: A Graphical Sense of Touch

Pat Hanrahan

One of the major innovations in computing was the invention of the graphical user interface at MIT, SRI, and Xerox PARC. The...

ThinSight: A Thin Form-Factor Interactive Surface Technology

Shahram Izadi, Steve Hodges, Alex Butler, Darren West, Alban Rrustemi, Mike Molloy, William Buxton

ThinSight is a thin form-factor interactive surface technology based on optical sensors embedded inside a regular LCD. These...

Technical Perspective: Narrowing the Semantic Gap in Distributed Programming

Peter Druschel

In science, significant advances are often made when researchers from different communities join forces.

Declarative Networking

Boon Thau Loo, Tyson Condie, Minos Garofalakis, David E. Gay, Joseph M. Hellerstein, Petros Maniatis, Raghu Ramakrishnan, Timothy Roscoe, Ion Stoica

Declarative Networking is a programming methodology that enables developers to concisely specify network protocols and services...

Technical Perspective: Machine Learning for Complex Predictions

John Shawe-Taylor

Interest in machine learning can be traced back to the early days of computer science. Alan Turing himself conjectured that some...

Predicting Structured Objects with Support Vector Machines

Thorsten Joachims, Thomas Hofmann, Yisong Yue, Chun-Nam Yu

Machine Learning today offers a broad repertoire of methods for classification and regression. But what if we need to predict...

Technical Perspective: Relational Query Optimization—Data Management Meets Statistical Estimation

Surajit Chaudhuri

Relational systems have made it possible to query large collections of data in a declarative style through languages such as...

Distinct-Value Synopses for Multiset Operations

Kevin Beyer, Rainer Gemulla, Peter J. Haas, Berthold Reinwald, Yannis Sismanis

The task of estimating the number of distinct values (DVs) in a large dataset arises in a wide variety of settings in computer...

Technical Perspective: Data Stream Processing—When You Only Get One Look

Johannes Gehrke

The database and systems communities have made great progress in developing database systems that allow us to store and query...

Finding the Frequent Items in Streams of Data

Graham Cormode, Marios Hadjieleftheriou

Many data generation processes can be modeled as data streams. While this data may be archived and indexed within a data warehouse...

Technical Perspective: Abstraction for Parallelism

Katherine Yelick

Looking for some new insight into an old problem? The  familiar problem of writing parallel applications and a fresh approach...

Optimistic Parallelism Requires Abstractions

Milind Kulkarni, Keshav Pingali, Bruce Walter, Ganesh Ramanarayanan, Kavita Bala, L. Paul Chew

Writing software for multicore processors is greatly simplified if we could automatically parallelize sequential programs. Although...

Technical Perspective: They Do Click, Don't They?

Marc Dacier

You never click on advertisements received in spam or in phishing messages, do you? Nobody does. So, if that is true, why are...

Spamalytics: An Empirical Analysis of Spam Marketing Conversion

Chris Kanich, Christian Kreibich, Kirill Levchenko, Brandon Enright, Geoffrey M. Voelker, Vern Paxson, Stefan Savage

We all receive spam advertisements, but few of us have encountered a person who admits to following through on an offer and making...

Technical Perspective: Maintaining Quality in the Face of Distributed Development

James Herbsleb

It was a problem that should not have taken three weeks to solve. The documentation claimed that if a function was called from...

Does Distributed Development Affect Software Quality?: An Empirical Case Study of Windows Vista

Christian Bird, Nachiappan Nagappan, Premkumar Devanbu, Harald Gall, Brendan Murphy

Existing literature on distributed development in software engineering and other fields discusses various challenges, including...

Technical Perspective: Where the Chips May Fall

Sachin S. Sapatnekar

The traditional approach to circuit design has been to build chips that work correctly at extreme-case process corners, thereby...

Statistical Analysis of Circuit Timing Using Majorization

Michael Orshansky, Wei-Shen Wang

Future miniaturization of silicon transistors following Moore's Law may be in jeopardy as it becomes harder to precisely define...

Technical Perspective: The Ultimate Pilot Program

Stuart Russell, Lawrence Saul

In one scene from The Matrix, two leaders of the human resistance are trapped on the roof of a skyscraper. The only means of...

Apprenticeship Learning for Helicopter Control

Adam Coates, Pieter Abbeel, Andrew Y. Ng

Autonomous helicopter flight is widely regarded to be a highly challenging control problem. As helicopters are highly unstable...

Technical Perspective: A Compiler's Story

Greg Morrisett

In the early 1970s, pioneers like Floyd, Dijkstra, and Hoare argued that programs should be formally specified and proven correct...

Formal Verification of a Realistic Compiler

Xavier Leroy

This paper reports on the development and formal verification of CompCert, a compiler from Clight (a large subset of the C programming...

Technical Perspective: Reframing Security for the Web

Andrew Myers

The web has brought exciting new functionality while simultaneously requiring new mechanisms to make it secure. We've repeatedly...

Securing Frame Communication in Browsers

Adam Barth, Collin Jackson, John C. Mitchell

Many Web sites embed third-party content in frames, relying on the browser's security policy to protect against malicious content...

Two Hardware-Based Approaches for Deterministic Multiprocessor Replay

Derek R. Hower, Pablo Montesinos, Luis Ceze, Mark D. Hill, Josep Torrellas

Modern computer systems are inherently nondeterministic due to a variety of events that occur during an execution. The lack of...

Technical Perspective: A Chilly Sense of Security

Ross Anderson

Many systems rely on keeping a master key secret. But technological progress can undermine old assumptions.

Lest We Remember: Cold-Boot Attacks on Encryption Keys

J. Alex Halderman, Seth D. Schoen, Nadia Heninger, William Clarkson, William Paul, Joseph A. Calandrino, Ariel J. Feldman, Jacob Appelbaum, Edward W. Felten

DRAM retains its contents for several seconds after power is lost. Although DRAM becomes less reliable when it is not refreshed...

Technical Perspective: Highly Concurrent Data Structures

Maurice Herlihy

The advent of multicore architectures has produced a Renaissance in the study of highly concurrent data structures.

Scalable Synchronous Queues

William N. Scherer, Doug Lea, Michael L. Scott

In a thread-safe concurrent queue, consumers typically wait for producers to make data available. In a synchronous queue, producers...

Technical Perspective: Disk Array Models for Automating Storage Management

Arif Merchant

Large disk arrays are everywhere. When we shop at an Internet retailer, the product and account data come from a disk array in...

Relative Fitness Modeling

Michael P. Mesnier, Matthew Wachs, Raja R. Sambasivan, Alice X. Zheng, Gregory R. Ganger

Relative fitness is a new approach to modeling the performance of storage devices. In contrast to a conventional model, which...

Technical Perspective: Integrating Flash Devices

Goetz Graefe

Flash memory nowadays seems to be in every discussion about system architecture. Sure enough, flash memory boasts multiple qualities...

Integrating NAND Flash Devices onto Servers

David Roberts, Taeho Kgil, Trevor Mudge

In this paper, we examine the use of Flash storage in the server domain. Wear-out has the potential to limit the use of Flash...

Technical Perspective: The Beauty of Error-Correcting Codes

Daniel A. Spielman

Error-correcting codes are the means by which we compensate for interference in communication, and are essential for the accurate...

Error Correction Up to the Information-Theoretic Limit

Venkatesan Guruswami, Atri Rudra

Ever since the birth of coding theory almost 60 years ago, researchers have been pursuing the elusive goal of constructing the...

Technical Perspective: Where Biology Meets Computing

Bud Mishra

Alan Turing died in 1954 in his laboratory after eating a cyanide-laced apple. During his last years, Turing had become interested...

Learning and Detecting Emergent Behavior in Networks of Cardiac Myocytes

Radu Grosu, Scott A. Smolka, Flavio Corradini, Anita Wasilewska, Emilia Entcheva, Ezio Bartocci

We address the problem of specifying and detecting emergent behavior in networks of cardiac myocytes, spiral electric waves in...

Technical Perspective: Tools for Information to Flow Securely and Swift-ly

Dan Wallach

Back in the old days of the Web (before 1995), Web browsers were fairly simple devices. The server's Web interface was simple...

Building Secure Web Applications With Automatic Partitioning

Stephen Chong, Jed Liu, Andrew C. Myers, Xin Qi, K. Vikram, Lantian Zheng, Xin Zheng

Swift is a new, principled approach to building Web applications that are secure by construction. Swift automatically partitions...

Technical Perspective: The Complexity of Computing Nash Equilibrium

Ehud Kalai

Computer science and game theory go back to the same individual, John von Neumann, and both subjects deal with the mathematization...

The Complexity of Computing a Nash Equilibrium

Constantinos Daskalakis, Paul W. Goldberg, Christos H. Papadimitriou

Traditionally, computational problems fall into two classes: those that have a polynomial-time algorithm and those that are NP...

Technical Perspective: Customizing Media to Displays

Harry Shum

A mind-boggling array of displays differ greatly in resolutions and aspect ratios. But  images and videos are captured at fixed...

Seam Carving for Media Retargeting

Ariel Shamir, Shai Avidan

Traditional image resizing techniques are oblivious to the content of the image when changing its width or height. In contrast...

Voyagers and Voyeurs: Supporting Asynchronous Collaborative Visualization

Jeffrey Heer, Fernanda B. Viégas, Martin Wattenberg

This article describes mechanisms for asynchronous collaboration in the context of information visualization, recasting visualizations...

Technical Perspective: One Size Fits All: An Idea Whose Time has Come and Gone

Michael Stonebraker

Beginning in the early to mid-1980s the relational model of data has dominated the DBMS landscape. Moreover, descendents of the...

Breaking the Memory Wall in MonetDB

Peter A. Boncz, Martin L. Kersten, Stefan Manegold

In this paper, we report how research around the MonetDB database system has led to a redesign of database architecture in order...

Technical Perspective: Patching Program Errors

Martin C. Rinard

C programmers are are all too familiar with out-of-bounds memory errors. The paper here presents an intriguing technique for...

Exterminator: Automatically Correcting Memory Errors with High Probability

Gene Novark, Emery D. Berger, Benjamin G. Zorn

Programs written in C and C++ are susceptible to memory errors, including buffer overflows and dangling pointers. We present...

Technical Perspective: The Polaris Tableau System

Jim Gray

Jim Gray nominated the Polaris paper for the Research Highlights section and wrote the first draft of this Technical Perspective...

Polaris: A System for Query, Analysis, and Visualization of Multidimensional Databases

Chris Stolte, Diane Tang, Pat Hanrahan

In this paper, we address these demands by presenting the Polaris formalism, a visual query language for precisely describing...

Technical Perspective: Safeguarding Online Information Against Failures and Attacks

Barbara Liskov

Users need storage that is highly reliable (it is not lost) and highly available (accessible when needed). Guaranteeing these...

Zyzzyva: Speculative Byzantine Fault Tolerance: speculative Byzantine fault tolerance

Ramakrishna Kotla, Allen Clement, Edmund Wong, Lorenzo Alvisi, Mike Dahlin

A longstanding vision in distributed systems is to build reliable systems from unreliable components. An enticing formulation...

Technical Perspective: Computational Photography on Large Collections of Images

Marc Levoy

This paper wil strike a familiar chord with anyone who has ever taken a picture. The problem is easy to understand— replacing...

Scene Completion Using Millions of Photographs

James Hays, Alexei A. Efros

What can you do with a million images? In this paper, we present a new image completion algorithm powered by a huge database...

Technical Perspective: New Developments in Graph Partitioning

Éva Tardos

Arora, Rao, and Vazirani discuss the most important developments in approximation algorithms over the last two decades.

Geometry, Flows, and Graph-Partitioning Algorithms

Sanjeev Arora, Satish Rao, Umesh Vazirani

"Graph partitioning" refers to a family of computational problems in which the vertices of a graph have to be partitioned into...

Technical Perspective: Transactional Memory in the Operating System

Mark Moir

The long tradition of building ever-faster processors is ending, with the computer industry instead putting more processing "cores"...

TxLinux and MetaTM: Transactional Memory and the Operating System

Christopher J. Rossbach, Hany E. Ramadan, Owen S. Hofmann, Donald E. Porter, Aditya Bhandari, Emmett Witchel

TxLinux is the first operating system to use hardware transactional memory (HTM) as a synchronization primitive, and the first...

Technical Perspective: Distributing Your Data and Having It, Too

Hagit Attiya

Distributed Selection: A Missing Piece of Data Aggregation

Fabian Kuhn, Thomas Locher, Roger Wattenhofer

In this article, we study the problem of distributed selection from a theoretical point of view. Given a general connected graph...

Technical Perspective: A Methodology for Evaluating Computer System Performance

William Pugh

Computer science has long had a solid foundation for evaluating the performance of algorithms. The asymptotic complexity of the...

Wake Up and Smell the Coffee: Evaluation Methodology for the 21st Century

Stephen M. Blackburn, Kathryn S. McKinley, Robin Garner, Chris Hoffmann, Asjad M. Khan, Rotem Bentzur, Amer Diwan, Daniel Feinberg, Daniel Frampton, Samuel Z. Guyer, Martin Hirzel, Antony Hosking, Maria Jump, Han Lee, J. Eliot B. Moss, Aashish Phansalkar,

Evaluation methodology underpins all innovation in experimental computer science. It requires relevant workloads, appropriate...

Technical Perspective: Transactions are Tomorrow's Loads and Stores

Nir Shavit

In computer science, when we say "time is money," we typically refer to two types of time that determine the costs and benefits...

Composable Memory Transactions

Tim Harris, Simon Marlow, Simon Peyton Jones, Maurice Herlihy

In this paper we present a concurrency model based on transactional memory. All the usual benefits of transactional memory are...

Technical Perspective: Computer Science Takes on Molecular Dynamics

Bob Colwell

The following paper by researcher David Shaw and colleagues describes their Anton molecular dynamics engine. Shaw's Anton engine...

Anton, A Special-Purpose Machine for Molecular Dynamics Simulation

David E. Shaw, Martin M. Deneroff, Ron O. Dror, Jeffrey S. Kuskin, Richard H. Larson, John K. Salmon, Cliff Young, Brannon Batson, Kevin J. Bowers, Jack C. Chao, Michael P. Eastwood, Joseph Gagliardo, J. P. Grossman, C. Richard Ho, Douglas J. Ierardi, Ist

The ability to perform long, accurate molecular dynamics (MD) simulations involving proteins and other biological macro-molecules...

Technical Perspective: The Physical Side of Computing

Feng Zhao

Wireless sensor networks represent a new computing platform that blends computation, sensing, and communication with a physical...

The Emergence of a Networking Primitive in Wireless Sensor Networks

Philip Levis, Eric Brewer, David Culler, David Gay, Samuel Madden, Neil Patel, Joe Polastre, Scott Shenker, Robert Szewczyk, Alec Woo

The wireless sensor network community approached networking abstractions as an open question, allowing answers to emerge with...