Month: August 2015

Joseph F. Traub, a pioneering computer scientist and founder of the Computer Science department at Columbia University, died Monday, August 24, 2015 in Santa Fe, NM. He was 83. Most recently the Edwin Howard Armstrong Professor of Computer Science, Traub was an early pioneer in computer science years before such a discipline existed, and he would do a lot to shape the field.

Traub was most known for his work on optimal algorithms and computational complexity applied to continuous scientific problems. In collaboration with Henryk Woźniakowski, he created the field of information-based complexity, where the goal is to understand the cost of solving problems when information is partial, contaminated, or priced. Applications for information-based complexity are diverse and include differential and integral equations, continuous optimization, path integrals, high-dimensional integration and approximation, and low-discrepancy sequences.

Understanding the role of information about a problem was a unifying theme of Traub’s contributions to a number of diverse areas of computing. Often collaborating with others, he created significant new algorithms, including the Jenkins-Traub algorithm for polynomial zeros, the Kung-Traub algorithm for comparing the expansion of an algebraic function, and the Shaw-Traub algorithm to increase computational speed. He authored or edited ten monographs and some 120 papers in computer science, mathematics, physics, computational finance, and quantum computing.

Apart from his scientific research, he had a major role in building and leading organizations that promoted computer science. In 1971, at the age of 38, he was appointed chair of the computer science department at Carnegie Mellon University (CMU), overseeing its expansion from fewer than 10 professors to 50, and making it one of the strongest computer science departments in the country. Based on his achievements at CMU, Columbia University in 1979 extended an offer to Traub to found the University’s Computer Science department. He accepted the offer and chose to locate Computer Science within the Engineering School, which at the time offered a single computer, only three tenured faculty members teaching computer science, and a huge demand for computer classes.

After securing a $600,000 gift from IBM (which later provided another $4 million), he was able to add faculty and attract top students. Within a year the department was awarding bachelor’s and master’s degrees as well as PhDs. He would chair the department until 1989.

In 1982 he oversaw the construction of the Computer Science Building, working closely with architects to come up with a final design that would later win awards.

Traub liked building things from scratch. In 1985 while still chair of the Computer Science department, he became the founding editor-in-chief of the Journal of Complexity (a position he held at the time of his death). In 1986, he founded the Computer Science and Technology Board (CSTB) of the National Research Council, serving as its chair from 1986 until 1992 and again in 2005 and 2009.

His awards and honors are many and include election to the National Academy of Engineering in 1985, the 1991 Emanuel R. Piore Gold Medal from IEEE, and the 1992 Distinguished Service Award from the Computer Research Association (CRA). He is a Fellow of the Association for Computing Machinery (ACM), the American Association for the Advancement of Science (AAAS), the Society for Industrial and Applied Mathematics (SIAM), and the New York Academy of Sciences (NYAS). He was selected by the Accademia Nazionale dei Lincei in Rome to present the 1993 Lezione Lincee, a cycle of six lectures. Traub received the 1999 Mayor’s Award for Excellence in Science and Technology, an award presented by Mayor Rudy Giuliani.

In 2012, his 80th birthday was commemorated by a symposium at Columbia’s Davis Auditorium to celebrate his research and contributions to computer science.

Traub’s “contributions to Columbia’s Computer Science Department have been instrumental in establishing the strong foundation of excellence of our Computer Science department today, enabling our ongoing frontier leadership in this field,” said Dean Mary C. Boyce. “Joe will be sorely missed by all of us at Columbia and by the computer science community across the globe.”

Traub always described himself as lucky: Lucky in his early life that his parents were able to flee Nazi Germany in 1939 and settle in New York City; that he had a knack for math and problem-solving just when those skills were needed; that a fellow student’s prescient suggestion led him to visit IBM’s Watson Laboratories where he first encountered computers. And lucky to be among the first to enter a new, unexplored field when he had the ambition to make new discoveries and a hunger to do something significant. In an interview recalling his life, he once said “I’m almost moved to tears but who could have expected such a wonderful life and such a wonderful career.”

That he returned to New York City to found Columbia’s computer science department is entirely appropriate. He attended both Bronx High School of Science and City College of New York (earning degrees in math and physics) before entering Columbia University in 1954 intent on a PhD in theoretical physics. That plan changed when he discovered computers, not at Columbia—which had no computers—but at the IBM Watson lab then located in Casa Hispanica, just off campus at 612 W. 116th Street. He was hired there as a fellow, gaining the perk of unlimited computer time.

In 1959 he earned his PhD under the Committee of Applied Mathematics at Columbia. After his first choice to work on a chess problem was rejected, he proposed instead a quantum problem that involved six months of programing to calculate the ground energy state of a helium atom, correct to four decimal points.

After graduating Columbia, Traub went to work at Bell Labs then in its “golden 60s” when researchers were given wide latitude to choose projects and conduct pure research. It was there that a colleague one day walked into his office with a problem. Could Traub find the zero of a function that involved an integral? Mulling over the problem led to two observations: one, it was expensive to compute the function; and two, there were lots of ways of solving it. His thinking about how to select the best, most optimal algorithm culminated in his 1964 monograph Iterative Methods for the Solution of Equations. It was the start of his career with many publications to come.

His luck extended to his personal life. He was married to Pamela McCorduck, a noted author who also taught science writing at Columbia. He enjoyed skiing, tennis, hiking, travel, and good food.

He regularly spent his summers in Santa Fe, where he was an External Professor at the Santa Fe Institute and played a variety of roles over the years, often organizing workshops to bring together those working in science and math. It was in Santa Fe where he died Monday morning, unexpectedly and quickly, after having made plans to travel to Germany, Poland, and CMU. He is survived by his wife Pamela and two daughters, Claudia Traub-Cooper and Hillary Spector.

Joseph Traub was an important and valued member of the Computer Science department he founded. He will be missed by faculty, staff, and students.

– Linda Crane

Henning Schulzrinne, the Julian Clarence Levi Professor of Mathematical Methods and Computer Science at The Fu Foundation School of Engineering at Columbia University, has been named the recipient of the 2016 IEEE Internet Award for exceptional contributions to the advancement of Internet technology.

Schulzrinne was recognized “for formative contributions to the design and standardization of Internet multimedia protocols and applications.” Schulzrinne is particularly known for his contributions in developing the Session Initiation Protocol (SIP) and Real-Time Transport Protocol (RTP), the key protocols that enable Voice-over-IP (VoIP) and other multimedia applications. Each is now an Internet standard and together they have had an immense impact on telecommunications, both by greatly reducing consumer costs and by providing a flexible alternative to the traditional and expensive public-switched telephone network.

“This award also recognizes the work by my students and visitors in the Columbia IRT lab as well as all the other colleagues who contributed to making Internet-based multimedia possible,” says Schulzrinne, in referring to the Internet Real-Time (IRT) Lab, which he directs and which conducts research in the areas of Internet and multimedia services.

The Internet award follows on the heel of two other honors recently accorded Schulzrinne. In January, he was named an ACM Fellow, and in December 2014 he received an Outstanding Service Award by the Internet Technical Committee (ITC), of which he was the founding chair. In 2013, Schulzrinne was inducted into the Internet Hall of Fame. Other notable awards include the New York City Mayor’s Award for Excellence in Science and Technology and the VON Pioneer Award.

Schulzrinne whose research interests include applied network engineering, wireless networks, security, quality of service, and performance evaluation, continues to work on VoIP and other multimedia applications and is currently investigating an overall architecture for the Internet of Things and making it easier to diagnose network problems. He is also active in designing technology solutions to limit phone spam (“robocalls”) and recently testified on this topic before the Senate Special Committee on Aging.

In addition to his research, Schulzrinne is active in public policy and in serving the broader technology community. From 2012 until 2014, he was the Chief Technology Officer for the Federal Communications Committee where he guided the FCC’s work on technology and engineering issues and played a major role in the FCC’s decision to require mobile carriers to support customers’ abilities to contact 911 using text messages. He continues to serve as a technical advisor to the FCC.

Schulzrinne is a past member of the Board of Governors of the IEEE Communications Society and a current vice chair of ACM SIGCOMM. He has served on the editorial board of several key publications, chaired important conferences, and published more than 250 journal and conference papers and more than 86 Internet Requests for Comment.

Posted 6/30/2015

Columbia University researchers are presenting six papers at this year’s SIGGRAPH. In addition, Changxi Zheng is session chair for Wave-Particle Fluidity (Monday, August 10, 3:45-5:35), and Keenan Crane (now Assistant Professor at Carnegie-Mellon University) is session chair for Simsquishal Geometry (Tuesday, August 11, 9-10:30 am).

High-level descriptions of each paper are given below with links provided to the papers and companion videos.

Category: Computational Illumination, Monday, 10 August, 9-10:30 am
Phasor Imaging: A Generalization of Correlation-Based Time-of-Flight Imaging

Mohit Gupta, Columbia University
Shree Nayar, Columbia University
Matthias B. Hullin, Rheinische Friedrich-Wilhelms-Universität Bonn
Jaime Martin, Rheinische Friedrich-Wilhelms-Universität Bonn

An interview with Mohit Gupta.

Time-of-flight cameras measure 3D shape of objects by measuring the time it takes light to travel between the camera and the object. In recent years, they have fast become the preferred 3D imaging method, specially in consumer settings. Microsoft Kinect, one of the fastest selling consumer devices in history, is based on time-of-flight. Going forward, these cameras can potentially have a broad range of applications, including autonomous cars, industrial and surgical robots, human-computer interfaces, and augmented reality.

Conventional ToF systems assume that light travels only directly between the scene and the camera. While this idealized model is valid in laboratory settings, in almost any real-world setting, light bounces and scatters multiple times within the scene before reaching the camera. This phenomena, called multi-path interference, poses a fundamental challenge to conventional ToF imaging systems. Imagine a robot sorting machine parts or performing surgery inside human body, an autonomous car driving in strong fog or a dust storm, or a robot navigating inside a cave or a room. In all these scenarios, light bounces and scatters multiple times, which results in large errors in the 3D shape. Because these errors are highly structured and not random, they cannot be removed just by using computational algorithms.

Phasor imaging is a new ToF imaging technique that avoids the multipath interference problem to a large extent by re-designing the image capture process itself. We show that by capturing images at multiple high temporal frequencies that are slightly different, the captured images are error free to start with. From these images, it becomes possible to recover highly accurate 3D shape even in challenging scenarios with strong multi-path interference (including fog and smoke).

Multipath interference (MPI) is an important problem which can severely limit the applicability of ToF cameras. By solving this problem, we can significantly increase the range of applications in which ToF cameras can be used. From a theoretical stand-point as well, MPI is one of the most elegant problems which has been widely researched in computer vision over past few decades. Existing solutions, however, are still restricted to a limited class of objects and scenes. The problem is challenging because in addition to the errors being large (up to 50% in some settings), the structure of errors depends on 3D shape itself, making it a ‘chicken-and-egg problem.’ We could remove the errors if we knew the shape, but to measure the shape, we must remove the errors first.

Phasor imaging approach, for the first time, could solve the MPI problem for a very general class of objects and scenes. The solution is based on a first-principles analysis of the physics of how light travels in and interacts with the physical world. The approach is highly efficient—it requires capturing only one extra image (four vs. three for conventional ToF systems) and lowers MPI errors by 1-2 orders of magnitude.

SIGGRAPH has recently emerged as one of the most inter-disciplinary venues among all of computer science, which promises to give our paper wide visibility among researchers and practitioners in a broad range of fields.

Category: Geometry Field Trip, Monday, 10 August, 9-10:30 am
Stripe Patterns on Surfaces
Felix Knöppel, Technische Universität Berlin
Keenan Crane, Columbia University
Ulrich Pinkall, Technische Universität Berlin
Peter Schröder, California Institute of Technology

An interview with Keenan Crane.

Although the current paper focuses on stripes, the motivation actually comes from a fundamental problem in geometry that we are all still thinking about: how do you map a curved surface to the flat plane with as little distortion as possible? This problem was originally raised by cartographers trying to make flat maps of the round Earth. What you discover very quickly is that there is no perfect way to do it: either areas get stretched out (like Greenland becoming bigger than Australia in a Mercator projection) or angles get distorted (for instance, North and East may no longer be at right angles). The route we are pursuing with “stripe patterns” suggests a third possibility: wherever map making gets hard, insert singularities that allow you to do a good job of preserving lengths and angles everywhere else. As you add more and more singularities, the map gets closer and closer to being perfect (or “isometric”) away from these isolated points. The current paper is one step in that direction, where we just focus on one of two coordinates, i.e., just longitude rather than longitude and latitude. As you can see from the pictures, our longitude lines are already looking pretty good!

Can you describe at a high level the main innovation of your paper? How much of a departure is your method from previous methods on generating stripes?

---

A method for interactively deforming shapes

In computer graphics, a common task is to change the shape or pose of an object or character. The normal process is for the user to pick a point, or handle, from which to control movement. As the user moves the handle, changes propagate outward, affecting the nearby area. The question is always, how far does the influence of the handle extend and how quickly does the influence fall off? Previously the user decided, typically by using a paintbrush-type tool to define the area and the rate of fall-off.

Over the past four years, we have been working to automate the interpolation process by developing an optimization that calculates the correspondence between distance and how much weight to assign the influence of the handle, and does so in a way that ensures smooth, natural motions.

This makes the deformation task easier for the user who no longer has to figure out the interpolations. But the calculations take time; every time the user inserts a handle, it takes a few minutes for the calculations to complete, interfering with the desired interactivity. Our new paper fixes this problem by speeding up the calculations to interactive time.

There are several; I will mention two.

We examined the algebraic properties of our optimization for computing correspondences and discovered that if we were more careful about the cost function, we could speed the process. Previously the weighting function would consider all possible functions between 1 and 0, and choose the smoothest function. We found that by carefully modeling the idea of smoothness, it suddenly became possible to re-use a lot of the computation for finding the weights of one handle and use it for all other handles. That was a big time savings.

Another came from removing the non-negative constraint from the weighting function, a constraint that seems very intuitive to have. If this one handle is negative and gets moved right, the other handle should have an opposite response and go left. Plus a non-negative constraint makes it unnecessary to optimize over all functions, only those that are non-negative. But the constraint makes the optimization much harder. It turns out to be easier and faster to optimize over a generic function set than a very specific set.

What we realized, to our surprise, was we could either have very smooth deformations—without bumps at each of the handle—or we could have non-negative weights, but we could not have both. It was a tradeoff we were willing to make; we could put up with a bit of non-intuitiveness for better results. Further, without that constraint, the optimization is much faster.

In the end, we were able to speed things up to the point that a user can plop down a handle, decide it is not right, and immediately choose another handle and continue working. The design process is now easy and fluid.

It might be a while. Studios have well-established procedures, and introducing something new into that can take time. Plus new features have to be adapted for the different packages where the underlying geometries may be hidden by additional layers.

It is the research community that will make immediate use of new projects and features. We have made our software available online, and we expect that the first users will be researchers whose work depends on deformations that perhaps they were not able to do previously. Now instead of having to rely on artists or modelers, researchers themselves can explore new territory.

Category: Fabrication & Function, Wednesday, August 12, 10:45 am to 12:15 pm
Computational Design of Twisty Joints and Puzzles
Timothy Sun, Columbia University
Changxi Zheng, Columbia University

---

Precisely aligning colors and patterns to arbitrary 3D objects

---

Vortex sheets: A faster, more efficient method for simulating bubbles

Posted 8/25/2015