Q&A with Simons Institute Senior Scientist Venkat Guruswami

Venkatesan Guruswami joined the Simons Institute as our newest senior scientist on January 1. We hope you enjoy our conversation with Venkat about his visions for the field and for the Simons Institute.
 

How did you get interested in theoretical computer science?

I got into computer science for the somewhat pedestrian reason that it was a very highly sought-after subject to study at the IITs (Indian Institutes of Technology). I studied some programming in 11th and 12th grades, and algorithmic thinking seemed to align well with the kind of mathematical reasoning that I enjoyed, so I went with that choice even though I didn’t have much idea about computing. 

In my third semester, I took an amazing course on graph theory, taught in an inspirational and crystal-clear fashion by Professor S. A. Choudum. I was really hooked and also followed up with some research in enumerative graph theory under his generous mentorship. I realized soon after that even within CS I could essentially do math, which was my basic passion, by focusing on theoretical computer science. In addition to cherishing and doing well in the theoretical courses, in my junior and senior years I was fortunate to work under the advice of Professor C. Pandu Rangan, who had an amazing knack for engaging undergraduates in research and sending them onward to graduate school. I did a fair bit of work on graph-theoretic optimization problems and really enjoyed the research process. I also learned some of the frontiers of computational complexity, which further hooked me to TCS — in particular, reading Sanjeev Arora’s recent PhD thesis on the PCP theorem and Christos Papadimitriou’s complexity book was inspirational. I should point out that access to such latest books and preprints was not easy in India back then, and the TCS lab of Professor Pandu Rangan provided me privileged access to those resources. The lab became a sort of solace for me. During college, I was also fortunate to attend summer programs at TIFR (Tata Institute of Fundamental Research), Bombay, in mathematics — these exposed me to some graduate-level topics in a tasteful way. In particular, the commutative algebra and algebraic number theory I learned there really fascinated and had a profound influence on me, and later also found its way into some of my research, taking it in some interesting and unexpected directions.

So I want to give a big shout-out to the excellent undergraduate program at IIT and my inspiring peer group, the generous mentorship of Professors Choudum and Pandu Rangan, and a healthy dose of luck (and some courage), for setting me on the path to a PhD in CS. In general, the role which good mentors play in molding successful students cannot be overemphasized, and I am grateful to have benefited from some amazing mentorship and advice in my career. In my view, working with and mentoring passionate students is also the most gratifying part of a professor’s life.

I ended up at MIT for my PhD, and then something wonderfully serendipitous happened: Madhu Sudan joined its faculty that very fall — a stroke of very lucky timing for me! I had come across many of his works and had longingly imagined working with someone with such a profile: Madhu’s interests in PCPs, approximate optimization, and algebraic methods were literally my dream combination. I became one of his early PhD students, and it was a total blast — I couldn’t have planned it better with any amount of foresight!
 

What research questions are you interested in right now?

I might be old-fashioned in that the directions I am interested in fit the same broader themes as my early career works, which include error-correcting codes, approximate optimization, and pseudorandomness. Of course, a lot has changed since then due to the ensuing progress, and I have focused on some entirely new angles within the topics (particularly in coding theory, with topics such as polar codes and codes for distributed storage only emerging in the last decade or so, and really taking off since).

I believe in the unity of theoretical computer science and enjoy working in a number of interconnected areas. Broadly, I am drawn to fundamental questions where there is a substantial gap in our knowledge — for example, between algorithms and hardness results, or existential and constructive results, or information-theoretic and computational thresholds, or where the gap results from differing perspectives and technical language barriers. For example, while the approximability of many discrete optimization problems is well understood, several basic questions in continuous optimization, such as optimizing a low-degree polynomial on some convex set or computing operator norms, baffle us. A similar situation prevails in pseudorandomness, where continuous analogs of error-correcting codes (good Euclidean sections) remain hard to explicitly construct. While the theory of error correction against substitution errors is well developed, many basic mysteries remain concerning codes for synchronization errors such as deletions (though there has been steady and good progress in recent years). In each case, the questions are fundamental, but also naturally arise in applications. 

These days I continue to investigate probabilistic, combinatorial, and algorithmic aspects of error-correcting codes in diverse models, together with many collaborators. I have always been fascinated by constraint satisfaction problems (CSPs), and in the post-CSP-dichotomy world, our continuing forays into promise constraint satisfaction — which are a compelling and vast generalization of the CSP framework — have generated a lot of interest. I am also excited, on the heels of some of our work on algorithms (both efficient and nondeterministic) for refuting smoothed CSP instances, about the prospect of certifying pseudorandom properties as a functional proxy for explicit constructions that remain out of reach. Looking further afield from fully theoretical work, there is a burgeoning body of work on using deep learning methods to design codes and/or decoding algorithms that I am quite intrigued (but not yet knowledgeable) about. Especially for noise settings that can’t be crisply modeled, and perhaps even for some classical models, this might be a fruitful way to make practical progress.
 

What are your aspirations as senior scientist at the Simons Institute?

This unique position will place me right in the midst of all the exciting action that happens at the Simons Institute semester after semester, spanning a whole spectrum of topics. This will expose me to the cutting edge of research in so many fields, some close to my core interests but many further afield. In such an environment, I hope to expand my horizons and recalibrate my vision of the field’s immense possibilities. My most favorite part of academic life is the privilege of learning from and working with junior researchers, who are responsible for a large number of the field’s breakthroughs. With the Simons Institute bringing together an amazing cohort of postdocs and research fellows each semester, interacting with them on a regular basis will be eye-opening, rewarding, and fun, and something I am really looking forward to. I also hope to assist, in whatever ways I can, the process of sustaining the roster of impressive semester programs and ensuring their efficient functioning. The success with which this has been accomplished in the first decade with a mind-expanding (and field-expanding) array of programs has rightfully catapulted the Simons Institute as the global hub for innovation in theoretical computer science. I hope to do my part in ensuring the continued success of the Institute in this regard, and also help with its many associated outreach initiatives.

I am hoping that the environment and interactions will also steer my own research in new directions. For example, while I have worked on error correction in many models, I am yet to work on quantum error correction, which is a topic of rapidly increasing significance. I can imagine that all the current quantum-related activity at the Simons Institute will inspire me to delve into this subject. But I’m hoping there are many topics I can’t even currently foresee that I’ll have the fortune of exploring, inspired by all the creative and passionate researchers who grace the halls of the Simons Institute each semester.
 

What role does the Simons Institute play within the theoretical computer science ecosystem?

The formation of the Simons Institute was perfectly timed. Theoretical computer science was making enormous strides — with regular breakthroughs on old questions, broadening to include further foundational topics under its wings, and ambitiously expanding its reach beyond computer science by providing a framework for posing and addressing challenges in diverse areas with underlying computational phenomena (either designed or natural). Further, the field was attracting incredible talent. The quality of students we attract year after year is mind-boggling and humbling (I’m relieved I’m not applying to grad school in current times!).

With all its momentum and potential, what was missing for TCS was a global hub, which would highlight, celebrate, continually enable, and further enhance all these amazing things that were going on. 

And the Simons Institute has accomplished precisely that, beyond even the most optimistic expectations. It has curated and hosted a large variety of programs covering pretty much all corners of theory, targeting the very core of the field and its deep long-standing questions, the emerging areas where foundational work is happening now, as well as connections to engineering, mathematics, sciences, social sciences, and economics. The Institute has been really good for the branding of theory, and the increase in its stature amongst the sciences. Hopefully in due course it will facilitate theoretical CS to have the kind of broad cachet in the public eye which, say, physics or medicine enjoy. TCS, of course, deserves this, given the foundational and pervasive nature of computation (admittedly I’m biased here). Kudos to the Institute leadership and management team who have been doing a great job with the newsletters, SimonsTV, and the other outreach activities, both online and in person. I think the theory of computing as a field is in its prime, and the Simons Foundation and the Institute have accelerated the significant recognition of the field’s accomplishments and immense potential.
 

You were a program organizer for the Simons Institute’s spring 2015 program on Information Theory. What did you learn from that experience, and how will it inform your approach as senior scientist?

First of all, the program was a blast, and it was an honor and pleasure to co-organize it. The program epitomized the tenet of the Institute that the program activities shouldn’t be business as usual, but achieve a whole that’s bigger than the sum of its parts, with collaborations that are otherwise unlikely.

Coding and information theory have traditionally been addressed in two communities, by communication engineers, who are typically housed in electrical engineering departments, and by theoretical computer scientists and discrete mathematicians, who tend to be in math or CS departments.

Despite roughly similar goals, these communities have largely progressed in parallel in their own ways.

One thing I learned from the program is the power of bringing together people from across the aisle, creating an intense cross-pollination of ideas over an extended period of time, and then magical things organically happen. Breakthroughs occurred by synthesizing the viewpoints of both communities, and program participants (including myself) worked on questions they wouldn’t have investigated otherwise, with new collaborators they wouldn’t have had a chance to interact with in such depth. It was also serendipitous that we were the only program that semester, so there was never a shortage of breakout space or seminar rooms to meet and interact with people in an impromptu fashion.

I also appreciated the significant lead time and careful planning needed to ensure that a quorum of senior researchers are present for extended periods to provide perspective, vision, and mentorship, and the importance of attracting a strong and diverse group of junior fellows who bring their bold ideas and technical strength to the collaborations. A special shout-out to then-Associate Director Alistair Sinclair, who went above and beyond to help us with the planning and meeting all the deadlines. His attention to detail and excellent guidance on every aspect of the planning and organization was truly extraordinary.

While coordinating the details of program planning with organizers doesn’t directly fall under my responsibilities as senior scientist, I’ll be happy to share my experiences as organizer and provide feedback to planning teams as appropriate. I expect to be involved in the solicitation of topical semester programs and summer clusters, and I also hope to be part of the organizing teams for some programs in the coming years. For programs with a good level of overlap with my expertise and interests, I look forward to being as engaged on the scientific aspects as my schedule permits.
 

The Simons Institute’s senior scientists oversee the Institute’s mentorship program for our postdoctoral-level research fellows. Can you talk a bit about the mentorship program, and anything you have in mind for ways to enhance it?

As I already mentioned, the research fellows program is in my eyes one of the most attractive features of the Simons Institute programs. These are top young researchers in their fields, brimming with ideas and energy, and it is going to be exhilarating to be amongst them. The junior fellows are an integral part of the thematic programs, and as such their academic pursuits at the Institute are taken care of by the program activities. In my senior scientist role, I look forward to weekly gatherings with the fellows, and learning about their interests and research via informal chats as well as technical presentations. Hopefully there will also be casual social outings that we will organize regularly. This would be especially useful because postdocs don’t usually have a natural peer group (unlike, say, PhD students), but at the Simons Institute they do because of the common program umbrella. It will be great to take advantage of this to both create a sense of belonging among the fellows and enhance serendipitous interactions and collaborative discussions amongst them.

When I have postdocs in my group, we usually collaborate intensely in one-on-one settings. This is not something feasible in the context of a large body of postdocs at the Institute. Hopefully there should be enough program activities and collaborations to keep all the postdocs busy, but when relevant, I’ll also try to facilitate connections that might exist in the broader UC Berkeley context, such as PhD students or departmental postdocs with similar interests (this could extend beyond technical matters — for example, for career planning and job applications). Of course, for this I need to first get my feet wet and get a sense of the immense scale of research activities in EECS, Math, and other corners of UC Berkeley — I very much look forward to this learning experience.
 

The Simons Institute seeks to broaden participation at the Institute and in the field of theoretical computer science across a variety of parameters: gender, ethnicity, race, country of origin. What are your perspectives on ways to enhance our impact in this area?

I applaud the attention the Simons Institute gives to broadening participation, and the Institute is already doing a great job in some quarters. For example, the percentage of women in Simons programs is a noticeable notch higher than the community averages, and this is robust across multiple measurement metrics. Unfortunately, for other groups of underrepresented minorities, the numbers in the field are so low that even if the Institute had two or three times higher representation, the participation would still be embarrassingly small. 

For the post-PhD stage, I know the Simons Institute urges program organizers to pay special attention to diversity in their cohort of long-term participants and program fellows. The Institute has been very successful in fundraising from industry for many of its fellows — perhaps this can be augmented with some diversity-focused fellowships (similar to several such fellowships that have emerged for PhD students in recent years) as an added recruiting boost for postdocs from underrepresented groups.

In my previous role as PhD program director at Carnegie Mellon, I have given some thought to the challenge of improving the diversity of the PhD student body. There are two significant hurdles one faces in this quest — one is getting the pipeline of the applicant pool and admitted students to be more representative, and the second relates to recruitment and retention.

The Simons Institute can play an influential role in the latter aspect. The Simons Institute already hosts events like Women in Theory regularly. Perhaps there can be diversity-focused residency programs, where PhD students can come and spend a semester at Simons as a visiting student. There would be a clear case for this if their research fits the themes of the current programs, but even otherwise, such a semester can be eye-opening and inspiring for students when they witness the diversity of program participants and activities, and the excitement in the field broadly.

Regarding the former aspect, on improving the pipeline of entering PhDs in theoretical CS, summer schools or undergraduate research programs under the auspices of the Simons Institute might be an avenue to consider. The recently launched David Harold Blackwell Summer Research Institute is an exciting venture, and I am glad that the Simons Institute is providing organizational support and convening space for it. There must also be a lot of activities already happening on the UC Berkeley campus which one can leverage for attracting students to graduate studies in computer science. For instance, if students are coming under REU (Research Experiences for Undergraduates) programs to work with Berkeley faculty in the summer, perhaps they could be invited to attend some talks at the Simons Institute geared towards a broad audience. One can also imagine an outreach-focused TCS conference for a couple of days each summer. This will align with other excellent outreach activities such as Richard M. Karp Distinguished Lectures and Theoretically Speaking series already happening at the Simons Institute during the academic year. So while the diversity problem is too broad and complex in scope for the primary mission of the Simons Institute to tackle head-on, the Institute can capitalize on and influence existing initiatives in the community and at UC Berkeley.

Can you comment on how TCS has evolved since you first entered the field? And where do you think it’s headed in the next 10 years? What kinds of developments can we look forward to?

TCS is a young and vibrant field, and has evolved and made progress at an incredible rate. The evolution of the field has been on multiple fronts. 

One is obviously the depth and sophistication of the field. TCS has been very good at internalizing tools from various areas of mathematics in a significant way at various stages to break new ground in our understanding of computation. TCS itself can be viewed as a branch of mathematics, so this symbolizes an aspect related to the unity of mathematics. In early days, topics in logic and discrete mathematics (combinatorics, graph theory) naturally played a big role (and of course continue to do so). Soon probability also became a prominent tool. The rise of interactive proofs, PCPs, and algorithmic coding theory ushered in algebraic methods, often in a potent combination with probability. With quantum computing and spectral graph theory, linear algebra became indispensable (in many other areas too). Analytic tools to study Boolean functions became important in many areas, including learning, PCPs, and pseudorandomness. Algebraic geometry and topology make influential appearances in coding theory and distributed computing. Number theory has always played a pivotal role in cryptography, and lattices and other advanced mathematical constructs drive a lot of modern cryptography research. And the list goes on and on. 

The sophistication of theoretical CS has thus grown immensely in the past two to three decades, and in many subfields there has been a steady accumulation of knowledge and techniques leading to deep results that were unimaginable a decade prior. A flip side to this is that the general amount of preparation needed to begin cutting-edge research has also been steadily increasing. Yet, crisp, accessible, and compelling questions remain, and as I said, the field attracts amazing talent. So students are able to make a large chunk of impressive contributions to the field, and undergraduate research is also thriving, with many students having impressive research experience prior to graduate school. I think this combination is incredibly healthy for the field. We are upping the game, but the community is comfortably tackling the challenges, and is poised for ever greater achievements.

The second big evolution has been in the kind of questions the field tackles, broadening significantly from the original computational setting of mapping a well-defined input to a specific desired output. Modern algorithmic research deals with inputs that are distributed, uncertain, stochastic, dynamic, streaming by, private, or strategically revealed, and that are often too big to even be read fully. Entire subfields have emerged to tackle various combinations of constraints on the inputs, desired outputs, and computational restrictions. The accelerated adoption of algorithms and data-driven approaches for decision-making in all walks of life has ushered in a revolution but also upped the ante for algorithmic research. Theoretical CS is now gearing up to tackle exciting new frontiers such as fairness, responsible computing, and sustainability. The field has naturally grown and broadened in light of this evolution, but I’d say that overall we are still pretty small and punch well above our weight. 

Another unique feature of theoretical CS is how the interplay with technological needs and developments can rejuvenate the field. To give an example closer to my research, ensuring reliability and availability of data on large-scale cloud storage systems has opened up a host of questions concerning error-correcting codes. Old coding questions then come with some new frills, and suddenly some beautiful basic questions arise. These could have well been posed 50 years ago, but the time for them only came in the wake of recent computing demands.

In this exciting backdrop, it is hard to predict (at least for me) where the field is headed in the next 10 years. Some things, however, seem clear to me. Amazing talent will continue to be attracted to the compelling questions and far-reaching impact of the field. So we will get ambitious and talented people, and they will do amazing things. I am hopeful that there will be noteworthy progress on some classical long-standing goals of the field. We probably won’t resolve P vs. PSPACE or LOGSPACE vs. NP or anything close to that in the next 10 years, but that's perfectly reasonable and I think we will learn a lot and know more about some fundamental questions a decade from now than we do today. And I think that's all we can really ask for in a field as deep and as young as TCS.

I feel confident that the stature of the theory of computing within computer science, and in the broader landscape of science and engineering, will steadily increase, and the Simons Institute will have a big role to play in this regard. Theoretical computer scientists are naturally curious and seek out interesting, challenging problems where computational thinking plays a vital role, regardless of their origins. Our track record in recent times is testament to this trend, and I think the theory of computing will have a meaningful and long-lasting impact on several adjacent and not-so-adjacent areas. I can’t wait to see how all this unfolds, and feel privileged that I have the opportunity to witness it from the vantage point of the Simons Institute.