(Virtual) DIMACS Workshop on Entropy and Optimization on May 18, 19, 2022

Mohit Singh and I are organizing a two-day virtual DIMACS Workshop on Entropy and Optimization that starts tomorrow — May 18, 19, 2022.

We have a stellar lineup of speakers:

Nima Anari (Stanford University), Alexander Barvinok (Michigan), Mark Braverman (Princeton), Sebastien Bubeck (Microsoft Research), Péter Csikvári (Alfred Renyi Institute of Mathematics), Zongchen Chen (MIT), Ronen Eldan (Weizmann), Tali Kaufman (Bar-Ilan University), Jon Lee (Michigan), Shayan Oveis-Gharan (U Washington)

The goal of this workshop is to explore various connections between entropy, optimization, and sampling. Entropy-maximizing probability distributions have been recently used in interesting ways in applications such as algorithms for counting problems, algorithms for NP-hard optimization problems, and interior-point methods for convex programming

Attendance to the workshop is free but registration is required. To see the program of the workshop and register, visit here.

Looking forward to seeing many of you there!

FOCS 2021 Talk Videos

After more than a year of planning, FOCS 2021 concluded yesterday.

In case you missed all or part of the event, the talks for all of 117 papers and for the three workshops are now available on this youtube channel.

The full versions of all papers (and videos) are also freely available here.

Many thanks to more than 1000 people, including authors, program committee members, external reviewers, organizers, TCMF members, volunteers, and attendees for making this happen!

FOCS 2021 is (Virtually) Here!

The 62nd Annual IEEE Foundations of Computer Science (FOCS) will be held (virtually) February 7-10, 2022 — this coming Monday!

Thanks to the effort of the progam committee, the FOCS 2021 program consists of 118 amazing papers in three parallel sessions. All talks will be live and of the usual length of 20 minutes. The program has also set aside ample time for breaks to enable the participants to socialize and connect on gather and slack.

FOCS 2021 also has three exciting workshops as a part of the main program:

1) Recent directions in Machine Learning: co-organized by Daniel Hsu, Aleksander Madry, and Aravindan Vijayaraghavan, and and featuring Anima Anandkumar, Elias Bareinboim, Risi Kondor, Christopher Manning, Andrej Risteski, Cynthia Rush, Jacob Steinhardt.

2) Reflections on Propositional Proofs in Algorithms and Complexity: co-organized by Toni Pitassi, Susanna de Rezende, and Robert Robere, and featuring Sam BussJoshua GrochowPravesh K. KothariJan KrajíčekToni PitassiSusanna de Rezende, Robert RobereRahul SanthanamNeil Thapen.

3) Workshop on Cryptography: co-organized by Dan Boneh and Amit Sahai, and featuring Elette Boyle, Aayush Jain, Yuval Ishai, Rachel Lin, Wilson Nguyen, Rafael Pass, Hoeteck Wee.

Registration is still open and available at a reduced rate of $100-150 for participants.

Thanks to generous support from the National Science Foundation, there will be a total of $15,000 in support for FOCS 2021 for eligible students and postdoctoral fellows towards registration fee.

Looking forward to seeing many of you next week!

Update: Junior/Senior Lunches by Clement Cannone and Gautam Kamath:

Back by popular demand! As part of FOCS 2021, and in view of the success of similar events in the past, a “junior/senior lunch” will take place on Tuesday February 8, 1:30PM-2:30pm ET. Importantly, this is not limited to FOCS attendees! As in previous years, this virtual lunch will be the occasion for senior researchers in the field, broadly construed, to have an informal chat with students, postdocs, and junior faculty, answer their questions, discuss their research, and generally have a nice conversation.

To participate as either a senior or junior researcher, please write your name in this spreadsheet. Further instructions will be sent to people who sign up.  If you are on the “senior” side of the lunch, you will be responsible for contacting the corresponding juniors, and provide a Zoom link.

FOCS 2021 Best Paper Awards

On behalf of the FOCS 2021 PC, I am delighted to announce the Best Paper Awards.

Best paper:

Nutan Limaye, Srikanth Srinivasan and Sébastien Tavenas. Superpolynomial Lower Bounds Against Low-Depth Algebraic Circuits

This paper makes a fundamental advance by proving super-polynomial lower bounds against algebraic circuits of arbitrary constant depth.

Paper: https://eccc.weizmann.ac.il/report/2021/081/

Machtey Award for Best Student Paper:

Xiao Mao. Breaking the Cubic Barrier for (Unweighted) Tree Edit Distance

This paper shows how, unlike the weighted case, the unweighted tree edit distance problem has a sub-cubic time algorithm.

Paper: https://arxiv.org/abs/2106.02026

Congratulations to the winners and see you all in Denver from Feb 7-10, 2022!

Submit your papers to the 62nd FOCS!

The submission server for the 62nd FOCS is open!

Please read the Call for Papers carefully before you submit.

Below are some important points:

  • The title/abstract registration deadline is 5 pm EDT on May 31st, 2021. Since this information will be used in paper assignments, significant changes to the title/abstract will not be allowed after this deadline.
  • The full paper submission deadline is 5 pm EDT on June 3, 2021.
  • The conference is expected to take place physically in Boulder, Colorado Feb 7-10, 2022.
  • Papers that broaden the reach of the theory of computing, make foundational connections to other areas, or raise important problems and demonstrate that they can benefit from theoretical investigation and analysis are especially encouraged.
  • Reviewers will be asked to evaluate submissions both on conceptual and technical merits. So, authors are encouraged to emphasize both conceptual and technical novelty in the first few pages of the paper. 
  • FOCS is an IEEE conference and as such, we will review papers in alignment with the IEEE ethics guidelines. Authors are encouraged to reflect on these guidelines in shaping their work, dissemination, and submission.

The PC is eagerly looking forward to your submissions!

Algorithms for Convex Optimization Book

I am excited to announce that a pre-publication draft of my book Algorithms for Convex Optimization (to be published by Cambridge University Press) is now available for download here:

Algorithms for Convex Optimization Book

The goal of this book is to enable a reader to gain an in-depth understanding of algorithms for convex optimization. The emphasis is to derive key algorithms for convex optimization from first principles and to establish precise running time bounds in terms of the input length.

The intended audience includes advanced undergraduate students, graduate students and researches from theoretical computer science, discrete optimization, and machine learning.

The book has four parts:

  1. Chapters 3,4, and 5: Introduction to convexity, models of computation and notions of efficiency in convex optimization, Lagrangian duality, Legendre-Fenchel duality, and KKT conditions.
  2. Chapters 6,7, and 8: First-order methods such as gradient descent, mirror descent and the multiplicative weights update method, and accelerated gradient descent.
  3. Chapters 9,10, and 11: Newton’s method, path-following interior point methods for linear programming, and self-concordant barrier functions.
  4. Chapter 11 and 12: Cutting plane methods such as the ellipsoid method for linear and general convex programs.

Chapter 1 summarizes the book via a brief history of the interplay between continuous and discrete optimization: how the search for fast algorithms for discrete problems is leading to improvements in algorithms for convex optimization.

Many chapters contain applications ranging from finding maximum flows, minimum cuts, and perfect matchings in graphs, to linear optimization over 0-1-polytopes, to submodular function minimization, to computing maximum entropy distributions over combinatorial polytopes.

The book is self-contained and starts with a review of calculus, linear algebra, geometry, dynamical systems, and graph theory in Chapter 2. Exercises posed in this book not only play an important role in checking one’s understanding, but sometimes important methods and concepts are introduced and developed entirely through them. Examples include the Frank-Wolfe method, coordinate descent, stochastic gradient descent, online convex optimization, the min-max theorem for zero-sum games, the Winnow algorithm for classification, the conjugate gradient method, primal-dual interior point method, and matrix scaling.

Feedback, corrections, and comments are welcome.

The dynamics of Lagrange and Hamilton

In 1788, Lagrange presented a set of equations of motion that, unlike Newtonian mechanics, are independent of the choice of coordinates of the physical system, and ultimately led to the formulation of general relativity. Hamilton came up with a different set of equations of motion in 1833 that arguably led to the development of quantum mechanics. Remarkably, in classical mechanics, these sets of equations turn out to be equivalent via a beautiful duality due to Legendre.


A portrait of Legendre by H. Rousseau, E. Thomas, Augustin Challamel, and Desire Lacroix via Wikimedia Commons

Lagrangian and Hamiltonian dynamics have inspired several promising optimization and sampling algorithms such as first-order methods in optimizationHamiltonian Monte Carlo (see also this paper that will appear in NIPS 2018). Legendre duality also appears in convex optimization as Fenchel dualityThis note, written primarily for optimization folks, introduces Lagrangian dynamics, Hamiltonian dynamics, and proves the duality that connects them.

I hope that these fundamental ideas inspire you as well to think about optimization from a physics perspective!



Fair Elections

Elisa Celis and Nisheeth Vishnoi

Elections are the nervous system of a democracy and, hence, issues related to their transparency and fairness are central to healthy societies. However, the number of controversial elections has exploded since 2000, and the more recent ones involve the use of the Internet and algorithms — a good excuse for computer scientists to get involved in elections to save democracy!

Last year, the two of us and Lingxao Huang revisited the question of fairness in multi-winner elections. A multi-winner election is one where the objective is to select a committee from a set of candidates based on voter preferences. However, election systems for multi-winner elections have been shown to be biased against minorities by giving preference to committees that under-represent their already-small numbers. When the candidates have certain sensitive attributes (such as gender), and different types (e.g., male, female and non-binary) we may instead wish to impose additional requirement so that the winning committee is fair. We considered the problem of finding the committee with the maximum number of votes, subject to such additional fairness requirements.

But what does it mean to be fair?

Is a committee fair when types are equally represented? Or proportionally represented? These questions have received more than a century’s worth of attention in social choice theory and are deeply entangled with culture and politics. In short, fairness means different things in different contexts and rather than addressing a specific instance of this question, we asked ourselves — can we provide a framework in which a user can specify fairness constraints according to their needs and design algorithms that can compute the winning committee accordingly?

Because such a framework must handle general classes of constraints, the algorithmic task became more challenging than the usual unconstrained case. If you are interested in understanding our algorithmic and complexity results, they appear in our recent paper that was presented at IJCAI-ECAI this year.

Clearly, however, there are real merits to providing such generality — earlier this year, our paper caught the eye of members of a people’s movement from the Valais canton in Switzerland, who were in the process of rethinking elections in their region. They were happy to know that we had solved the exact problem they needed for a primary election and asked us if we would be willing to help them conduct their elections. We were, of course, thrilled!

After an intense collaboration for more than four months, 8 elections that used our framework concluded on September 9, 2018. For us, there were several eye-opening aspects of taking our algorithmic framework from theory to practice. Perhaps the most interesting one was coming up with an answer to:

Who decides what is fair?

In this case, it was the voters! Before voting on the committee, a vote to determine the fairness constraints was conducted in each of the eight districts. This vote was in mid-June and also checked if the voters agree to use our algorithmic framework. Since transparency was the key motivation, prior to this vote,  we were invited to a press conference to educate the people about the whole process that resulted in coverage in newspapers Le Temps,  Le Nouvelliste, TV channel Canal 9, and radio channels Rhone FM and  Radio Chablais.


An image from the press conference in Sion on June 12, 2018. Elisa Celis (center), accompanied by members of Appel Citoyen.

In the end, the voters decided to place constraints on the gender balance, age demographics, and regions. While all districts approved these same three attributes, the specific constraints varied by district according to their demographics and pre-defined regions. This was a truly open and democratic way to determine the criteria by which the committee was to be balanced. The constraints not only ensured that the outcome would be fair (as defined by the voters) but also encouraged many more women to run for election than the party originally anticipated — in fact, in several districts there were more women than men contesting the election!


Computing the winning committees in Sion on September 9, 2018. From L to R: Lingxiao Huang, Vijay Keswani, Elisa Celis, Florian Evequoz, Bernadette Morand-Aymon.

Everything about these elections, from votes, candidates, constraints, and code, to the output, is open for all to verify. We have also made available a demo with pre-loaded constraints, candidate information, and votes for anyone to test and compute the results. To know more about the use of our algorithm in these elections, take a look at this video. A few links to the coverage of these elections can be found here: Canal 9,  Le Temps, Le Nouvelliste.

We feel fortunate that we were given this unique opportunity to take tools from computer science to the heart of a democratic process. It was an unparalleled learning experience for all of us and something that we increasingly look forward to in the future.



You can also use our demo to design your own elections and play around with our algorithms. This demo was developed with the help of Abhibhav Garg and Vijay Keswani and has limited functionality. If you are interested in using our full framework and/or working with us,  please feel free to contact us.



An Exposition on Geodesic Convexity

I arrived at the Institute for Advanced Study to attend a workshop on Optimization, Complexity and Invariant Theory organized by Avi Wigderson. The workshop has an incredibly diverse agenda, also reflected in the participants.

I will talk about Geodesic Convexity: Sometimes, functions that are non-convex in the Euclidean space turn out to be convex if one introduces a suitable metric (or differential structure) and redefines convexity with respect to the induced straight lines — geodesics. Such a function is called geodesically convex. Unlike standard convexity,  when does a function have this property and how to optimize it, is not well-understood. My talk will focus on introducing geodesic convexity and show that the problem of computing the Brascamp-Lieb constant has a succinct geodesically convex formulation.

And, accompanying my talk are these self-contained and expository notes on differentiation on manifolds, geodesics, and geodesic convexity that are prepared with the help of my student Ozan Yildiz.