Technical Perspective: The Ray-Tracing Engine That Could
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
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
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?
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
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
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
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
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
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
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
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
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
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?
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
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
"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
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
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
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
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...
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!
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
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?
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
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
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
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
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
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
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?
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
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
We give a logical characterization of the polynomial-time properties of graphs with excluded minors.
Technical Perspective: Images Everywhere Looking for Models
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
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
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
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
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
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
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
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
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
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
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
Privacy Integrated Queries (PINQ) is an extensible data analysis platform designed to provide unconditional privacy guarantees...
Technical Perspective: Constraint Satisfaction Problems and Computational Complexity
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
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
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
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
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
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
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
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
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
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
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
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
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
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
In science, significant advances are often made when researchers from different communities join forces.
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
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
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
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
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?
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
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
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
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
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
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
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
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
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
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
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
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
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
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 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
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
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
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
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
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
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
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
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
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...