Theory of Computing Report

The Swiss Winter School on Theoretical Computer Science (Jan 26 — 31 2025, https://theory.epfl.ch/WinterSchool2025/) is the third installment in a series of annual winter schools jointly organized by EPFL and ETH Zurich.
The goal of the school is to educate outstanding international PhD students about exciting recent developments in theoretical computer science.
The winter school will be held in Zinal, a mountain village in the Swiss Alps that has a long tradition of hosting academic workshops and that allows for nice excursions and stimulating discussions in a relaxed atmosphere.

This year’s installment features an exciting trinity of speakers:
Anupam Gupta (NYU), Toni Pitassi (University of Toronto), and Thomas Vidick (EPFL)

For full consideration, applications must be submitted by October 14th 2024.
Notifications will be sent by November 1st 2024.
The application form is available at https://theory.epfl.ch/WinterSchool2025/.

The winter school is organized by Mika Goos (EPFL), Michael Kapralov (EPFL), Rasmus Kyng (ETH Zurich), David Steurer (ETH Zurich), Ola Svennson (EPFL).

By Boaz Barak

This is the second part of the live blog of Lecture 9 of my graduate class “Convex Optimization.” A Table of Contents is here.

What a difference a lecture makes. Yesterday morning, I was apprehensive about class because I couldn’t find a satisfying and intuitive explanation of duality. But… now I think I have one? Let me try it out on you, my dear readers, and let me know if this clarifies anything for you or if it makes things even more confusing. 

Advance warning: I’ve been trying to keep these blogs on the less technical side, but Friday posts have ended up being extra technical. Today’s Friday post is not an exception to this emergent rule.

Earlier this week, I discussed what it would mean to prove that you’ve found a solution to an optimization problem. If you have a candidate solution, you can plug it in and check feasibility. This is usually easy enough to compute. However, verifying optimality was more involved as we had to check conditions held for all points in the feasible set. I gave a few examples of ways to construct such proofs of optimality. Duality theory provides a path that generalizes all of them.

The main idea is to construct lower bounds. If you had a way of rigorously generating lower bounds on the optimization problem, and the lower bound equaled the objective value of your candidate solution, then you would have a proof of optimality. You need a potential solution and a lower bound saying that all points have objective value greater than or equal to the one you are proposing.

Duality starts with an explicit construction of lower bounds to optimization problems. We find a family of lower bounds and then construct a dual problem by finding the best lower bound. This will be called the dual problem.

Let’s consider the constrained optimization problem.

For now, I won’t assume anything about the convexity of these functions. We can think of constrained optimization as unconstrained optimization if we let ourselves work with functions that can map a point to infinity. Solving the optimization problem is the same as minimizing the unconstrained function

You might not have a good algorithm to deal with infinities, but from a conceptual standpoint, this extended real-valued function captures what the optimization problem means. The only x with finite objective are the feasible points.

I can define a family of lower bounds for my extended real-valued function p(x) by introducing the Lagrangian:

The Lagrangian has three arguments. It takes a primal value x and two Lagrange multipliers 𝜶 and β. For fixed Lagrange multipliers, the Lagrangian is a lower bound of the function p as long as 𝜶 is greater than or equal to zero. This is because if you plug in a feasible x, the first summation will be nonpositive and the second summation will be zero. Therefore, the Lagrangian yields a value less than f₀(x). For a nonfeasible x, the Lagrangian will be some number less than infinity. 

How tight are these lower bounds? For a fixed x, we have 

That is, for each x, there is a sequence of Lagrange multipliers so that the value Lagrangian converges to p(x). To see why, note that if x is feasible, you’re going to want to set 𝜶_i to zero whenever an inequality constraint is satisfied. But if x is not feasible, the supremum must be infinite. If f_i(x) is greater than 0, the supremum of 𝜶_i is infinity. Similarly, if an h_j(x) is nonzero, the supremum with respect to β_j is infinite. Following this argument to its logical end, I’ve argued that the original optimization problem we cared about is equivalent to the minimax problem

Now let’s think about the quality of the lower bound provided by each fixed assignment of the Lagrange multipliers. First, the Lagrangian is unconstrained, so you might try to run gradient descent to find a minimum. Since this Lagrangian function is a lower bound of our optimization problem, if the minimum that you find is feasible, you have found an optimal solution of the optimization problem. That’s pretty powerful already! If you instead find a nonfeasible point when minimizing the Lagrangian, you still get a lower bound on the optimal value of the original optimization problem. For each 𝜶 and β, we can quantify the value of this bound with the dual function

The value of g is always a lower bound on the optimal value of the optimization problem. Over all choices of the Lagrange multipliers, the best lower bound is also a lower bound. The maximin problem

is called the Lagrangian dual problem or usually just the dual problem. Our original problem is then retroactively dubbed the primal problem. The optimal value of the dual problem is always a lower bound of the primal problem. This inequality is called weak duality and follows from the simple argument I wrote yesterday. Today’s exposition has motivated duality as a way of generating lower bounds, so this shouldn’t be too surprising.

Now, why should we care about this family of lower bounds? The Lagrangian is an affine function of the Lagrange multipliers. The dual function is an infimum of affine functions. That means it is concave, no matter what f_i and h_j are. The dual problem is always a convex optimization problem.1 We’ve derived a powerful tool to construct lower bounds for intractable problems.

In convex programming, there’s a second remarkable benefit. If the primal problem is convex and properly conditioned, then the dual and primal optimal values are equal. This is called strong duality. With strong duality, we have arrived at our initial goal of proving a particular solution of the primal problem is optimal. A dual optimal solution certifies the optimality of a primal optimal solution. Moreover, these primal and dual solutions often come in pairs, where you can compute one from the other. I will cover strong duality and such optimality conditions next week.

Subscribe now

By Ben Recht

Authors: Euiwoong Lee, Ola Svensson, Theophile Thiery

For any $\varepsilon > 0$, we prove that $k$-Dimensional Matching is hard to approximate within a factor of $k/(12 + \varepsilon)$ for large $k$ unless $\textsf{NP} \subseteq \textsf{BPP}$. Listed in Karp's 21 $\textsf{NP}$-complete problems, $k$-Dimensional Matching is a benchmark computational complexity problem which we find as a special case of many constrained optimization problems over independence systems including: $k$-Set Packing, $k$-Matroid Intersection, and Matroid $k$-Parity. For all the aforementioned problems, the best known lower bound was a $\Omega(k /\log(k))$-hardness by Hazan, Safra, and Schwartz. In contrast, state-of-the-art algorithms achieved an approximation of $O(k)$. Our result narrows down this gap to a constant and thus provides a rationale for the observed algorithmic difficulties. The crux of our result hinges on a novel approximation preserving gadget from $R$-degree bounded $k$-CSPs over alphabet size $R$ to $kR$-Dimensional Matching. Along the way, we prove that $R$-degree bounded $k$-CSPs over alphabet size $R$ are hard to approximate within a factor $\Omega_k(R)$ using known randomised sparsification methods for CSPs.

Authors: Kasper Green Larsen, Omar Montasser, Nikita Zhivotovskiy

Multi-distribution or collaborative learning involves learning a single predictor that works well across multiple data distributions, using samples from each during training. Recent research on multi-distribution learning, focusing on binary loss and finite VC dimension classes, has shown near-optimal sample complexity that is achieved with oracle efficient algorithms. That is, these algorithms are computationally efficient given an efficient ERM for the class. Unlike in classical PAC learning, where the optimal sample complexity is achieved with deterministic predictors, current multi-distribution learning algorithms output randomized predictors. This raises the question: can these algorithms be derandomized to produce a deterministic predictor for multiple distributions? Through a reduction to discrepancy minimization, we show that derandomizing multi-distribution learning is computationally hard, even when ERM is computationally efficient. On the positive side, we identify a structural condition enabling an efficient black-box reduction, converting existing randomized multi-distribution predictors into deterministic ones.

Authors: Mario Grobler, Stephanie Maaz, Amer E. Mouawad, Naomi Nishimura, Vijayaragunathan Ramamoorthi, Sebastian Siebertz

In the solution discovery variant of a vertex (edge) subset problem $\Pi$ on graphs, we are given an initial configuration of tokens on the vertices (edges) of an input graph $G$ together with a budget $b$. The question is whether we can transform this configuration into a feasible solution of $\Pi$ on $G$ with at most $b$ modification steps. We consider the token sliding variant of the solution discovery framework, where each modification step consists of sliding a token to an adjacent vertex (edge). The framework of solution discovery was recently introduced by Fellows et al. [Fellows et al., ECAI 2023] and for many solution discovery problems the classical as well as the parameterized complexity has been established. In this work, we study the kernelization complexity of the solution discovery variants of Vertex Cover, Independent Set, Dominating Set, Shortest Path, Matching, and Vertex Cut with respect to the parameters number of tokens $k$, discovery budget $b$, as well as structural parameters such as pathwidth.

Authors: Junhao Gan, Seeun William Umboh, Hanzhi Wang, Anthony Wirth, Zhuo Zhang

In this paper, we study the Dynamic Parameterized Subset Sampling (DPSS) problem in the Word RAM model. In DPSS, the input is a set,~$S$, of~$n$ items, where each item,~$x$, has a non-negative integer weight,~$w(x)$. Given a pair of query parameters, $(\alpha, \beta)$, each of which is a non-negative rational number, a parameterized subset sampling query on~$S$ seeks to return a subset $T \subseteq S$ such that each item $x \in S$ is selected in~$T$, independently, with probability $p_x(\alpha, \beta) = \min \left\{\frac{w(x)}{\alpha \sum_{x\in S} w(x)+\beta}, 1 \right\}$. More specifically, the DPSS problem is defined in a dynamic setting, where the item set,~$S$, can be updated with insertions of new items or deletions of existing items. Our first main result is an optimal algorithm for solving the DPSS problem, which achieves~$O(n)$ pre-processing time, $O(1+\mu_S(\alpha,\beta))$ expected time for each query parameterized by $(\alpha, \beta)$, given on-the-fly, and $O(1)$ time for each update; here, $\mu_S(\alpha,\beta)$ is the expected size of the query result. At all times, the worst-case space consumption of our algorithm is linear in the current number of items in~$S$. Our second main contribution is a hardness result for the DPSS problem when the item weights are~$O(1)$-word float numbers, rather than integers. Specifically, we reduce Integer Sorting to the deletion-only DPSS problem with float item weights. Our reduction implies that an optimal algorithm for deletion-only DPSS with float item weights (achieving all the same bounds as aforementioned) implies an optimal algorithm for Integer Sorting. The latter remains an important open problem. Last but not least, a key technical ingredient for our first main result is an efficient algorithm for generating Truncated Geometric random variates in $O(1)$ expected time in the Word RAM model.

Authors: Claire Mathieu, William Thurston

Splay trees are a simple and efficient dynamic data structure, invented by Sleator and Tarjan. The basic primitive for transforming a binary tree in this scheme is a rotation. Sleator, Tarjan, and Thurston proved that the maximum rotation distance between trees with n internal nodes is exactly 2n-6 for trees with n internal nodes (where n is larger than some constant). The proof of the upper bound is easy but the proof of the lower bound, remarkably, uses sophisticated arguments based on calculating hyperbolic volumes. We give an elementary proof of the same result. The main interest of the paper lies in the method, which is new. It basically relies on a potential function argument, similar to many amortized analyses. However, the potential of a tree is not defined explicitly, but by constructing an instance of a flow problem and using the max-flow min-cut theorem.

Authors: Koustav Bhanja

Let $G=(V,E)$ be an undirected weighted graph on $n=|V|$ vertices and $S\subseteq V$ be a Steiner set. Steiner mincut is a well-studied concept, which provides a generalization to both (s,t)-mincut (when $|S|=2$) and global mincut (when $|S|=n$). Here, we address the problem of designing a compact data structure that can efficiently report a Steiner mincut and its capacity after the failure of any edge in $G$; such a data structure is known as a \textit{Sensitivity Oracle} for Steiner mincut. In the area of minimum cuts, although many Sensitivity Oracles have been designed in unweighted graphs, however, in weighted graphs, Sensitivity Oracles exist only for (s,t)-mincut [Annals of Operations Research 1991, NETWORKS 2019, ICALP 2024], which is just a special case of Steiner mincut. Here, we generalize this result to any arbitrary set $S\subseteq V$. 1. Sensitivity Oracle: Assuming the capacity of every edge is known, a. there is an ${\mathcal O}(n)$ space data structure that can report the capacity of Steiner mincut in ${\mathcal O}(1)$ time and b. there is an ${\mathcal O}(n(n-|S|+1))$ space data structure that can report a Steiner mincut in ${\mathcal O}(n)$ time after the failure of any edge in $G$. 2. Lower Bound: We show that any data structure that, after the failure of any edge, can report a Steiner mincut or its capacity must occupy $\Omega(n^2)$ bits of space in the worst case, irrespective of the size of the Steiner set. The lower bound in (2) shows that the assumption in (1) is essential to break the $\Omega(n^2)$ lower bound on space. For $|S|=n-k$ for any constant $k\ge 0$, it occupies only ${\mathcal O}(n)$ space. So, we also present the first Sensitivity Oracle occupying ${\mathcal O}(n)$ space for global mincut.

Authors: Sofya Raskhodnikova, Teresa Anna Steiner

We study differentially private algorithms for analyzing graphs in the challenging setting of continual release with fully dynamic updates, where edges are inserted and deleted over time, and the algorithm is required to update the solution at every time step. Previous work has presented differentially private algorithms for many graph problems that can handle insertions only or deletions only (called partially dynamic algorithms) and obtained some hardness results for the fully dynamic setting. The only algorithms in the latter setting were for the edge count, given by Fichtenberger, Henzinger, and Ost (ESA 21), and for releasing the values of all graph cuts, given by Fichtenberger, Henzinger, and Upadhyay (ICML 23). We provide the first differentially private and fully dynamic graph algorithms for several other fundamental graph statistics (including the triangle count, the number of connected components, the size of the maximum matching, and the degree histogram), analyze their error and show strong lower bounds on the error for all algorithms in this setting. We study two variants of edge differential privacy for fully dynamic graph algorithms: event-level and item-level. We give upper and lower bounds on the error of both event-level and item-level fully dynamic algorithms for several fundamental graph problems. No fully dynamic algorithms that are private at the item-level (the more stringent of the two notions) were known before. In the case of item-level privacy, for several problems, our algorithms match our lower bounds.

Authors: Harsha Vardhan Simhadri, Martin Aumüller, Amir Ingber, Matthijs Douze, George Williams, Magdalen Dobson Manohar, Dmitry Baranchuk, Edo Liberty, Frank Liu, Ben Landrum, Mazin Karjikar, Laxman Dhulipala, Meng Chen, Yue Chen, Rui Ma, Kai Zhang, Yuzheng Cai, Jiayang Shi, Yizhuo Chen, Weiguo Zheng, Zihao Wan, Jie Yin, Ben Huang

The 2023 Big ANN Challenge, held at NeurIPS 2023, focused on advancing the state-of-the-art in indexing data structures and search algorithms for practical variants of Approximate Nearest Neighbor (ANN) search that reflect the growing complexity and diversity of workloads. Unlike prior challenges that emphasized scaling up classical ANN search ~\cite{DBLP:conf/nips/SimhadriWADBBCH21}, this competition addressed filtered search, out-of-distribution data, sparse and streaming variants of ANNS. Participants developed and submitted innovative solutions that were evaluated on new standard datasets with constrained computational resources. The results showcased significant improvements in search accuracy and efficiency over industry-standard baselines, with notable contributions from both academic and industrial teams. This paper summarizes the competition tracks, datasets, evaluation metrics, and the innovative approaches of the top-performing submissions, providing insights into the current advancements and future directions in the field of approximate nearest neighbor search.

Authors: Pierre Bourhis, Florent Capelli, Stefan Mengel, Cristian Riveros

We study the problem of evaluating a Monadic Second Order (MSO) query over strings under updates in the setting of direct access. We present an algorithm that, given an MSO query with first-order free variables represented by an unambiguous variable-set automaton $\mathcal{A}$ with state set $Q$ and variables $X$ and a string $s$, computes a data structure in time $\mathcal{O}(|Q|^\omega\cdot |X|^2 \cdot |s|)$ and, then, given an index $i$ retrieves, using the data structure, the $i$-th output of the evaluation of $\mathcal{A}$ over $s$ in time $\mathcal{O}(|Q|^\omega \cdot |X|^3 \cdot \log(|s|)^2)$ where $\omega$ is the exponent for matrix multiplication. Ours is the first efficient direct access algorithm for MSO query evaluation over strings; such algorithms so far had only been studied for first-order queries and conjunctive queries over relational data. Our algorithm gives the answers in lexicographic order where, in contrast to the setting of conjunctive queries, the order between variables can be freely chosen by the user without degrading the runtime. Moreover, our data structure can be updated efficiently after changes to the input string, allowing more powerful updates than in the enumeration literature, e.g.~efficient deletion of substrings, concatenation and splitting of strings, and cut-and-paste operations. Our approach combines a matrix representation of MSO queries and a novel data structure for dynamic word problems over semi-groups which yields an overall algorithm that is elegant and easy to formulate.

I often do LeetCode problems for fun. This site mainly provides short coding problems for students and others to train for the kinds of question that come up in technical job interviews. I use the site to keep up my programming skills and it often requires clever algorithms and data structures. The Daily Question is like a Wordle for recreational programmers. Try this problem which asks you to create a data structure for sets with insert, delete and get-random-element operations in expected constant amortized time.

I have to turn off GitHub Co-pilot, otherwise it will give you the solution before you even finish typing the function name. There are so many solutions to these problems out there and in the training sets for LLMs.

A student asked me last week why he should do LeetCode problems if AI can solve them all. I responded that doing the problems (and CS homework more importantly) give you the skills to understand code and algorithms and in your future jobs you'll encounter problems AI may not solve fully, or correctly, or efficiently and having those skills will allow you to solve those kinds of problems AI alone can't tackle.

But is this the right answer as AI continues to improve? Ideally we want to create students who transcend AI instead of being replaced by it. For that they need to fully understand programming and computing and be smart enough to know when and when not to outsource that skill to AI. That's the challenge for CS departments: teaching students how to use AI to make themselves better computer scientists without relying on it. It's a hard balance in a technology where we can't predict AI's capabilities at the time these students graduate.

By Lance Fortnow

This is the live blog of Lecture 9 of my graduate class “Convex Optimization.” A Table of Contents is here.

Duality theory in optimization is deep, beautiful, and mysterious. For every minimization problem, we can construct a convex maximization problem whose optimal value is less than or equal to the optimal value of the minimization problem. The minimization problem is called the primal problem because it’s the one we primarily care about. The maximization problem is called the dual problem, and it helps us reason about the primal problem. 

Lower bounds are useful: if you have a point that you think is optimal for the primal problem and a potential solution for the dual problem with the same objective value, you have found a solution for both the primal problem and the dual problem.  In fact, we’ll show that any feasible point for the minimization problem will have an objective value larger than any feasible point for the new maximization problem. And even if your primal problem is nonconvex, the dual problem is always convex, so it can provide insights into what might be achievable with your intractable primal problem.

Duality theory also gives us insights into the robustness of solutions to specification and the sensitivity of different modeling assumptions. It inspires algorithmic strategies for solving both convex and nonconvex problems. It’s a powerful theoretical and applied tool and is essential to understand if you want to be a practicing optimizer.

And yet, I’ve been struggling all morning to figure out how to introduce the topic without it seeming magical. There are different paths to introduce it, and all of them feel weird and confusing. Boyd and Vandenberge jump right in with a Lagrangian function, but where did Lagrange come up with those ideas of Lagrange multipliers? It takes some work to motivate this! Some people start with abstract convex geometry, relating graphs of optimization problems and their characterization in terms of separating hyperplanes. I love this derivation, but it takes me an hour of confusion to remember how to explain it (apologies to Dimitri Bertsekas). The final introduction, which parallels the historical origin of optimization duality, is through minimax theory. But, again, minimax theorems are also mysterious.

Well, let me try to go through the minimax theorem because it did really start this whole thing rolling. I’ll introduce it the same way von Neumann discovered it: in terms of a game. The game has two players, Player One and Player Two. Player One and Player Two have a known joint function F(x,y). Player One wants to choose x from a set X to make F as large as possible. Player Two wants to choose y from a set Y to make F as small as possible. At the end of the game, Player 1 gets F(x,y) points, and Player Two gets -F(x,y) points. Does it matter who plays first?

If Player One goes first and plays x1, then Player Two will minimize with respect to their available choices. That is, Player Two chooses y to achieve a payout

Therefore, to anticipate this move by Player Two, Player One should pick the x that maximizes this infimum. Player One’s best strategy yields a final payout of

From the same analysis, if Player Two chooses first, then the final score is

Should Player One opt to go first or second? How does a maximum of a minimum compare to a minimum of a maximum? The following nearly tautological analysis shows that Player One should always choose to go second.

Take any function F(x,y) and any sets X and Y. Then for a fixed x0 and y0,

Now, this means that if you take the supremum of both sides, this inequality is valid

Since this holds for all values of y0, we have

That is, minimums of maximums are always greater than maximums of minimums.

In 1928, John von Neumann realized that they were often equal. In this game, suppose the players choose their moves at random. Even if players declare their strategies in advance (each player declares their sampling distribution), there is no advantage to the order. In math, if X and Y are both probability simplexes, von Neumann proved that

If players play these random strategies, they can even tell their opponent in advance what their strategy is and still be optimal. 

Von Neumann derived this in studying parlor games, but its impact has been felt far beyond game theory. In fact, if X is a convex compact set and Y is convex, then the minimax theorem is still true. The min max equals the max min. 

What does this have to do with optimization? In class today, I’ll show how to write minimization problems as a min max. The dual problem will then be the associated problem when we switch the order of minimum and maximum. Like I said, it’s mysterious. I’ll write back tomorrow to report on how it went.

Subscribe now

By Ben Recht

Today is the day I became radicalized in my Jewish and Zionist identities.

Uhhh, you thought that had already happened? Like maybe in the aftermath of October 7, or well before then? Hahahaha no. You haven’t seen nothin’ yet.

See, a couple days ago, I was consoling myself on Facebook that, even as the arts and humanities and helping professions appeared to have fully descended into 1930s-style antisemitism, with “Zionists” (i.e., almost all Jews) now regularly getting disinvited from conferences and panels, singled out for condemnation by their teachers, placed on professional blacklists, etc. etc.—still, at least we in math, CS, and physics have mostly resisted these insanities. This was my way of trying to contain the damage. Sure, I told myself, all sorts of walks of life that had long been loony got even loonier, but at least it won’t directly affect me, here in my little bubble of polynomial-time algorithms and lemmas and chalk and LaTeX and collegiality and sanity.

So immediately afterward, as if overhearing, the International Olympiad on Informatics announced that, by a vote of more than two-thirds of its delegates, it’s banning the State of Israel from future competition. For context, the IOI is the world’s main high-school programming contest. I once dreamed of competing in the IOI, but then I left high school at age 15, which is totally the reason why I didn’t make it. Incredibly, despite its tiny size, Israel placed #2 in this month’s contest, which was held in Egypt. (The Israeli teenagers had to compete remotely, since Egypt could not guarantee their safety.)

Anyway, apparently the argument that carried the day at IOI was that, since Russia had previously been banned, it was only fair to ban Israel too. Is it even worth pointing out that Russia launched a war of conquest and annihilation against a neighbor, while Israel has been defending itself from such a war launched by its neighbors? I.e., that Israel is the “Ukraine” here, not the “Russia”? Do you even have to ask whether Syria, Iran, Saudi Arabia, or China were also banned? Will it change anyone’s mind that, if we read Israel’s enemies in their own words—as I do, every day—they constantly tell us that, in their view, Israel’s fundamental “aggression” was not building settlements or demolishing houses or rigging pagers, but simply existing? (“We don’t want no two states!,” they explain. “We want all of ’48,” they explain.)

Surely, then, the anti-Zionists, the ones who rush to assure us they’re definitely not antisemites, must have some plan for what will happen to half the world’s remaining Jews after the little Zionist lifeboat is gone, after the new river-to-the-sea state of Palestine has expelled the hated settler-colonialists? Surely the plan won’t just be to ship the Jews back to the countries that murdered or expelled their grandparents, most of which have never offered to take them back? Surely the plan won’t be the same plan from last time—i.e., the plan that the Palestinian leadership enthusiastically supported the last time, the plan that it yearned to bring to Tel Aviv and Haifa, the plan called (where it was successfully carried out) by such euphemisms as Umsiedlung nach dem Osten and Endlösung der Judenfrage?

I feel like there must be sane answers to these questions, because if there aren’t, then too many people around the globe have covered themselves in a kind of shame that I thought had died a generation before I was born. And, like, these are people who consider themselves the paragons of enlightened morality: weeping for the oppressed, marching for LGBTQ+, standing on the right side of history. They organize literary festivals and art shows and (god help me) even high-school programming contests. They couldn’t also be monsters full of hatred, could they? Even though, the last time the question was tested, they totally were?

Let me add, in fairness: four Israeli high-school students will still be suffered to compete in the IOI, “but only as individuals.” To my mind, then, the right play for those students is to show up next year, do as well as they did this year, and then disqualify themselves by raising an Israeli flag in front of the cameras. Let them honor the legacy of Israel’s Olympic athletes, who kept showing up to compete (and eventually, to win medals) even after the International Olympic Committee had made clear that it would not protect them from being massacred mid-event. Let them exemplify what Mark Twain famously said of “the Jew,” that “he has made a marvellous fight in this world, in all the ages; and has done it with his hands tied behind him.”

But why do I keep abusing your time with this, when you came to hear about quantum computing or AI safety? I’ll get back to those soon enough. But truthfully, if speaking clearly about the darkness now re-enveloping civilization demanded it, I’d willingly lose every single non-Jewish friend I had, and most of my Jewish friends too. I’d completely isolate myself academically, professionally, and socially. I’d give up 99% of the readership of this blog. Better that than to look in the mirror and see a coward, a careerist, a kapo.

I thank the fates or the Born Rule, then, that I won’t need to do any of that. I’ve lived my life surrounded by friends and colleagues from Alabama and Alaska, China and India, Brazil and Iran, of every race and religion and sexual orientation and programming indentation style. Some of my Gentile friends 300% support me on this issue. Most of the rest are willing to hear me out, which is enough for friendship. If I can call the IOI’s Judenboykott what it is while keeping more than half of my readers, colleagues, and friends—that’s not even much of a decision, is it?

---

Important Update (September 26): Jonathan Mosheiff, of Israeli’s IOI delegation, got in touch with me and gave me permission to share the document below, which in my view shows that the anti-Israel animus at IOI goes much deeper than I realized, and that the process taken to remove Israel was fundamentally corrupt and in violation of the IOI’s own promises. –SA

---

I served as the Israeli team leader at the International Olympiad in Informatics (IOI) from 2011 to 2015, and since then, I have maintained an unofficial advisory role to the team. Currently, I am an Assistant Professor in the Computer Science department at Ben-Gurion University.

There are two key issues that need to be addressed:

Israel’s Participation in IOI 2024

At IOI 2023, the Israeli delegation was informed by the Egyptian delegation that Israel would not be able to attend IOI 2024 as an official delegation under the Israeli flag. Instead, Israel could participate under a neutral “IOI flag,” similar to how Russia participated in the 2021 Olympic Games in Tokyo. The Egyptians cited security concerns as the reason for this restriction, a claim that is highly questionable. The Israeli delegation inquired whether, after the IOI concluded, the official IOI scoreboard would reflect Israel’s representation under the Israeli flag rather than a neutral one. The Egyptian organizers responded that they would be unable to make this change, without providing any justification. This clearly undermines the credibility of their security-related reasoning.

In March 2024, Ben Burton, the IOI President from Australia, officially notified Israel that it would not be invited to participate in IOI 2024, not even under a neutral flag. This decision directly contravenes IOI rules, which mandate that the host nation must invite all IOI member countries. It’s important to differentiate between two scenarios: In some cases, a host country may invite another nation, but that nation cannot attend due to visa issues. However, this was not the situation here. Egypt did not issue Israel a letter of invitation and ignored Israel’s attempts at communication. To my knowledge, this is only the second instance in IOI history where a host nation failed to invite another nation—the first being Iran’s refusal to invite Israel when it hosted IOI 2017.

The IOI International Committee (the executive branch of the IOI) has not provided any explanation as to how the host nation could be allowed to act in this manner. They did propose a solution where Israel would participate remotely. Along with Israel, Iran also had to participate remotely due to visa issues, as did one German contestant. However, the treatment of Iran and Israel was vastly different. Iranian contestants (and the one German contestant) were acknowledged in all official on-site IOI publications and were recognized at both the opening and closing ceremonies. In contrast, Israel was completely ignored and went unrecognized throughout IOI 2024. The Israeli contestants were only “retroactively added” to the competition by the International Committee after IOI 2024 had concluded. Even now, our contestants cannot obtain official placement certificates, as the host nation deleted them from the competition servers. As far as I am aware, no other country in IOI history has been treated this way.

The Vote to Sanction Israel

In March 2024, the IOI President issued a brief statement indicating that there were requests to sanction Israel and that an email would be sent to all participating nations to gather their opinions. On August 3rd, 2024, a second email was sent, requesting that opinions be submitted directly to the International Committee rather than through a public discussion. In this email, Israel was already being compared to Russia. Israel submitted a position letter and requested that it be shared with all member nations, but the International Committee declined to disseminate Israel’s position. The IOI President assured Israel that, should a vote on sanctions be held during IOI 2024, Israel would be allowed to participate in the discussion remotely and have its voice heard. On August 16th, the International Committee announced that such a vote would indeed take place, and that Israel would be included in both the discussion and the vote.

IOI 2024 began on September 1st, 2024. At that time, the Israeli delegation was informed that they would not be allowed to participate in the discussion, even remotely. Israel was permitted to submit a written statement, which would be made available for all team leaders to download, but it was never read aloud during any discussions. The reason given was that Israel had been effectively erased from IOI 2024 by the hosts, and the International Committee acquiesced to this. Meanwhile, the Egyptian and Palestinian delegations were actively lobbying for votes throughout the week of IOI 2024. The discussion and vote on sanctions took place on the final day of IOI 2024 during a meeting of the General Assembly (the legislative branch of the IOI, where each nation has one vote). Israel was not even permitted to listen to the discussion (our leaders managed to hear it only because a sympathetic team leader unofficially opened a Zoom channel for them), let alone speak. The discussion itself was problematic in many ways. For instance, it grouped Israel together with Russia and Belarus. Ultimately, a majority voted to sanction Israel, along with Russia and Belarus, which had already been sanctioned previously.

By Scott

Authors: Maxwell West, Antonio Anna Mele, Martin Larocca, M. Cerezo

A unitary state $t$-design is an ensemble of pure quantum states whose moments match up to the $t$-th order those of states uniformly sampled from a $d$-dimensional Hilbert space. Typically, unitary state $t$-designs are obtained by evolving some reference pure state with unitaries from an ensemble that forms a design over the unitary group $\mathbb{U}(d)$, as unitary designs induce state designs. However, in this work we study whether Haar random symplectic states -- i.e., states obtained by evolving some reference state with unitaries sampled according to the Haar measure over $\mathbb{SP}(d/2)$ -- form unitary state $t$-designs. Importantly, we recall that random symplectic unitaries fail to be unitary designs for $t>1$, and that, while it is known that symplectic unitaries are universal, this does not imply that their Haar measure leads to a state design. Notably, our main result states that Haar random symplectic states form unitary $t$-designs for all $t$, meaning that their distribution is unconditionally indistinguishable from that of unitary Haar random states, even with tests that use infinite copies of each state. As such, our work showcases the intriguing possibility of creating state $t$-designs using ensembles of unitaries which do not constitute designs over $\mathbb{U}(d)$ themselves, such as ensembles that form $t$-designs over $\mathbb{SP}(d/2)$.

Authors: John Mackey, Bernardo Subercaseaux

Erd\H{o}s and Guy initiated a line of research studying $\mu_k(n)$, the minimum number of convex $k$-gons one can obtain by placing $n$ points in the plane without any three of them being collinear. Asymptotically, the limits $c_k := \lim_{n\to \infty} \mu_k(n)/\binom{n}{k}$ exist for all $k$, and are strictly positive due to the Erd\H{o}s-Szekeres theorem. This article focuses on the case $k=5$, where $c_5$ was known to be between $0.0608516$ and $0.0625$ (Goaoc et al., 2018; Subercaseaux et al., 2023). The lower bound was obtained through the Flag Algebra method of Razborov using semi-definite programming. In this article we prove a more modest lower bound of $\frac{5\sqrt{5}-11}{4} \approx 0.04508$ without any computation; we exploit``planar-point equations'' that count, in different ways, the number of convex pentagons (or other geometric objects) in a point placement. To derive our lower bound we combine such equations by viewing them from a statistical perspective, which we believe can be fruitful for other related problems.

Authors: Tilo Strutz, Nico Schreiber

There is a class of entropy-coding methods which do not substitute symbols by code words (such as Huffman coding), but operate on intervals or ranges. This class includes three prominent members: conventional arithmetic coding, range coding, and coding based on asymmetric numeral systems. To determine the correct symbol in the decoder, each of these methods requires the comparison of a state variable with subinterval boundaries. In adaptive operation, considering varying symbol statistics, an array of interval boundaries must additionally be kept up to date. The larger the symbol alphabet, the more time-consuming both the search for the correct subinterval and the updating of interval borders become. Detailed pseudo-code is used to discuss different approaches to speed up the symbol search in the decoder and the adaptation of the array of interval borders, both depending on the chosen alphabet size. It is shown that reducing the $\mathcal{O}$-complexity does not lead to an acceleration in practical implementations if the alphabet size is too small. In adaptive compression mode, the binary indexing method proves to be superior when considering the overall processing time. Although the symbol search (in the decoder) takes longer than with other algorithms, the faster updating of the array of interval borders more than compensates for this disadvantage. A variant of the binary indexing method is proposed, which is more flexible and has a partially lower complexity than the original approach.

Authors: Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya

We propose an algorithm for counting the number of cycles under local differential privacy for degeneracy-bounded input graphs. Numerous studies have focused on counting the number of triangles under the privacy notion, demonstrating that the expected \(\ell_2\)-error of these algorithms is \(\Omega(n^{1.5})\), where \(n\) is the number of nodes in the graph. When parameterized by the number of cycles of length four (\(C_4\)), the best existing triangle counting algorithm has an error of \(O(n^{1.5} + \sqrt{C_4}) = O(n^2)\). In this paper, we introduce an algorithm with an expected \(\ell_2\)-error of \(O(\delta^{1.5} n^{0.5} + \delta^{0.5} d_{\max}^{0.5} n^{0.5})\), where \(\delta\) is the degeneracy and \(d_{\max}\) is the maximum degree of the graph. For degeneracy-bounded graphs (\(\delta \in \Theta(1)\)) commonly found in practical social networks, our algorithm achieves an expected \(\ell_2\)-error of \(O(d_{\max}^{0.5} n^{0.5}) = O(n)\). Our algorithm's core idea is a precise count of triangles following a preprocessing step that approximately sorts the degree of all nodes. This approach can be extended to approximate the number of cycles of length \(k\), maintaining a similar \(\ell_2\)-error, namely $O(\delta^{(k-2)/2} d_{\max}^{0.5} n^{(k-2)/2} + \delta^{k/2} n^{(k-2)/2})$ or $O(d_{\max}^{0.5} n^{(k-2)/2}) = O(n^{(k-1)/2})$ for degeneracy-bounded graphs.

Authors: Sankardeep Chakraborty, Seungbum Jo, Geunho Kim, Kunihiko Sadakane

A permutation $\pi: [n] \rightarrow [n]$ is a Baxter permutation if and only if it does not contain either of the patterns $2-41-3$ and $3-14-2$. Baxter permutations are one of the most widely studied subclasses of general permutation due to their connections with various combinatorial objects such as plane bipolar orientations and mosaic floorplans, etc. In this paper, we introduce a novel succinct representation (i.e., using $o(n)$ additional bits from their information-theoretical lower bounds) for Baxter permutations of size $n$ that supports $\pi(i)$ and $\pi^{-1}(j)$ queries for any $i \in [n]$ in $O(f_1(n))$ and $O(f_2(n))$ time, respectively. Here, $f_1(n)$ and $f_2(n)$ are arbitrary increasing functions that satisfy the conditions $\omega(\log n)$ and $\omega(\log^2 n)$, respectively. This stands out as the first succinct representation with sub-linear worst-case query times for Baxter permutations. Additionally, we consider a subclass of Baxter permutations called \textit{separable permutations}, which do not contain either of the patterns $2-4-1-3$ and $3-1-4-2$. In this paper, we provide the first succinct representation of the separable permutation $\rho: [n] \rightarrow [n]$ of size $n$ that supports both $\rho(i)$ and $\rho^{-1}(j)$ queries in $O(1)$ time. In particular, this result circumvents Golynski's [SODA 2009] lower bound result for trade-offs between redundancy and $\rho(i)$ and $\rho^{-1}(j)$ queries. Moreover, as applications of these permutations with the queries, we also introduce the first succinct representations for mosaic/slicing floorplans, and plane bipolar orientations, which can further support specific navigational queries on them efficiently.

A polygonalization of a set of points in the plane is a non-self-crossing polygon using all the points as vertices. One way to prove that it always exists is to observe that the traveling salesperson tour is always a polygonalization, because any two crossed edges can be uncrossed in two different ways, one of which preserves the connectivity of the tour, and this cannot increase the tour length. So if minimizing tour length eliminates all crossings, surely maximizing tour length must introduce as many crossings as possible, right?

This is the subject of a recent paper by ten authors including myself: “Noncrossing longest paths and cycles”, by Greg Aloupis, Ahmad Biniaz, Jit Bose, Jean-Lou De Carufel, me, Anil Maheshwari, Saeed Odak, Michiel Smid, Csaba Tóth, and Pavel Valtr, most of whom worked together on this at the 10th Annual Workshop on Geometry and Graphs in Barbados last year. It was presented last week at Graph Drawing 2024, for which the program has links to preliminary versions of all papers, at least until the published proceedings is ready.

Three points, or four points in non-convex position, have no crossings, but for larger numbers of points in general position a crossing is always possible. In a recent paper in Graphs and Combinatorics, Jose Luis Álvarez-Rebollar, Jorge Cravioto-Lagos, Nestaly Marín, Oriol Andreu Solé-Pi, and Jorge Urrutia conjectured that sets of five or more points in general position always have crossings in their longest cycles (maximum traveling salesperson tours) and asked whether they also have crossings in their longest paths (maximum traveling salesperson paths). Our new work provides strong counterexamples to both questions: for all \(n\), there exist sets of \(n\) points in general position in the plane with a non-crossing longest cycle, and sets of \(n\) points with a non-crossing longest path.

The path construction for even numbers of points is simplest. Its basic ideas are:

• All points will be placed close to the \(x\)-axis, with \(x\)-coordinate much larger than \(y\), so that the differences in \(x\)-coordinate dominate their distances.

• If the \(y\)-coordinates are zero, and the points are placed with half of their \(x\)-coordinates positive and half negative, then the (many) equally longest paths all start and end at the two middle points, with their edges all crossing the \(y\)-axis. Edges that do not cross the axis can be paired off on both sides of the axis and replaced by longer pairs of edges that cross. Among paths where all edges cross the axis, the total length is the sum of distances to the axis, doubled for non-endpoints, so the endpoints should be the two middle points.

• We can use equally spaced \(x\)-coordinates, half positive and half negative, perturbed by very small \(y\)-coordinates. The longest path will continue to have all edges crossing the \(y\)-axis, but the perturbation will force one such path to be longest. (The construction for an odd number of points uses a slightly uneven placement that is not important for this post.)

• When we perturb two points, the length of their edge increases (compared to its length with zero \(y\)-coordinates) by an amount that can be calculated by the Pythagorean theorem to be

  \[\frac{\Delta_y^2}{2\Delta_x}\bigl(1+o(1)\bigr),\]

  where \(\Delta_x\) and \(\Delta_y\) are the differences in \(x\)- and \(y\)-coordinates, assuming \(\Delta_x\gg\Delta_y\).

• Our perturbation will assign exponentially increasing \(y\)-coordinates to the points, with the largest perturbations going to the points closest to the \(x\)-axis, except for leaving one of the two middle points unperturbed.

• Because of this exponential growth, the terms \(\Delta_y\) in the length increase are up to a small error term the same as the \(y\)-coordinates themselves, regardless of the choice of path. But different paths can pair up different \(\Delta_y\) terms with different \(\Delta_x\) terms. To get the longest path, we should pair up the largest \(\Delta_y\) term (coming from the edge incident to the highest point) with the smallest \(\Delta_x\) term (coming from the non-middle vertex closest to the other side of the \(x\)-axis), and continue greedily choosing edges that at each step pair the highest remaining vertex with the non-middle vertex closest to the other side of the axis.

• The resulting unique longest path is uncrossed! Each edge connects two vertices that are consecutive when sorted by their \(y\)-coordinates. Because the edges span disjoint ranges of \(y\), they cannot cross. In a not-to-scale view with untuned parameters, it looks something like the following.

To construct uncrossed longest paths with odd numbers of points we choose \(x\)-coordinates a little more carefully, and then merely omit the topmost point. The cycle construction uses a similar idea, but in two variations depending on whether the number of points is supposed to be odd or even. For evenly many points we double each point except the first and last in the non-crossing path path and carefully place its two copies so that a thin polygon can zigzag in the same way as the path. For odd points we find a polygon that adds one vertex and two edges to the long path to connect it into a polygon. See the paper for details.

(Discuss on Mastodon)

By David Eppstein

Classical data can be copied and re-used for computation, with adverse consequences economically and in terms of data privacy. Motivated by this, we formulate problems in one-way communication complexity where Alice holds some data and Bob holds $m$ inputs, and he wants to compute $m$ instances of a bipartite relation on Alice's data and each of his inputs. We call this the asymmetric direct sum question for one-way communication. We give a number of examples where the quantum communication complexity of such problems scales polynomially with $m$, while the classical communication complexity depends at most logarithmically on $m$. For these examples, data behaves like a consumable resource when the owner stores and transmits it as quantum states. We show an application to a strategic data-selling game, and discuss other potential economic implications.

We initiate a study of doubly-efficient interactive proofs of proximity, while focusing on properties that can be tested within query-complexity that is significantly sub-linear, and seeking interactive proofs of proximity in which 1. The query-complexity of verification is significantly smaller than the query-complexity of testing. 2. The query-complexity of the honest prover strategy is not much larger than the query-complexity of testing. We call such proof systems doubly-sublinear IPPs (dsIPPs). We present a few doubly-sublinear IPPs. A salient feature of these IPPs is that the honest prover does not employ an optimal strategy. In particular, the honest prover in our IPP for sets recognizable by constant-width read-once oblivious branching programs uses a distance-approximator for such sets.

Authors: Philippe L. Toint

The adaptive regularization algorithm for unconstrained nonconvex optimization was shown in Nesterov and Polyak (2006) and Cartis, Gould and Toint (2011) to require, under standard assumptions, at most $\mathcal{O}(\epsilon^{3/(3-q)})$ evaluations of the objective function and its derivatives of degrees one and two to produce an $\epsilon$-approximate critical point of order $q\in\{1,2\}$. This bound was shown to be sharp for $q \in\{1,2\}$. This note revisits these results and shows that the example for which slow convergence is exhibited is not isolated, but that this behaviour occurs for a subset of univariate functions of nonzero measure.

Authors: Ruiquan Gao, Mohammad Roghani, Aviad Rubinstein, Amin Saberi

Given a so called ''Sperner coloring'' of a triangulation of the $D$-dimensional simplex, Sperner's lemma guarantees the existence of a rainbow simplex, i.e. a simplex colored by all $D+1$ colors. However, finding a rainbow simplex was the first problem to be proven $\mathsf{PPAD}$-complete in Papadimitriou's classical paper introducing the class $\mathsf{PPAD}$ (1994). In this paper, we prove that the problem does not become easier if we relax ''all $D+1$ colors'' to allow some fraction of missing colors: in fact, for any constant $D$, finding even a simplex with just three colors remains $\mathsf{PPAD}$-complete! Our result has an interesting application for the envy-free cake cutting from fair division. It is known that if agents value pieces of cake using general continuous functions satisfying a simple boundary condition (''a non-empty piece is better than an empty piece of cake''), there exists an envy-free allocation with connected pieces. We show that for any constant number of agents it is $\mathsf{PPAD}$-complete to find an allocation -- even using any constant number of possibly disconnected pieces -- that makes just three agents envy-free. Our results extend to super-constant dimension, number of agents, and number of pieces, as long as they are asymptotically bounded by any $\log^{1-\Omega(1)}(\epsilon)$, where $\epsilon$ is the precision parameter (side length for Sperner and approximate envy-free for cake cutting).

Authors: Vedangi Bengali, Nate Veldt

A minimum $s$-$t$ cut in a hypergraph is a bipartition of vertices that separates two nodes $s$ and $t$ while minimizing a hypergraph cut function. The cardinality-based hypergraph cut function assigns a cut penalty to each hyperedge based on the number of nodes in the hyperedge that are on each side of the split. Previous work has shown that when hyperedge cut penalties are submodular, this problem can be reduced to a graph $s$-$t$ cut problem and hence solved in polynomial time. NP-hardness results are also known for a certain class of non-submodular penalties, though the complexity remained open in many parameter regimes. In this paper we highlight and leverage a connection to Valued Constraint Satisfaction Problems to show that the problem is NP-hard for all non-submodular hyperedge cut penalty, except for one trivial case where a 0-cost solution is always possible. We then turn our attention to approximation strategies and approximation hardness results in the non-submodular case. We design a strategy for projecting non-submodular penalties to the submodular region, which we prove gives the optimal approximation among all such projection strategies. We also show that alternative approaches are unlikely to provide improved guarantees, by showing it is UGC-hard to obtain a better approximation in the simplest setting where all hyperedges have exactly 4 nodes.

Authors: Bingbing Hu, Adam Polak

Most of the known tight lower bounds for dynamic problems are based on the Online Boolean Matrix-Vector Multiplication (OMv) Hypothesis, which is not as well studied and understood as some more popular hypotheses in fine-grained complexity. It would be desirable to base hardness of dynamic problems on a more believable hypothesis. We propose analogues of the OMv Hypothesis for variants of matrix multiplication that are known to be harder than Boolean product in the offline setting, namely: equality, dominance, min-witness, min-max, and bounded monotone min-plus products. These hypotheses are a priori weaker assumptions than the standard (Boolean) OMv Hypothesis. Somewhat surprisingly, we show that they are actually equivalent to it. This establishes the first such fine-grained equivalence class for dynamic problems.

Authors: Andrej Bogdanov, Chris Jones, Alon Rosen, Ilias Zadik

The planted random subgraph detection conjecture of Abram et al. (TCC 2023) asserts the pseudorandomness of a pair of graphs $(H, G)$, where $G$ is an Erdos-Renyi random graph on $n$ vertices, and $H$ is a random induced subgraph of $G$ on $k$ vertices. Assuming the hardness of distinguishing these two distributions (with two leaked vertices), Abram et al. construct communication-efficient, computationally secure (1) 2-party private simultaneous messages (PSM) and (2) secret sharing for forbidden graph structures. We prove the low-degree hardness of detecting planted random subgraphs all the way up to $k\leq n^{1 - \Omega(1)}$. This improves over Abram et al.'s analysis for $k \leq n^{1/2 - \Omega(1)}$. The hardness extends to $r$-uniform hypergraphs for constant $r$. Our analysis is tight in the distinguisher's degree, its advantage, and in the number of leaked vertices. Extending the constructions of Abram et al, we apply the conjecture towards (1) communication-optimal multiparty PSM protocols for random functions and (2) bit secret sharing with share size $(1 + \epsilon)\log n$ for any $\epsilon > 0$ in which arbitrary minimal coalitions of up to $r$ parties can reconstruct and secrecy holds against all unqualified subsets of up to $\ell = o(\epsilon \log n)^{1/(r-1)}$ parties.

Authors: Qian Li, Minghui Ouyang, Yuyi Wang

This paper presents a distributed algorithm in the CONGEST model that achieves a $(1+\epsilon)$-approximation for row-sparse fractional covering problems (RS-FCP) and the dual column-sparse fraction packing problems (CS-FPP). Compared with the best-known $(1+\epsilon)$-approximation CONGEST algorithm for RS-FCP/CS-FPP developed by Kuhn, Moscibroda, and Wattenhofer (SODA'06), our algorithm is not only much simpler but also significantly improves the dependency on $\epsilon$.

Authors: Elena Gribelyuk, Honghao Lin, David P. Woodruff, Huacheng Yu, Samson Zhou

The majority of streaming problems are defined and analyzed in a static setting, where the data stream is any worst-case sequence of insertions and deletions that is fixed in advance. However, many real-world applications require a more flexible model, where an adaptive adversary may select future stream elements after observing the previous outputs of the algorithm. Over the last few years, there has been increased interest in proving lower bounds for natural problems in the adaptive streaming model. In this work, we give the first known adaptive attack against linear sketches for the well-studied $\ell_0$-estimation problem over turnstile, integer streams. For any linear streaming algorithm $\mathcal{A}$ that uses sketching matrix $\mathbf{A}\in \mathbb{Z}^{r \times n}$ where $n$ is the size of the universe, this attack makes $\tilde{\mathcal{O}}(r^8)$ queries and succeeds with high constant probability in breaking the sketch. We also give an adaptive attack against linear sketches for the $\ell_0$-estimation problem over finite fields $\mathbb{F}_p$, which requires a smaller number of $\tilde{\mathcal{O}}(r^3)$ queries. Finally, we provide an adaptive attack over $\mathbb{R}^n$ against linear sketches $\mathbf{A} \in \mathbb{R}^{r \times n}$ for $\ell_0$-estimation, in the setting where $\mathbf{A}$ has all nonzero subdeterminants at least $\frac{1}{\textrm{poly}(r)}$. Our results provide an exponential improvement over the previous number of queries known to break an $\ell_0$-estimation sketch.

Authors: Ruben Hoeksma, Gavin Speek, Marc Uetz

We consider the minimum spanning tree problem in a setting where the edge weights are stochastic from unknown distributions, and the only available information is a single sample of each edge's weight distribution. In this setting, we analyze the expected performance of the algorithm that outputs a minimum spanning tree for the sampled weights. We compare to the optimal solution when the distributions are known. For every graph with weights that are exponentially distributed, we show that the sampling based algorithm has a performance guarantee that is equal to the size of the largest bond in the graph. Furthermore, we show that for every graph this performance guarantee is tight. The proof is based on two separate inductive arguments via edge contractions, which can be interpreted as reducing the spanning tree problem to a stochastic item selection problem. We also generalize these results to arbitrary matroids, where the performance guarantee is equal to the size of the largest co-circuit of the matroid.

Authors: Mohsen Ghaffari, Anton Trygub

We present the first (randomized) parallel dynamic algorithm for maximal matching, which can process an arbitrary number of updates simultaneously. Given a batch of edge deletion or insertion updates to the graph, our parallel algorithm adjusts the maximal matching to these updates in $poly(\log n)$ depth and using $poly(\log n)$ amortized work per update. That is, the amortized work for processing a batch of $k$ updates is $kpoly(\log n)$, while all this work is done in $poly(\log n)$ depth, with high probability. This can be seen as a parallel counterpart of the sequential dynamic algorithms for constant-approximate and maximal matching [Onak and Rubinfeld STOC'10; Baswana, Gupta, and Sen FOCS'11; and Solomon FOCS'16]. Our algorithm readily generalizes to maximal matching in hypergraphs of rank $r$ -- where each hyperedge has at most $r$ endpoints -- with a $poly(r)$ increase in work, while retaining the $poly(\log n)$ depth.

Authors: Mohsen Ghaffari, Anton Trygub

We present a low-energy deterministic distributed algorithm that computes exact Single-Source Shortest Paths (SSSP) in near-optimal time: it runs in $\tilde{O}(n)$ rounds and each node is awake during only $poly(\log n)$ rounds. When a node is not awake, it performs no computations or communications and spends no energy. The general approach we take along the way to this result can be viewed as a novel adaptation of Dijkstra's classic approach to SSSP, which makes it suitable for the distributed setting. Notice that Dijkstra's algorithm itself is not efficient in the distributed setting due to its need for repeatedly computing the minimum-distance unvisited node in the entire network. Our adapted approach has other implications, as we outline next. As a step toward the above end-result, we obtain a simple deterministic algorithm for exact SSSP with near-optimal time and message complexities of $\tilde{O}(n)$ and $\tilde{O}(m)$, in which each edge communicates only $poly(\log n)$ messages. Therefore, one can simultaneously run $n$ instances of it for $n$ sources, using a simple random delay scheduling. That computes All Pairs Shortest Paths (APSP) in the near-optimal time complexity of $\tilde{O}(n)$. This algorithm matches the complexity of the recent APSP algorithm of Bernstein and Nanongkai [STOC 2019] using a completely different method (and one that is more modular, in the sense that the SSSPs are solved independently). It also takes a step toward resolving the open problem on a deterministic $\tilde{O}(n)$-time APSP, as the only randomness used now is in the scheduling.

Authors: Thomas Grützmacher, Robert Underwood, Sheng Di, Franck Cappello, Hartwig Anzt

The performance of the GMRES iterative solver on GPUs is limited by the GPU main memory bandwidth. Compressed Basis GMRES outperforms GMRES by storing the Krylov basis in low precision, thereby reducing the memory access. An open question is whether compression techniques that are more sophisticated than casting to low precision can enable large runtime savings while preserving the accuracy of the final results. This paper presents the lightweight in-register compressor FRSZ2 that can decompress at the bandwidth speed of a modern NVIDIA H100 GPU. In an experimental evaluation, we demonstrate using FRSZ2 instead of low precision for compression of the Krylov basis can bring larger runtime benefits without impacting final accuracy.

This is the live blog of Lecture 8 of my graduate class “Convex Optimization.” A Table of Contents is here.

The two central concepts of constrained optimization are feasibility and optimality. A point is feasible if it satisfies all of the constraints. A point is optimal if it is feasible and its objective value is less than or equal to the objective value of all other feasible points. To check if a point is feasible, you evaluate each constraint and verify that it holds. This is almost always a straightforward numerical procedure based on a few primitives (e.g., Is some function less than zero? Is the vector nonnegative? Is a matrix positive semidefinite?).

Checking optimality is trickier because of the associated logic. Feasibility is a “there exists” problem. You can check feasibility by plugging in values to an appropriate formula. Optimality is a “for all” problem. 

Feasibility:

Optimality:

How can you check that a point has a lower objective value than every other? For a function to be verifiably optimal, we need a “short proof” of optimality. We need to be able to plug something into a formula that proves optimality. In convex optimization, we turn optimality checking into feasibility problems.

The transformation is very subtle. The first thing to note is that a function is locally optimal for a convex optimization problem if the directional derivative is positive in all directions that could stay feasible. For if the directional derivative were negative in some direction, you could move your point a small amount and decrease the function value. A point is optimal if all such decreasing moves leave the feasible region.

For convex sets, the set of all feasible directions is a cone (if two directions move a point inside a convex set, their sum and scaling do too). I’ll call it the feasible cone. Here’s a nice picture of some feasible cones:

The grey shading indicates the directions that can stay feasible. In the left picture, any direction in a half space can move inside the circle. On the left, only a restricted set of directions can stay inside the polygon.

Everyone forgets this from multivariate calculus, but the directional derivative of f in the direction v has a formula. It is the dot product of v with the gradient of f:

Rederive this for yourself! We want this dot product to be nonnegative for all v in the feasible cone. That means we have stumbled on a bizarre geometric fact. Verifying if x is optimal for a convex problem is thus transformed into if the gradient of the objective is in the dual of the feasible cone at x:

Fancy! We went from some simplistic geometric arguments to checking membership in a dual cone. But it is sort of neat: we transformed a “for all” problem into a “there exists” problem. If we can compute the dual cone of the feasible set, optimality checking is no harder than feasibility checking. This is only true for convex problems and is again a reason why we spend so much time on them.

For the circle above, the feasible cone is a single vector. It’s saying that the gradient of f must point along the x-axis. Here’s a picture showing the dual of the feasible cone for that polygon:

The cone is slightly wider than the polygon itself.

As is always the case in this class, we move back and forth between geometric intuition and algebraic verification. We can explore a few instances of what this condition means algebraically.

Unconstrained problems

For unconstrained problems, every direction is feasible. This means the dual cone is the point 0. That is, a point minimizes a convex function over Rⁿ if and only if its gradient is equal to zero. I am sure many of you have seen that condition before. At least this extra algebraic geometry is recovering common sense.

Equality constrained problems

When does x minimize f over the set where Ax=b? It turns out that this is true if and only if there exists a v such that 

This v is called a Lagrange multiplier. We’ll have a lot more to say about these on Thursday. 

Nonnegatively constraints

What about minimizing functions over nonnegative vectors? The optimality conditions here start to look a bit more exotic. x minimizes f over the nonnegative vectors if and only if the gradient itself is a nonnegative vector, the gradient is equal to zero in the components where x is nonzero, and x is equal to zero in the components where the gradient is nonzero. There is, let’s say, a complementarity between where the gradient vector is zero and the x vector is zero. Think about this condition in 2d:

On the boundary of the orthant, the only way to move into the set is to be orthogonal to that particular axis.

Now, if we had to derive optimality conditions on a case-by-case basis for all possible constraint sets, we wouldn’t be able to solve anything. On Thursday, we’ll dive into a systematic way to generate these sorts of optimality conditions: convex programming duality. The two ideas here, complementarity and Lagrange multipliers, will form the basis.

Subscribe now

By Ben Recht

Authors: Antonio Lauerbach, Kendra Reiter, Marie Schmidt

Dial-a-Ride problems have been proposed to model the challenge to consolidate passenger transportation requests with a fleet of shared vehicles. The line-based Dial-a-Ride problem (LiDARP) is a variant where the passengers are transported along a fixed sequence of stops, with the option of taking shortcuts. In this paper we consider the LiDARP with the objective function to maximize the number of transported requests. We investigate the complexity of two optimization problems: the LiDARP, and the problem to determine the minimum number of turns needed in an optimal LiDARP solution, called the MinTurn problem. Based on a number of instance parameters and characteristics, we are able to state the boundary between polynomially solvable and NP-hard instances for both problems. Furthermore, we provide parameterized algorithms that are able to solve both the LiDARP and MinTurn problem.

Authors: Eero Räty, István Tomon

A celebrated result of Alon from 1993 states that any $d$-regular graph on $n$ vertices (where $d=O(n^{1/9})$) has a bisection with at most $\frac{dn}{2}(\frac{1}{2}-\Omega(\frac{1}{\sqrt{d}}))$ edges, and this is optimal. Recently, this result was greatly extended by R\"aty, Sudakov, and Tomon. We build on the ideas of the latter, and use a semidefinite programming inspired approach to prove the following variant for hypergraphs: every $r$-uniform $d$-regular hypergraph on $n$ vertices (where $d\ll n^{1/2}$) has a bisection of size at most $$\frac{dn}{r}\left(1-\frac{1}{2^{r-1}}-\frac{c}{\sqrt{d}}\right),$$ for some $c=c(r)>0$. This bound is the best possible up to the precise value of $c$. Moreover, a bisection achieving this bound can be found by a polynomial-time randomized algorithm. The minimum bisection is closely related to discrepancy. We also prove sharp bounds on the discrepancy and so called positive discrepancy of hypergraphs, extending results of Bollob\'as and Scott. Furthermore, we discuss implications about Alon-Boppana type bounds. We show that if $H$ is an $r$-uniform $d$-regular hypergraph, then certain notions of second largest eigenvalue $\lambda_2$ associated with the adjacency tensor satisfy $\lambda_2\geq \Omega_r(\sqrt{d})$, improving results of Li and Mohar.

Authors: Angelo Monti, Blerina Sinaimeri

For a positive integer $s$, an $s$-club in a graph $G$ is a set of vertices inducing a subgraph with diameter at most $s$. As generalizations of cliques, $s$-clubs offer a flexible model for real-world networks. This paper addresses the problems of partitioning and disjoint covering of vertices with $s$-clubs on bipartite graphs. First we prove that for any fixed $s \geq 3$ and fixed $k \geq 3$, determining whether the vertices of $G$ can be partitioned into at most $k$ disjoint $s$-clubs is NP-complete even for bipartite graphs. Additionally, we study the Maximum Disjoint $(t,s)$-Club Covering problem (MAX-DCC($t,s$)), which aims to find a collection of vertex-disjoint $(t,s)$-clubs (i.e. $s$-clubs with at least $t$ vertices) that covers the maximum number of vertices in $G$. We prove that it is NP-hard to achieve an approximation factor of $\frac{95}{94} $ for MAX-DCC($t,3$) for any fixed $t\geq 8$ and for MAX-DCC($t,2$) for any fixed $t\geq 5$ even for bipartite graphs. Previously, results were known only for MAX-DCC($3,2$). Finally, we provide a polynomial-time algorithm for MAX-DCC($2,2$).

Authors: Dian Jin

Transfer entropy is used to establish a measure of causal relationships between two variables. Symbolic transfer entropy, as an estimation method for transfer entropy, is widely applied due to its robustness against non-stationarity. This paper investigates the embedding dimension parameter in symbolic transfer entropy and proposes optimization methods for high complexity in extreme cases with complex data. Additionally, it offers some perspectives on estimation methods for transfer entropy.

Authors: William Gay, William He, Nicholas Kocurek

We continue the study of the approximate $k$-wise independence of random reversible circuits as permutations of $\{\pm1\}^n$. Our main result is the first construction of a natural class of random reversible circuits with a sublinear-in-$n$ dependence on depth. Our construction is motivated by considerations in practical cryptography and is somewhat inspired by the design of practical block ciphers, such as DES and AES. Previous constructions of He and O'Donnell [HO24], which were built with gate architectures on one-dimensional lattices, suffered from an inherent linear-in-$n$ dependence on depth. The main novelty of our circuit model is a gate architecture built on higher-dimensional lattices.

Authors: Suthee Ruangwises

Zeiger is a pencil puzzle consisting of a rectangular grid, with each cell having an arrow pointing in horizontal or vertical direction. Some cells also contain a positive integer. The objective of this puzzle is to fill a positive integer into every unnumbered cell such that the integer in each cell is equal to the number of different integers in all cells along the direction an arrow in that cell points to. In this paper, we prove that deciding solvability of a given Zeiger puzzle is NP-complete via a reduction from the not-all-equal positive 3SAT (NAE3SAT+) problem. We also construct a card-based physical zero-knowledge proof protocol for Zeiger, which enables a prover to physically show a verifier the existence of the puzzle's solution without revealing it.

Authors: Yifan Zhang, Yuxuan Zhang

Quantum magic is a resource that allows quantum computation to surpass classical simulation. Previous results have linked the amount of quantum magic, characterized by the number of $T$ gates or stabilizer rank, to classical simulability. However, the effect of the distribution of quantum magic on the hardness of simulating a quantum circuit remains open. In this work, we investigate the classical simulability of quantum circuits with alternating Clifford and $T$ layers across three tasks: amplitude estimation, sampling, and evaluating Pauli observables. In the case where all $T$ gates are distributed in a single layer, performing amplitude estimation and sampling to multiplicative error are already classically intractable under reasonable assumptions, but Pauli observables are easy to evaluate. Surprisingly, with the addition of just one $T$ gate layer or merely replacing all $T$ gates with $T^{\frac{1}{2}}$, the Pauli evaluation task reveals a sharp complexity transition from P to GapP-complete. Nevertheless, when the precision requirement is relaxed to 1/poly($n$) additive error, we are able to give a polynomial time classical algorithm to compute amplitudes, Pauli observable, and sampling from $\log(n)$ sized marginal distribution for any magic-depth-one circuit that is decomposable into a product of diagonal gates. Our research provides new techniques to simulate highly magical circuits while shedding light on their complexity and their significant dependence on the magic depth.

Authors: Naman Jain

We give a parallel $O(\log(n))$-time algorithm on a CRCW PRAM to assign vertical and horizontal segments to the vertices of any planar bipartite graph $G$ in the following manner: i) Two segments cannot share an interior point ii) Two segments intersect if and only if the corresponding vertices are adjacent, which uses a polynomial number of processors. In other words, represent vertices of a planar bipartite graph as parallel segments, and edges as intersection points between these segments. Note that two segments are not allowed to cross. Our method is based on a parallel algorithm for st-numbering which uses an ear decomposition search.

Authors: William Sims, Meera Sitharam

A linkage $(G,\ell)$ is a pair containing a finite simple undirected graph $G$ and a squared edge-length map $\ell$ that assigns squared Euclidean lengths to the edges of $G$. A $d$-realization of $(G,\ell)$ is an assignment of points in $\mathbb{R}^d$ to the vertices of $G$ for which pair-wise distances between points agree with $\ell$. For $d \leq 3$, we characterize pairs $(G,f)$, where $f$ is a nonedge of $G$, such that, for any squared edge-length map $\ell$, there is a single interval of attained distance values between the endpoints of $f$ over all $d$-realizations of $(G,\ell)$, answering a question posed in \cite{sitharam2010characterizing} a decade ago, which gave an equivalent characterization for $d\le 2$ that does not generalize to $d\ge 3$. Two notable byproducts of this characterization are a new tool for partial $3$-tree completion, a well-studied problem, and a deeper understanding of the realization space of partial $3$-tree linkages through the lens of Cayley realization spaces. Although related to the minor closed class of $3$-flattenable graphs, the class of pairs $(G,f)$ with the above property is not minor closed, has no obvious well quasi-ordering, and there are infinitely many minimal graphs-nonedge pairs - w.r.t. edge contractions - in the complement class. Our characterization overcomes these obstacles, is based on the forbidden minors of the class of $3$-flattenable graphs, and contributes to the theory of Cayley configurations used for analyzing distance-constrained configuration spaces in a range of application domains. Generalizations to higher dimensions and efficient algorithmic characterizations are conjectured.

Authors: Nicolas Bousquet, Louis Esperet, Laurent Feuilloley, Sébastien Zeitoun

Local certification is the area of distributed network computing asking the following question: How to certify to the nodes of a network that a global property holds, if they are limited to a local verification? In this area, it is often essential to have identifiers, that is, unique integers assigned to the nodes. In this short paper, we show how to reduce the range of the identifiers, in three different settings. More precisely, we show how to rename identifiers in the classical local certification setting, when we can (resp. cannot) choose the new identifiers, and we show how a global certificate can help to encode very compactly a new identifier assignment that is not injective in general, but still useful. We conclude with a number of applications of these three results.

Authors: Cristian Boldrin, Fabio Vandin

In this work, we present the first efficient and practical algorithm for estimating the number of triangles in a graph stream using predictions. Our algorithm combines waiting room sampling and reservoir sampling with a predictor for the heaviness of edges, that is, the number of triangles in which an edge is involved. As a result, our algorithm is fast, provides guarantees on the amount of memory used, and exploits the additional information provided by the predictor to produce highly accurate estimates. We also propose a simple and domain-independent predictor, based on the degree of nodes, that can be easily computed with one pass on a stream of edges when the stream is available beforehand. Our analytical results show that, when the predictor provides useful information on the heaviness of edges, it leads to estimates with reduced variance compared to the state-of-the-art, even when the predictions are far from perfect. Our experimental results show that, when analyzing a single graph stream, our algorithm is faster than the state-of-the-art for a given memory budget, while providing significantly more accurate estimates. Even more interestingly, when sequences of hundreds of graph streams are analyzed, our algorithm significantly outperforms the state-of-the-art using our simple degree-based predictor built by analyzing only the first graph of the sequence.

Authors: Max Bender, Aum Desai, Jialin He, Oliver Thompson, Pramithas Upreti

We consider dynamic pricing algorithms as applied to the online set cover problem. In the dynamic pricing framework, we assume the standard client server model with the additional constraint that the server can only place prices over the resources they maintain, rather than authoritatively assign them. In response, incoming clients choose the resource which minimizes their disutility when taking into account these additional prices. Our main contributions are the categorization of online algorithms which can be mimicked via dynamic pricing algorithms and the identification of a strongly competitive deterministic algorithm with respect to the frequency parameter of the online set cover input.

Authors: Pavel Arkhipov, Vladimir Kolmogorov

We consider two problems for a directed graph $G$, which we show to be closely related. The first one is to find $k$ edge-disjoint forests in $G$ of maximal size such that the indegree of each vertex in these forests is at most $k$. We describe a min-max characterization for this problem and show that it can be solved in $O(k \delta m \log n)$ time, where $(n,m)$ is the size of $G$ and $\delta$ is the difference between $k$ and the edge connectivity of the graph. The second problem is the directed edge-connectivity augmentation problem, which has been extensively studied before: find a smallest set of directed edges whose addition to the graph makes it strongly $k$-connected. We improve the complexity for this problem from $O(k \delta (m+\delta n)\log n)$ [Gabow, STOC 1994] to $O(k \delta m \log n)$, by exploiting our solution for the first problem. A similar approach with the same complexity also works for the undirected version of the problem.

Authors: Matin Ansaripour, Alireza Danaei, Kurt Mehlhorn

It is known since 1975 (\cite{HK75}) that maximum cardinality matchings in bipartite graphs with $n$ nodes and $m$ edges can be computed in time $O(\sqrt{n} m)$. Asymptotically faster algorithms were found in the last decade and maximum cardinality bipartite matchings can now be computed in near-linear time~\cite{NearlyLinearTimeBipartiteMatching, AlmostLinearTimeMaxFlow,AlmostLinearTimeMinCostFlow}. For general graphs, the problem seems harder. Algorithms with running time $O(\sqrt{n} m)$ were given in~\cite{MV80,Vazirani94,Vazirani12,Vazirani20,Vazirani23,Goldberg-Karzanov,GT91,Gabow:GeneralMatching}. Mattingly and Ritchey~\cite{Mattingly-Ritchey} and Huang and Stein~\cite{Huang-Stein} discuss implementations of the Micali-Vazirani Algorithm. We describe an implementation of Gabow's algorithm~\cite{Gabow:GeneralMatching} in C++ based on LEDA~\cite{LEDAsystem,LEDAbook} and report on running time experiments. On worst-case graphs, the asymptotic improvement pays off dramatically. On random graphs, there is no improvement with respect to algorithms that have a worst-case running time of $O(n m)$. The performance seems to be near-linear. The implementation is available open-source.

Authors: Dustin Cobas, Travis Gagie, Gonzalo Navarro

The $r$-index represented a breakthrough in compressed indexing of repetitive text collections, outperforming its alternatives by orders of magnitude in query time. Its space usage, $O(r)$ where $r$ is the number of runs in the Burrows--Wheeler Transform of the text, is however higher than Lempel--Ziv (LZ) and grammar-based indexes, and makes it uninteresting in various real-life scenarios of milder repetitiveness. We introduce the $sr$-index, a variant that limits the space to $O(\min(r,n/s))$ for a text of length $n$ and a given parameter $s$, at the expense of multiplying by $s$ the time per occurrence reported. The $sr$-index is obtained subsampling the text positions indexed by the $r$-index, being still able to support pattern matching with guaranteed performance. Our experiments show that the theoretical analysis falls short in describing the practical advantages of the $sr$-index, because it performs much better on real texts than on synthetic ones: the $sr$-index retains the performance of the $r$-index while using 1.5--4.0 times less space, sharply outperforming {\em virtually every other} compressed index on repetitive texts in both time and space. Only a particular LZ-based index uses less space than the $sr$-index, but it is an order of magnitude slower. Our second contribution are the $r$-csa and $sr$-csa indexes. Just like the $r$-index adapts the well-known FM-Index to repetitive texts, the $r$-csa adapts Sadakane's Compressed Suffix Array (CSA) to this case. We show that the principles used on the $r$-index turn out to fit naturally and efficiently in the CSA framework. The $sr$-csa is the corresponding subsampled version of the $r$-csa. While the CSA performs better than the FM-Index on classic texts with alphabets larger than DNA, we show that the $sr$-csa outperforms the $sr$-index on repetitive texts over those larger alphabets and some DNA texts as well.

Authors: Dominik Köppl

We propose algorithms computing the semi-greedy Lempel-Ziv 78 (LZ78), the Lempel-Ziv Double (LZD), and the Lempel-Ziv-Miller-Wegman (LZMW) factorizations in linear time for integer alphabets. For LZD and LZMW, we additionally propose data structures that can be constructed in linear time, which can solve the substring compression problems for these factorizations in time linear in the output size. For substring compression, we give results for lexparse and closed factorizations.