The National Science Foundation (NSF) has awarded a $1.2M, four-year grant to computer science theorists Christos Papadimitriou and Mihalis Yannakakis for their proposal “Research in Algorithms and Complexity: Total Functions, Games, and the Brain.”
The following is an abstract of the work to be done under the grant.
The ubiquitous information environment around us, which has brought to the world unprecedented connectivity and availability of information, as well as newfound opportunities for individual expression, education, work, production and commerce, entertainment, and interpersonal communication, is the result of decades of research in all fields of computer science; furthermore, our best hope for confronting the many problems this new environment has brought to humanity (privacy and fairness, to mention only two) also lies in new computer science research.Research in theoretical computer science in particular over the past half century has been instrumental in bringing the benefits of Moore’s law to bear – through fundamental clever algorithms – and has made leaps in understanding the capabilities and limitations of computers and their software; in fact, it has articulated one of the most important problems in mathematics and all of science today: is P equal to NP? – that is to say, is exponential exhaustive search for a solution always avoidable?Papadimitriou and Yannakakis have over the past four decades contributed much to this edifice of mathematical research in computer science, often in close collaboration; in addition, they have successfully applied the kind of incisive mindset known as “algorithmic thinking” to important problems in other sciences, such as economics and biology.
For this project, they will join efforts again in order to attack a new generation of problems: complexity questions in the fringe of the P vs. NP problem, a new genre of algorithms possessing a novel kind of robustness, research at the interface between computer science and economics related to income inequality and market efficiency, as well as research aiming at a better understanding of evolution, and of brain functions as basic as memory and as advanced as language. Papadimitriou and Yannakakis will train PhD and Masters students – and possibly undergraduates as well – on these research topics, and will disseminate the findings of this research to students and researchers, both in computer science and in other disciplines, as well as to the general public, through journal and conference publications, undergraduate and graduate courses, seminars, colloquia, as well as public talks and general interest articles.
In more detail, Papadimitriou and Yannakakis will work on improving our understanding of the complexity of total functions in the class TFNP and its subclasses, in view of recent research progress in that area; they will investigate the complexity of an as yet unexplored, from this point of view, Tarski-like fixed point theorem widely used in economics; they will revisit the approximability of the traveling salesperson problem; and will explore a new kind of algorithmic notion of robustness based on dense nets of algorithms.In algorithmic game theory, Papadimitriou and Yannakakis will explore a new variant of the price of anarchy inspired by wealth inequality, as well as the complexity of market equilibria in markets with production and economies of scale; they will also research a new game theoretic solution concept based on the topology of dynamical systems; finally, they will pursue the proof of an intriguing new complexity-theoretic conjecture about the inaccessibility of Nash equilibria.They will also continue their work in certain promising directions at the interface of game theory and learning theory.In the life sciences, they will explore from the algorithmic point of view the problem of the true nature of mutations, and they will work on extending recent research with collaborators aiming at the computational understanding of how long-term memory, as well as syntax and language, are achieved in the human brain.
“How wonderful would it be if the growth of scientific and technological innovation would come along with more equality and social inclusion.” – Pope Francis
With the Pope’s full support and encouragement, the Vatican held its first ever hackathon, VHacks, over the March 8-11 weekend. Five Columbia students were among the 120 participating from 60 universities around the world.
Held in Rome steps from Vatican City, VHacks was a hackathon with a distinct European flavor. The hackathon itself took place in the centuries-old Palazzo della Rovere (which houses the Order of the Holy Sepulchre). Cardinals and other high-ranking curates along with secular dignitaries (the Prince of Liechtenstein) circulated among the students for demos in VR and other technologies.
In outward form, VHacks hewed closely to established hackathon outlines—a marathon coding session (in this case 36 hours interspersed with panels); corporate partners like Microsoft, Google, and Salesforce on site to hold workshops and give guidance on use of their products; prizes for the top projects; and plenty of free food, albeit of a higher quality than normally found at hackathons.
Where the VHacks diverged most noticeably was in its singular focus on social good, not market potential. Reflecting papal priorities, all projects fit one of three themes: social inclusion, interfaith dialogue, and resources to migrants and refugees. Each team before arriving in Rome was assigned one of the three themes. Diversity was another VHacks priority, with teams preselected to ensure equal representation by gender, religion, and background. Except in three or four instances, students arrived without having previously met their teammates in person.
For Myra Deng, a junior currently studying in Budapest, the chance to work toward social good was what finally convinced her to bite the bullet and enter her first hackathon. Vivian Shen, a hackathon veteran and the organizer of DevFest, signed up out of curiosity; she wanted to see how the Catholic church would embrace technology.
Being selected for a team rather than selecting your own team was another way VHacks diverged from other hackathons. Both Deng and Shen were on the same team (though they did not know one another previously), and while their team-mates quickly became close, there was an added layer of difficulty and adjustment. “You come in not knowing your team members’ strengths and weaknesses,” says Shen. “You have to both meet people and think up a new idea. It’s an additional element.”
For Nicole Valencia, not having to compete against a crowd of pre-established teams was one of the attractions. As a first-time hackathon competitor, she appreciated how VHacks leveled by the playing field by removing the advantages enjoyed by teams who come into a competition already formed, often knowing one another very well. She appreciated also the chance to interact and work with people from vastly different backgrounds.
Tomer Aharoni, fresh off two hackathons in six weeks (MakeHarvard, which his team won, and DevFest, where his team placed second) was impressed at the efforts made by organizers to ensure participation by top schools and students, and to enlist high-level executives from the corporate world. Among those serving as mentors, judges, and panelists were Google’s president of strategic relationships in Europe, the Middle East, and Africa as well as the former CEO of Ethereum Foundation, the Senior Vice President of Salesforce, the Senior Director of Microsoft, and many others.
Aharoni too chafed a bit at not being able to pick his own team or his own topic. With only three themes and 24 teams, it was harder to design a unique project that stood out from all the others. His team’s job-finding platform—which matched potential employers with migrants and refugees who advertised their skills via pictures rather than language—was one of four job-oriented projects, and though it drew outside interest (specifically by an Airbnb executive who floated the idea of doing a pilot), having a team scattered across several countries would seem to work against building a cohesive team to bring an idea to market.
VHacks organizers do hope a high percentage of participants (as high as 50%) will continue working on what they started (only 15% do in a typical hackathon). To help achieve that goal, mentors outnumbered competitors almost two to one, giving advice freely on both technical and business model aspects. Says Valencia, “I especially found it fascinating that not everyone was explicitly tech. One of our team members—not from computer science—had a brilliant mind and eye for design and was crucial is making a successful business presentation, something important not just for the judging rounds but in making pitches to potential investors.” Valencia’s team would go on to win third place in the interfaith category.
While it remains to be seen how successful VHacks will be in developing and scaling up hackathon projects for the real world, VHacks was tremendously successful in inspiring participants to think hard about how technology can be put to work for social good. Neil Chen, a veteran of over 10 hackathons, drew upon new social network analysis research done at Columbia to connect migrants in urban areas with local businesses to ease integration. “I’ve never before synthesized ideas from so many unique perspectives. After drawing from Professors Bellovin and Chaintreau’s paper on inferring ethnic migration patterns, we consulted with Maya, a Syrian refugee currently working as a web developer, and Bogomil Kohlbrenner, a social anthropologist from the University of Geneva, to figure out how to most effectively connect migrants to resources in their communities. Their experiences and Columbia research guided our application development.”
Deng and Shen’s team finished third in the social inclusion category with Xperience, a one-on-one livestreaming app intended to connect people who can’t travel—refugees and migrants, the elderly, those with disabilities—with others at a selected location who are willing to serve as guides, providing real-time, on-the-ground video. For Shen, the motivation came after attending the opening ceremonies and hearing how a Syrian refugee, separated from her family in Syria, was able through friends in France and Budapest to apply for a visa and help send money to her family. For those without such resources, Xperience serves as a virtual pen pal, providing long-distance experiences and friendships to those who may not have access to them.
And in including those otherwise excluded, Xperience perfectly fits the spirit of VHacks while showing the potential of technology and science to promote social good.
A PhD candidate advised by Shree Nayar, Smith is the creator of RAD (racing auditory display), which uses audio cues so players who are visually impaired can play existing video racing games.
Maynard Marshall Ball has been selected to receive a two-year IBM PhD Fellowship for the 2018-19 and 2019-2020 academic years. Highly competitive (only 50 are awarded worldwide each year), IBM PhD fellowships recognize and support PhD students researching problems important to IBM and fundamental to innovation. Special attention this year was paid to AI, security, blockchain, and quantum computing.
A third-year PhD student, Ball is particularly interested in the foundations of cryptography and complexity, two fields deeply intertwined and whose connections Ball seeks to further understand. According to his advisor Tal Malkin, Ball has made fundamental scientific contributions in three separate areas:
Fine-grained cryptography, where Ball has modeled moderately-hard cryptographic systems and crafted provably-secure proofs-of-work, with applications to blockchain technologies and spam detection.
Non-malleable codes, where Ball has designed codes with new unconditional security guarantees to protect against tampering attacks.
Topology-hiding computation, where Ball has helped maintain network privacy by constructing efficient secure protocols for peer-to-peer networks.
IBM PhD fellowships, which are for two years, come with a stipend for living, travel, and conference expenses (in the US, the stipend amounts to $35,000 each academic year) as well as one-year education allowance. Fellows are matched with an IBM Mentor according to their disciplines and technical interests, and they are encouraged to participate in an onsite internship.
“I am honored and thrilled to be able to continue working on the foundations of cryptography and complexity. I am grateful to my advisor and the many other incredibly talented individuals with whom I have collaborated with thus far. I look forward to working with the outstanding cryptography group at IBM,” says Ball.
“Discriminative Training Methods for Hidden Markov Models: Theory and Experiments with Perceptron Algorithms” laid the foundation for how to use machine learning methods across a range of natural language processing tasks.
Award cites Yung’s innovative contributions to computer and network security. Yung (CS PhD ’88) is an adjunct and visiting faculty at Columbia and has advised several PhD students including Gödel Prize winner Matthew K. Franklin.
Unequal parts hackathon and learnathon—the emphasis is solidly on learning—the annual DevFest took place last month with 1300 participants attending. One of Columbia’s largest tech events and hosted annually by ADI (Application Development Initiative), DevFest is a week of classes, mini-lectures, workshops, and sponsor tech talks, topped off by an 18-hour hackathon—all interspersed with socializing, meetups, free food, and fun events.
Open to any student from Columbia College, Columbia Engineering, General Studies, and Barnard, DevFest had something for everyone.
Beginners, even those with zero coding experience, could take introductory classes in Python, HMTL, JavaScript. Those already coding had the opportunity to expand their programming knowledge through micro-lectures on iOS, data science, Civic Data and through workshops on geospatial visualization, UI/UX, web development, Chrome extensions, and more. DevFest sponsor Google gave tech talks on Tensorflow and Google Cloud Platform, with Google engineers onsite giving hands-on instruction and valuable advice.
Every evening, DevSpace offered self-paced, online tutorials to guide DevFest participants through the steps of building a fully functioning project. Four tracks were offered: Beginner Development (where participants set up a working website), Web Development, iOS Development, Data Science. On hand to provide more help were TAs, mentors, and peers.
This emphasis on learning within a supportive community made for a diverse group and not the usual hackathon mix: 60% were attending their first hackathon, 50% were women, and 25% identified as people of color.
DevFest events were kicked off on Monday, February 12, with talks by Computer Science professor Lydia Chilton (an HCI researcher) and Jenn Schiffer, a pixel design artist and tech satirist; events concluded with an 18-hour hackathon starting Saturday evening and continuing through Sunday.
Ends with a hackathon
Thirty teams competed in the DevFest hackathon. Limited to a few members only, teams either arrived ready-made or coalesced during a team-forming event where students pitched ideas to attract others with the needed skills.
The $1500 first place went to Eyes and Ears, a video service aimed at making information within video more widely accessible, both by translating it for those who don’t speak the language in a video, and by providing audio descriptions of a scene’s content for people with visual impairments. The aim was to erase barriers preventing people from accessing the increasing amounts of information resources available in video. Someone using the service simply chooses a video, selects a language, and then waits for an email delivering the translated video complete with audio scene descriptions.
Eyes and Ears is the project of four computer science MS students—Siddhant Somani, Ishan Jain, Shubham Singhal, Amit Bhat—who came to DevFest with the intent to compete as a team in the hackathon. The idea for a project came after they attended Google’s Cloud workshop, learning there about an array of Google APIs. The question then became finding a way to combine APIs to create something with an impact for good.
The initial idea was to “simply” translate a video from any language to any other language supported by Google Translate (roughly 80% of the world’s languages). However, having built a translation pipeline, the team realized the pipeline could be extended to include audio descriptions of a video’s visual scenes, both when a scene changes or per a user’s request.
That such a service is even possible—let alone buildable in 18 hours—is due to the power of APIs to perform complex technology tasks.
Eyes and Ears: An end-to-end pipeline to make information in video more accessible through translations and audio scene descriptions.
It’s in the spaces between the many APIs and the sequential order of those APIs that required engineering effort. The team had to shepherd the output of one API to the output of another, sync pauses to the audio (which required an algorithm for detecting the start and stop of speech), sync the pace of one language to the pace of the other language (taking into account a differing number of words). Because Google Video Intelligence API, which is designed for indexing video only, outputs sparse single words (mostly nouns like “car” or “dog”), the team had to construct full, semantically correct sentences. All in 18 hours.
The project earned praise from Google engineers for its imaginative and ambitious use of APIs. In addition to its first place prize, Eyes and Ears was named best use of Google Cloud API.
The team will look to continue work on Eyes and Ears in future hackathons.
The $1000 second-place prize went to Nagish (Hebrew for “accessible”), a platform that makes it simple for people with hearing or speaking difficulties to make and receive phone calls using their smart phone. For incoming and outgoing calls, Nagish converts text to speech and speech to text in real time so voice phone calls can be read or generated via Facebook Messenger. All conversions are done in real-time for seamless and natural phone conversations.
The Nagish team— computer science majors Ori Aboodi, Roy Prigat, Ben Arbib, Tomer Aharoni, Alon Ezer—are five veterans who were motivated to help fellow veterans as well as others with hearing and speech impairments.
To do so required a fairly complex environment made up of several APIs (Google’s text-to-speech and speech-to-text as well as a Twilio API for generating phone numbers for each user and retrieving the mp3 files of the calls), all made to “talk” to one another over custom Python programs. Additionally, the team created a chatbot to connect Nagish to the Facebook platform.
For providing a needed service to those with hearing and speech impairments, the team won the Best Hack for Social Good.
Of course, potential users don’t have to be hearing- or speech-impaired to appreciate how Nagish makes it possible to unobtrusively take an important, or not so important, phone call during a meeting or perhaps even during class.
With Nagish uploaded to a smart phone, Facebook Messenger becomes a platform for making and receiving silent phone calls via speech-text conversion.
Taking the $750 third-place prize was Three a Day, a platform that matches restaurants or individuals wanting to donate food with those in need of food donations. The goal is making sure every individual gets three meals a day. The two-person team (computer science majors Kanishk Vashisht and Sambhav Anand) built Three a Day using Firebase as the database and React as the front end, with the back-end computing supplied primarily through Google Cloud functions. A Digital Ocean server runs Cron jobs to schedule the matching of restaurants and charities. The team also won for the best use of Digital Ocean products.
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
The National Science Foundation (NSF) has awarded a $1.2M, four-year grant to computer science theorists Christos Papadimitriou and Mihalis Yannakakis for their proposal “Research in Algorithms and Complexity: Total Functions, Games, and the Brain.”
With the Pope’s full support and encouragement, the Vatican held its first ever hackathon, 
Add to GMail