Papers from CS researchers were accepted to the 60th Annual Symposium on Foundations of Computer Science (FOCS 2019). The papers delve into population recovery, sublinear time, auctions, and graphs.
Finding Monotone Patterns in Sublinear Time Omri Ben-Eliezer Tel-Aviv University, Clement L. Canonne Stanford University, Shoham Letzter ETH-ITS, ETH Zurich, Erik Waingarten Columbia University
The paper is about finding increasing subsequences in an array in sublinear time. Imagine an array of n numbers where at least 1% of the numbers can be arranged into increasing subsequences of length k. We want to pick random locations from the array in order to find an increasing subsequence of length k. At a high level, in an array with many increasing subsequences, the task is to find one. The key is to cleverly design the distribution over random locations to minimize the number of locations needed.
Roughly speaking, the arrays considered have a lot of increasing subsequences of length k; think of these as “evidence of existence of increasing subsequences”. However, these subsequences can be hidden throughout the array: they can be spread out, or concentrated in particular sections, or they can even have very large gaps between the starts and the ends of the subsequences.
“The surprising thing is that after a specific (and simple!) re-ordering of the “evidence”, structure emerges within the increasing subsequences of length k,” said Erik Waingarten, a PhD student. “This allows for design efficient sampling procedures which are optimal for non-adaptive algorithms.”
Consider the problem of reconstructing the DNA sequence of an extinct species, given some DNA sequences of its descendant(s) that are alive today. We know that DNA sequences get modified through random mutations, which can be substitutions, insertions and deletions.
A mathematical abstraction of this problem is to recover an unknown source string x of length n, given access to independent samples of x that have been corrupted according to a certain noise model. The goal is to determine the minimum number of samples required in order to recover x with high confidence. In the special case that the corruption occurs via a deletion channel (i.e., each character in x is deleted independently with some probability, say 0.1, and the surviving characters are concatenated and transmitted), each sample is called a trace. The corresponding recovery problem is called trace reconstruction, and it has received significant attention in recent years.
The researchers considered a generalized version of this problem (known as population recovery) where there are multiple unknown source strings, along with an unknown distribution over them specifying the relative frequency of each source string. Each sample is generated by first drawing a source string with the associated probability, and then generating a trace from it via the deletion channel. The goal is to recover the source strings, along with the distribution over them (up to small error), from the mixture of traces.
For the main sample complexity upper bound, they show that for any population size s = o(log n / log log n), a population of s strings from {0,1}^n can be learned under deletion channel noise using exp(n^{1/2 + o(1)}) samples. On the lower bound side, we show that at least n^{\Omega(s)} samples are required to perform population recovery under the deletion channel when the population size is s, for all s <= n^0.49.
“I found it interesting that our work is based on certain mathematical results in which, at first glance, seem to be completely unrelated to the computational problem we consider,” said Sandip Sinha, a PhD student. In particular, they used constructions based on Chebyshev polynomials, a certain sequence of polynomials which are extremal for many properties, and is hence ubiquitous throughout theoretical computer science. Similarly, previous work on trace reconstruction rely on certain extremal results about complex-valued polynomials. Continued Sinha, “I think it is quite intriguing that complex analytic techniques yield useful results about a problem which is fundamentally about discrete structures (binary strings).”
The paper is about the theory of combinatorial auctions. In a combinatorial auction, an auctioneer wants to allocate several items among bidders. Each bidder has a certain amount that they value each item; bidders also have values for combinations of items, and in a combinatorial auction a bidder might not value a combination of items as much as each item individually.
For instance, say that a pencil and a pen will be auctioned. The pencil is valued at 30 cents and the pen at 40 cents, but the pen and pencil together at only 50 cents (it may be that there isn’t any additional value from having both the pencil and the pen). Valuation functions with this property — that the value of a combination of items is less than or equal to the sum of the values of each item — are called subadditive.
In the paper, the researchers answered a longstanding open question about combinatorial auctions with two bidders who have subadditive valuation — roughly speaking, is it possible for an auctioneer to efficiently communicate with both bidders to figure out how to allocate the items between them to make the bidders happy?
The answer turns out to be no. In general, if the auctioneer wants to do better than just giving all of the items to one bidder or the other at random, the auctioneer needs to communicate a very large amount with the bidders.
The result itself was somewhat surprising, the researchers expected it to be possible for the auctioneer to do pretty well without having to communicate with the bidders too much. “Also, information theory was extensively used as part of proving the result,” said Eric Neyman, a PhD student. “This is unexpected, because information theory has not been used much in the study of combinatorial auctions.”
In a graph, an independent set is a set of vertices with the property that none are adjacent. For example, in the graph of Facebook friends, vertices are people and there is an edge between two people who are friends. An independent set would be a set of people, none of whom are friends with each other. A basic problem is to find a large independent set. The paper focuses on one type of large independent set known as a maximal independent set, that is, one that cannot have any more vertices added to it.
Graphs, such as the friends graph, evolve over time. As the graph evolves, the maximal independent set needs to be maintained, without recomputing one from scratch. The paper significantly decreases the time to do so, from time that is polynomial in the input size to one that is polylogarithmic.
A graph can have many maximal independent sets (e.g. in a triangle, each of the vertices is a potential maximal independent set). One might think that this freedom makes the problems easier. The researchers picked one particular kind of maximal independent set, known as a lexicographically first maximal independent set (roughly this means that in case of a tie, the vertex whose name is first in alphabetical order is always chosen) and show that this kind of set can be maintained more efficiently.
“Giving up this freedom actually makes the problems easier,” said Cliff Stein, a computer science professor. “The idea of restricting the set of possible solutions making the problem easier is a good general lesson.”
Columbia’s Womxn in Computer Science (WiCS) share their experiences from the 2019 Grace Hopper Convention in Orlando, Florida. The annual conference is the world’s largest gathering of women in computing.
Hadley Callaway Grace Hopper was a fantastic experience. I completed three interviews with companies while there, and I was able to leave the conference with an offer for a software engineering internship.
I spoke to recruiters and engineers from all sorts of different companies (big and small, offering a variety of products), and attended fun corporate events in the evening, including one at SeaWorld.
It was also very empowering to hear from womxn at the cutting edge of their field speak about their experiences and what they have learned. Attending the conference was a great opportunity for me to continue to develop professional skills such as pitching, networking, following up on connections, etc.
I am so thankful to WiCS and the Columbia CS department for making such an invaluable opportunity possible!
Michelle Mao Thanks to WiCS, I was able to go to Grace Hopper ‘19, and any womxn in STEM would be lucky to do the same. The Grace Hopper Celebration is a lot of things but the most impactful thing about the celebration, for me, was how inspiring those short few days were.
I had heard a lot about the conference from friends who have gone in the past, so I knew to expect a hectic schedule when I arrived in Orlando. In the three and a half days at Grace Hopper, I went to the career fair, got a free ticket to Harry Potter World, interviewed at a few companies, and acquired a lot of swag.
What I did not expect was spontaneously meeting other womxn while waiting in lines, running into friends I had not seen in years, or how truly friendly, open, and uplifting the atmosphere would be. I attended a researcher’s luncheon with my friend, but I was a little nervous about going because the research I was doing was not exactly related to computing. But everyone at the table was so kind and welcoming — as we ate, the conversation shifted to topics other than research, until the luncheon just felt like a chat among a group of friends.
After the first couple of days, I also noticed that in my interviews, most of my interviewers were womxn. I had not realized until then that I have grown accustomed to being interviewed by men. It was wonderful to have this representation feel so normal, and meeting and talking with these incredible womxn was just the cherry on top.
It’s difficult to put into words, but Grace Hopper really does feel like a celebration: the energy is palpable and electrifying, the conversations are genuine, and womxn in STEM are there to support each other in every way possible. Being in this space was a privilege and I felt like I belonged, in every sense of the word, and it is one hundred percent an event any womxn interested in computing should experience.
Haley So In a single word, the Grace Hopper Celebration was empowering. It was inspiring to see so many womxn pursuing and pushing the boundaries of computer science.
There were talks on everything from emerging technologies to how to promote yourself as a womxn in tech. I was also able to explore different paths and find out a little more about what direction I want to go in. I met so many lovely womxn, and I got closer to some WiCS members as we wandered around the enormous career fair and listened to talks from leaders in the field.
Going to the conference
opened my eyes to the endless possibilities, introduced me to new role models,
and made me excited about the future. I cannot wait for all those womxn to
build the future world of tech!
The goal of the competition is to develop DL driving models — predicting steering wheel angle and vehicle speed is given large-scale training data and using advanced deep learning techniques. Two teams, composed of students from the computer science (CS) department and the Data Science Institute (DSI), won the challenge in all major categories ranking first and second place.
“Winning the top three categories in this international challenge is an excellent achievement,” said adjunct associate professor Iddo Drori. “I am very proud to have mentored the teams to the finish line.”
As part of the unique DL course curriculum, students get to compete in common task framework competitions which enable them to test the waters in the real world while advancing science. This semester Drori and teaching assistants Manik Goyal and Benedikt Dietmar performed feasibility tests on the Learning-to-Drive Challenge and found it in line with the course goals.
Students used the Drive 360 dataset to design, develop and train a driving model. Over the course of three weeks, teams worked on and improved their submissions competing with groups from across the world. Students were given cloud resources to develop their models even further. The effort paid off with the CS and DSI students at the top of the competition leaderboard. In order to claim victory, they had to quickly write up and submit their findings.
CS graduate students Michael J Diodato and Yu Li won first place, while DSI graduate students Antonia Lovjer and Minsu Yeom won second place.
After 26 years in the computer science department, professor Steven Nowick is retiring. Friends, colleagues, and those dear to him recently gathered to celebrate his teaching and academic career — one that has pushed the asynchronous community to be more widely noticed and accepted. Nowick walks away with a body of work that is as diverse and nuanced as the next chapter of his life — composing music.
Left to right : Grant Chorley, Steven Nowick, David Conte (chair of composition, San Francisco Conservatory), Fred Blum, Joel Feigin (former music professor, UC Santa Barbara) at the Conservatoire Americaine, Fontainebleau, France (1975).
Many probably do not know that he has a B.A. from Yale University in music and an M.A. in music composition from Columbia University, where his master’s thesis was symphony. The better part of his 20s was spent on a music career, during which time he studied privately with composer David Diamond, and in France with the legendary music teacher Nadia Boulanger.
However, he decided to shift gears and retrain in computer science (CS) when he hit 30 years old. After two years of brushing up on CS concepts, including a class taught by Steven Feiner that first introduced him to digital hardware, he applied and was accepted to the PhD program at Stanford University in 1986.
While at Stanford, his interest in asynchronous systems was cemented when he started to work on research with professor David Dill. In 1993, he found himself back at Columbia as an assistant professor. In his first year, he recognized the need for a Computer Engineering program in the engineering school, and worked with two colleagues from computer science and electrical engineering departments to establish the degree that was later expanded to include a masters program. In his second year at Columbia, he co-founded the IEEE ASYNC symposium, the premier international forum for researchers to present their latest findings in the area of asynchronous digital design, which is still thriving after 25 years.
“Computer engineering is entirely to Steve’s credit that it grew to what it is today,” said Kathy McKeown, the Henry and Gertrude Rothschild Professor of Computer Science, who looked through her emails all the way back to the time when she was the department chair in the late 90s for her tribute to Nowick. “It is also because of his persistence and dedication as head of the strategic planning committee, that our faculty has grown.”
Also at the party, Zvi Galil, former computer science professor and dean of the School of Engineering and Applied Sciences, shared, “In the good old days we couldn’t even hire one faculty, now they can hire five in a year.” At the time in the late 90s there were less than 20 faculty, currently there are 59 faculty. Said another colleague, Shree Nayar, “Thank you for all that you’ve done for the department, we would not look the same if not for you.”
Through the years, Nowick has taught and mentored hundreds of
students. “He is an amazing academic father,” said Montek Singh, a former PhD student who is now a tenured associate professor at
the University of North Carolina at Chapel Hill. Singh shared how when they
were working on MOUSETRAP: High-Speed Transition-Signaling Asynchronous Pipelines,
they brainstormed for days working out every little detail. And then they
brainstormed even more to come up with the name, which is actually an acronym –
Minimum Overhead Ultra-high-Speed Transition-signaling Asynchronous Pipeline.
Continued Singh, “I can only hope to be half as good to my PhD students as he
is.”
Left to right : Michael Theobald (PhD student), George Faldamis (MS student), Cheoljoo Jeong (PhD student), Melinda Agyekum (PhD student), Steven Nowick, Martha Helfer (Nowick’s wife), Cheng-Hong Li (MS student), Montek Singh (PhD student)
The party was also attended by a number of his other former graduate students, post-docs, and outside colleagues, including former PhD student Michael Theobald, a research scientist in formal verification at D.E. Shaw Research, who served as “master of ceremonies.” His asynchronous colleagues Ivan Sutherland (the Turing Award winning inventor of interactive computer graphics and virtual reality) and Marly Roncken flew out from Oregon, and computer science professor Rajit Manohar came down from Yale.
“Steve is a highly ambitious person with a lot of passion, a tremendous persistence and a lot of perseverance,” said Jeannette Wing, the Avanessians Director of the Data Science Institute and computer science professor. In 2016, Nowick established a working group at the Data Science Institute, and in 2018 worked with Wing to turn it into a center – The Center for Computing Systems for Data-Driven Science. He has gathered 45 faculty from across the university to explore the design and application of large-scale computing systems for data-driven scientific discovery. It is multi-disciplinary and brings together diverse researchers at Columbia in three areas: computing systems, data science and machine learning, and large-scale computational application areas in science, engineering and medicine. Qiang Du, a professor from Applied Physics and Applied Mathematics, and associate computer science professor Martha Kim are now co-chairs of the center.
Left to right : Columbia Executive Vice President for Research Michael Purdy, Steven Nowick, and professor Sebastian Will, physics department
As chair of the working group, in 2017, he organized an on-campus inaugural symposium, attracting 150 participants, which included leading speakers from IBM, D.E. Shaw Research and NASA Goddard. In 2019, as his final major act as center chair, he co-organized the NY Scientific Data Summit jointly with nearby Brookhaven National Laboratory, to showcase regional research on data-driven science, and to forge closer bonds between the two institutions.
Of course, asynchronous research and activities to advance the field were happening simultaneously with all these other activities. Nowick has been one of the leaders in the revival of clockless, or asynchronous, digital hardware systems. While most digital systems today are synchronous, built using a central clock, increasingly the challenge of assembling large, complex and heterogeneous systems – with dozens to millions of processors and memory units – is becoming unworkable under centralized control. The vision of asynchronous systems has seen a resurgence in the last twenty years, and Nowick has been at the forefront. Such systems, assembled with “Lego-like” hardware building blocks, which are plugged together and communicate locally, promise to overcome some of the extreme barriers faced in the microelectronics industry, providing low energy, ease of assembly, high performance, and reliable operation.
Recent asynchronous advances include “brain-inspired” (i.e. neuromorphic) chips from IBM (TrueNorth) and Intel (Loihi). Nowick has collaborated closely with AMD Research, migrating his asynchronous on-chip networks into the company’s advanced technology, and experimentally demonstrating significant benefits in power, performance and area, over their synchronous commercial designs. He and his students have also introduced an influential set of computer-aided design (CAD) software tools, optimization algorithms and analysis techniques, for asynchronous circuits and systems. In addition, he has worked closely over the years with IBM Research, Boeing and NASA on asynchronous design projects.
Nowick is an IEEE Fellow (2009), a recipient of an Alfred P. Sloan Research Fellowship (1995), received NSF CAREER (1995) and RIA (1993) awards, and he is also a Senior Member of the ACM. He received Best Paper Awards at the IEEE International Conference on Computer Design (1991, 2012) and the IEEE Async Symposium (2000). He also acted as program chair at various workshops and conferences, as well as served on leading journal editorial boards, such as IEEE Design & Test Magazine, IEEE Transactions on Computer-Aided Design, IEEE Transactions on VLSI Systems, and ACM Journal on Emerging Technologies in Computer Systems, and served as a guest editor for a special issue of the Proceedings of the IEEE. He holds 13 issued US patents, and his research has been supported by over 20 grants and gifts. In recognition of his teaching, he also received the SEAS Alumni Distinguished Faculty Teaching Award in 2011.
But the pull of music has become stronger in recent years.
“In the back of my mind I always knew I would return to it and I
should do it now while I can still do it well, rather than when I’m in my 80s
or 90s,” said Nowick.
He plays the piano and his focus will be classical composition. He has written music for string quartet, orchestra, choir, piano, cello, two flutes, and for voice and piano. He is writing new compositions and looks forward to his music being performed.
“Music will be his act two,” said Montek Singh. “So in a sense
he’s come full circle.”
The J.P. Morgan AI Research Awards 2019 partners with research thinkers across artificial intelligence. The program is structured as a gift that funds a year of study for a graduate student.
Prediction semantics and interpretations that are
grounded in real data Principal Investigator: Daniel Hsu Computer Science Department & Data Science Institute
The importance of transparency in predictive technologies is by now well-understood by many machine learning practitioners and researchers, especially for applications in which predictions may have serious impacts on human lives (e.g., medicine, finance, criminal justice). One common approach to providing transparency is to ensure interpretability in the models and predictions produced by an application, or to accompany predictions with explanations. Interpretations and explanations may help individuals understand predictions that affect them, and also help developers reason about failure cases of their applications.
However, there are numerous possibilities for what constitutes a suitable interpretation or explanation, and the semantics of such provided by existing systems are not always clear.
Suppose, for example, that a bank uses a linear model to predict whether or not a loan applicant will forfeit on a loan. A natural strategy is to seek a sparse linear model, which are often touted as highly interpretable. However, attributing significance to variables with non-zero regression coefficients (e.g., zip-code) and not others (e.g., race, age) is suspect when variables may be correlated. Moreover, an explanation based on pointing to individual variables or other parameters of a model ignores the source of the model itself: the training data (e.g., a biased history of borrowers and forfeiture outcomes) and the model fitting procedure. Invalid or inappropriate explanations may create a “transparency fallacy” that creates more problems than are solved.
The researchers propose a general class of mechanisms that provide explanations based on training or validation examples, rather than any specific component or parameters of a predictive model. In this way, the explanation will satisfy two key features identified in successful human explanations: the explanation will be contrastive, allowing an end-user to compare the present data to the specific examples chosen from the training or validation data, and the explanation will be pertinent to the actual causal chain that results in the prediction in question. These features are missing in previous systems that seek to explain predictions based on machine learning methods.
“We expect this research to lead to new methods for interpretable machine learning,” said Daniel Hsu, the principal investigator of the project. Because the explanations will be based on actual training examples, the methods will be widely applicable, in essentially any domain where examples can be visualized or communicated to a human. He continued, “This stands in contrast to nearly all existing methods for explanatory machine learning, which either require strong assumptions like linearity or sparsity, or do not connect to the predictive model of interest or the actual causal chain leading to a given prediction of interest.”
Efficient Formal Safety Analysis of Neural Networks Principal Investigators: Suman Jana Computer Science Department, Jeannette M. Wing Computer Science Department & Data Science Institute, Junfeng Yang Computer Science Department
Over the last few years, artificial intelligence (AI), in particular Deep Learning (DL) and Deep Neural Networks (DNNs), has made tremendous progress, achieving or surpassing human-level performance for a diverse set of tasks including image classification, speech recognition, and playing games such as Go. These advances have led to widespread adoption and deployment of DL in critical domains including finance, healthcare, autonomous driving, and security. In particular, the financial industry has embraced AI in applications ranging from portfolio management (“Robo-Advisor”), algorithmic trading, fraud detection, loan and insurance underwriting, sentiment and news analysis, customer service, to sales.
“Machine learning models are used in more and more safety and security-critical applications such as autonomous driving and medical diagnosis,” said Suman Jana, one of the principal investigators of the project. “Yet they are known to be fragile and frequently mispredicts on edge cases.“
In many critical domains including finance and autonomous driving, such incorrect behaviors can lead to disastrous consequences such as a gigantic loss in automated financial trading or a fatal collision of a self-driving car. For example, in 2016, a Google self-driving car crashed into a bus because it expected the bus to yield under a set of rare conditions but the bus did not. Also in 2016, a Tesla car in autopilot crashed into a trailer because the autopilot system failed to recognize the trailer as an obstacle due to its ‘white color against a brightly lit sky’ and the ‘high ride height.’
Before AI can become the next technological revolution, it must be robust against such corner-case inputs and does not cause disasters. The researchers believe AI robustness is one of the biggest challenges that needs to be solved in order to fully tame AI for good.
“Our research aims to create novel tools to verify that a machine learning model will not mispredict on certain important input ranges, ensuring safety and security,” said Junfeng Yang, one of the investigators of the research.
The proposed work enables rigorous analysis of autonomous AI systems and machine learning (ML) algorithms, enabling data scientists to (1) verify that their AI models function correctly within certain input regions and violate no critical properties they specify (e.g., bidding price is never higher than a given maximum) or (2) locate all sub-regions where their models misbehave and repair their model accordingly. This capability will also enable data scientists to explain and interpret the outputs from autonomous AI systems and ML algorithms by understanding how different input regions may lead to different output predictions. Said Yang,”If successful, our work will dramatically boost the robustness, explainability, and interpretability of today’s autonomous AI systems and ML algorithms, benefiting virtually every individual, business, and government that relies on AI and ML.”
Dean Boyce's statement on amicus brief filed by President Bollinger
President Bollinger announced that Columbia University along with many other academic institutions (sixteen, including all Ivy League universities) filed an amicus brief in the U.S. District Court for the Eastern District of New York challenging the Executive Order regarding immigrants from seven designated countries and refugees. Among other things, the brief asserts that “safety and security concerns can be addressed in a manner that is consistent with the values America has always stood for, including the free flow of ideas and people across borders and the welcoming of immigrants to our universities.”
This recent action provides a moment for us to collectively reflect on our community within Columbia Engineering and the importance of our commitment to maintaining an open and welcoming community for all students, faculty, researchers and administrative staff. As a School of Engineering and Applied Science, we are fortunate to attract students and faculty from diverse backgrounds, from across the country, and from around the world. It is a great benefit to be able to gather engineers and scientists of so many different perspectives and talents – all with a commitment to learning, a focus on pushing the frontiers of knowledge and discovery, and with a passion for translating our work to impact humanity.
I am proud of our community, and wish to take this opportunity to reinforce our collective commitment to maintaining an open and collegial environment. We are fortunate to have the privilege to learn from one another, and to study, work, and live together in such a dynamic and vibrant place as Columbia.
Sincerely,
Mary C. Boyce
Dean of Engineering
Morris A. and Alma Schapiro Professor
Add to GMail