Authors: Robert M. Alaniz, Josh Brunner, Michael Coulombe, Erik D. Demaine, Yevhenii Diomidov, Ryan Knobel, Timothy Gomez, Elise Grizzell, Jayson Lynch, Andrew Rodriguez, Robert Schweller, Tim Wylie

We analyze the computational complexity of basic reconfiguration problems for the recently introduced surface Chemical Reaction Networks (sCRNs), where ordered pairs of adjacent species nondeterministically transform into a different ordered pair of species according to a predefined set of allowed transition rules (chemical reactions). In particular, two questions that are fundamental to the simulation of sCRNs are whether a given configuration of molecules can ever transform into another given configuration, and whether a given cell can ever contain a given species, given a set of transition rules. We show that these problems can be solved in polynomial time, are NP-complete, or are PSPACE-complete in a variety of different settings, including when adjacent species just swap instead of arbitrary transformation (swap sCRNs), and when cells can change species a limited number of times (k-burnout). Most problems turn out to be at least NP-hard except with very few distinct species (2 or 3).

Authors: Oswin Aichholzer, Joachim Orthaber, Birgit Vogtenhuber

It is a longstanding conjecture that every simple drawing of a complete graph on $n\geq 3$ vertices contains a crossing-free Hamiltonian cycle. We confirm this conjecture for cylindrical drawings, strongly $c$-monotone drawings, as well as $x$-bounded drawings. Moreover, we introduce the stronger question of whether a crossing-free Hamiltonian path between each pair of vertices always exists.

Authors: Ilan Newman, Yuri Rabinovich

We study deterministic online embeddings of metrics spaces into normed spaces and into trees against an adaptive adversary. Main results include a polynomial lower bound on the (multiplicative) distortion of embedding into Euclidean spaces, a tight exponential upper bound on embedding into the line, and a $(1+\epsilon)$-distortion embedding in $\ell_\infty$ of a suitably high dimension.

Authors: François Lamothe, Emmanuel Rachelson, Alain Haït, Cedric Baudoin, Jean-Baptiste Dupe

Unsplittable flow problems cover a wide range of telecommunication and transportation problems and their efficient resolution is key to a number of applications. In this work, we study algorithms that can scale up to large graphs and important numbers of commodities. We present and analyze in detail a heuristic based on the linear relaxation of the problem and randomized rounding. We provide empirical evidence that this approach is competitive with state-of-the-art resolution methods either by its scaling performance or by the quality of its solutions. We provide a variation of the heuristic which has the same approximation factor as the state-of-the-art approximation algorithm. We also derive a tighter analysis for the approximation factor of both the variation and the state-of-the-art algorithm. We introduce a new objective function for the unsplittable flow problem and discuss its differences with the classical congestion objective function. Finally, we discuss the gap in practical performance and theoretical guarantees between all the aforementioned algorithms.

Authors: Xiang Li, Mingfu Shao

The high-throughput short-reads RNA-seq protocols often produce paired-end reads, with the middle portion of the fragments being unsequenced. We explore if the full-length fragments can be computationally reconstructed from the sequenced two ends in the absence of the reference genome - a problem here we refer to as de novo bridging. Solving this problem provides longer, more informative RNA-seq reads, and benefits downstream RNA-seq analysis such as transcript assembly, expression quantification, and splicing differential analysis. However, de novo bridging is a challenging and complicated task owing to alternative splicing, transcript noises, and sequencing errors. It remains unclear if the data provides sufficient information for accurate bridging, let alone efficient algorithms that determine the true bridges. Methods have been proposed to bridge paired-end reads in the presence of reference genome (called reference-based bridging), but the algorithms are far away from scaling for de novo bridging as the underlying compacted de Bruijn graph(cdBG) used in the latter task often contains millions of vertices and edges. We designed a new truncated Dijkstra's algorithm for this problem, and proposed a novel algorithm that reuses the shortest path tree to avoid running the truncated Dijkstra's algorithm from scratch for all vertices for further speeding up. These innovative techniques result in scalable algorithms that can bridge all paired-end reads in a cdBG with millions of vertices. Our experiments showed that paired-end RNA-seq reads can be accurately bridged to a large extent. The resulting tool is freely available at https://github.com/Shao-Group/rnabridge-denovo.

Authors: Konstantinos Georgiou, Nikos Giachoudis, Evangelos Kranakis

We consider search by mobile agents for a hidden, idle target, placed on the infinite line. Feasible solutions are agent trajectories in which all agents reach the target sooner or later. A special feature of our problem is that the agents are $p$-faulty, meaning that every attempt to change direction is an independent Bernoulli trial with known probability $p$, where $p$ is the probability that a turn fails. We are looking for agent trajectories that minimize the worst-case expected termination time, relative to competitive analysis.

First, we study linear search with one deterministic $p$-faulty agent, i.e., with no access to random oracles, $p\in (0,1/2)$. For this problem, we provide trajectories that leverage the probabilistic faults into an algorithmic advantage. Our strongest result pertains to a search algorithm (deterministic, aside from the adversarial probabilistic faults) which, as $p\to 0$, has optimal performance $4.59112+\epsilon$, up to the additive term $\epsilon$ that can be arbitrarily small. Additionally, it has performance less than $9$ for $p\leq 0.390388$. When $p\to 1/2$, our algorithm has performance $\Theta(1/(1-2p))$, which we also show is optimal up to a constant factor.

Second, we consider linear search with two $p$-faulty agents, $p\in (0,1/2)$, for which we provide three algorithms of different advantages, all with a bounded competitive ratio even as $p\rightarrow 1/2$. Indeed, for this problem, we show how the agents can simulate the trajectory of any $0$-faulty agent (deterministic or randomized), independently of the underlying communication model. As a result, searching with two agents allows for a solution with a competitive ratio of $9+\epsilon$, or a competitive ratio of $4.59112+\epsilon$. Our final contribution is a novel algorithm for searching with two $p$-faulty agents that achieves a competitive ratio $3+4\sqrt{p(1-p)}$.

Authors: Rashmi Ranjan Bhuyan, Adel Javanmard, Sungchul Kim, Gourab Mukherjee, Ryan A. Rossi, Tong Yu, Handong Zhao

We consider dynamic pricing strategies in a streamed longitudinal data set-up where the objective is to maximize, over time, the cumulative profit across a large number of customer segments. We consider a dynamic probit model with the consumers' preferences as well as price sensitivity varying over time. Building on the well-known finding that consumers sharing similar characteristics act in similar ways, we consider a global shrinkage structure, which assumes that the consumers' preferences across the different segments can be well approximated by a spatial autoregressive (SAR) model. In such a streamed longitudinal set-up, we measure the performance of a dynamic pricing policy via regret, which is the expected revenue loss compared to a clairvoyant that knows the sequence of model parameters in advance. We propose a pricing policy based on penalized stochastic gradient descent (PSGD) and explicitly characterize its regret as functions of time, the temporal variability in the model parameters as well as the strength of the auto-correlation network structure spanning the varied customer segments. Our regret analysis results not only demonstrate asymptotic optimality of the proposed policy but also show that for policy planning it is essential to incorporate available structural information as policies based on unshrunken models are highly sub-optimal in the aforementioned set-up.

Authors: Dhanyamol Antony, Sagartanu Pal, R.B. Sandeep

For a class $\mathcal{G}$ of graphs, the objective of \textsc{Subgraph Complementation to} $\mathcal{G}$ is to find whether there exists a subset $S$ of vertices of the input graph $G$ such that modifying $G$ by complementing the subgraph induced by $S$ results in a graph in $\mathcal{G}$. We obtain a polynomial-time algorithm for the problem when $\mathcal{G}$ is the class of graphs with minimum degree at least $k$, for a constant $k$, answering an open problem by Fomin et al. (Algorithmica, 2020). When $\mathcal{G}$ is the class of graphs without any induced copies of the star graph on $t+1$ vertices (for any constant $t\geq 3$) and diamond, we obtain a polynomial-time algorithm for the problem. This is in contrast with a result by Antony et al. (Algorithmica, 2022) that the problem is NP-complete and cannot be solved in subexponential-time (assuming the Exponential Time Hypothesis) when $\mathcal{G}$ is the class of graphs without any induced copies of the star graph on $t+1$ vertices, for every constant $t\geq 5$.

Authors: Mohsen Ghaffari, Christoph Grunau

$ \renewcommand{\tilde}{\widetilde} $We present an $\tilde{O}(\log^2 n)$ round deterministic distributed algorithm for the maximal independent set problem. By known reductions, this round complexity extends also to maximal matching, $\Delta+1$ vertex coloring, and $2\Delta-1$ edge coloring. These four problems are among the most central problems in distributed graph algorithms and have been studied extensively for the past four decades. This improved round complexity comes closer to the $\tilde{\Omega}(\log n)$ lower bound of maximal independent set and maximal matching [Balliu et al. FOCS '19]. The previous best known deterministic complexity for all of these problems was $\Theta(\log^3 n)$. Via the shattering technique, the improvement permeates also to the corresponding randomized complexities, e.g., the new randomized complexity of $\Delta+1$ vertex coloring is now $\tilde{O}(\log^2\log n)$ rounds.

Our approach is a novel combination of the previously known two methods for developing deterministic algorithms for these problems, namely global derandomization via network decomposition (see e.g., [Rozhon, Ghaffari STOC'20; Ghaffari, Grunau, Rozhon SODA'21; Ghaffari et al. SODA'23]) and local rounding of fractional solutions (see e.g., [Fischer DISC'17; Harris FOCS'19; Fischer, Ghaffari, Kuhn FOCS'17; Ghaffari, Kuhn FOCS'21; Faour et al. SODA'23]). We consider a relaxation of the classic network decomposition concept, where instead of requiring the clusters in the same block to be non-adjacent, we allow each node to have a small number of neighboring clusters. We also show a deterministic algorithm that computes this relaxed decomposition faster than standard decompositions. We then use this relaxed decomposition to significantly improve the integrality of certain fractional solutions, before handing them to the local rounding procedure that now has to do fewer rounding steps.

Authors: Irina Kostitsyna, David Liedtke, Christian Scheideler

Motivated by the prospect of nano-robots that assist human physiological functions at the nanoscale, we investigate the coating problem in the three-dimensional model for hybrid programmable matter. In this model, a single agent with strictly limited viewing range and the computational capability of a deterministic finite automaton can act on passive tiles by picking up a tile, moving, and placing it at some spot. The goal of the coating problem is to fill each node of some surface graph of size $n$ with a tile. We first solve the problem on a restricted class of graphs with a single tile type, and then use constantly many tile types to encode this graph in certain surface graphs capturing the surface of 3D objects. Our algorithm requires $\mathcal{O}(n^2)$ steps, which is worst-case optimal compared to an agent with global knowledge and no memory restrictions.

At least six readers have by now sent me the following photo, which was taken in Israel a couple nights ago during the historic street protests against Netanyahu’s attempted putsch:

(Update: The photo was also featured on Gil Kalai’s blog, and was credited there to Alon Rosen.)

This is surely the first time that “P=NP” has emerged as a viral rallying cry for the preservation of liberal democracy, even to whatever limited extent it has.

But what was the graffiti artist’s intended meaning? A few possibilities:

1. The government has flouted so many rules of Israel’s social compact that our side needs to flout the rules too: shut down the universities, shut down the airport, block the roads, even assert that P=NP (!).
2. As a protest movement up against overwhelming odds, we need to shoot for the possibly-impossible, like solving 3SAT in polynomial time.
3. A shibboleth for scientific literate people following the news: “Israel is full of sane people who know what ‘P=NP’ means as you know what it means, are amused by its use as political graffiti as you’d be amused by it, and oppose Netanyahu’s putsch for the same reasons you’d oppose it.”
4. No meaning, the artist was just amusing himself or herself.
5. The artist reads Shtetl-Optimized and wanted effectively to force me to feature his or her work here.

Anyway, if the artist becomes aware of this post, he or she is warmly welcomed to clear things up for us.

And when this fight resumes after Passover, may those standing up for the checks and balances of a liberal-democratic society achieve … err … satisfaction, however exponentially unlikely it seems.

By Scott

Let $\mathcal{L}$ be a language that can be decided in linear space and let $\epsilon >0$ be any constant. Let $\mathcal{A}$ be the exponential hardness assumption that for every $n$, membership in $\mathcal{L}$ for inputs of length~$n$ cannot be decided by circuits of size smaller than $2^{\epsilon n}$. We prove that for every function $f :\{0,1\}^* \rightarrow \{0,1\}$, computable by a randomized logspace algorithm $R$, there exists a deterministic logspace algorithm $D$ (attempting to compute $f$), such that on every input $x$ of length $n$, the algorithm $D$ outputs one of the following: 1: The correct value $f(x)$. 2: The string: ``I am unable to compute $f(x)$ because the hardness assumption $\mathcal{A}$ is false'', followed by a (provenly correct) circuit of size smaller than $2^{\epsilon n'}$ for membership in $\mathcal{L}$ for inputs of length~$n'$, for some $n' = \Theta (\log n)$; that is, a circuit that refutes $\mathcal{A}$. Moreover, $D$ is explicitly constructed, given $R$. We note that previous works on the hardness-versus-randomness paradigm give derandomized algorithms that rely blindly on the hardness assumption. If the hardness assumption is false, the algorithms may output incorrect values, and thus a user cannot trust that an output given by the algorithm is correct. Instead, our algorithm $D$ verifies the computation so that it never outputs an incorrect value. Thus, if $D$ outputs a value for $f(x)$, that value is certified to be correct. Moreover, if $D$ does not output a value for $f(x)$, it alerts that the hardness assumption was found to be false, and refutes the assumption. Our next result is a universal derandomizer for $BPL$ (the class of problems solvable by bounded-error randomized logspace algorithms): We give a deterministic algorithm $U$ that takes as an input a randomized logspace algorithm $R$ and an input $x$ and simulates the computation of $R$ on $x$, deteriministically. Under the widely believed assumption $BPL=L$, the space used by $U$ is at most $C_R \cdot \log n$ (where $C_R$ is a constant depending on~$R$). Moreover, for every constant $c \geq 1$, if $BPL\subseteq SPACE[(\log(n))^{c}]$ then the space used by $U$ is at most $C_R \cdot (\log(n))^{c}$. Finally, we prove that if optimal hitting sets for ordered branching programs exist then there is a deterministic logspace algorithm that, given a black-box access to an ordered branching program $B$ of size $n$, estimates the probability that $B$ accepts on a uniformly random input. This extends the result of (Cheng and Hoza CCC 2020), who proved that an optimal hitting set implies a white-box two-sided derandomization.

We relate various complexity measures like sensitivity, block sensitivity, certificate complexity for multi-output functions to the query complexities of such functions. Using these relations, we improve upon the known relationship between pseudo-deterministic query complexity and deterministic query complexity for total search problems: We show that pseudo-deterministic query complexity is at most the third power of its deterministic query complexity. (Previously a fourth-power relation was shown by Goldreich,Goldwasser,Ron (ITCS13).) We then obtain a significantly simpler and self-contained proof of a separation between pseudodeterminism and randomized query complexity recently proved by Goldwasser, Impagliazzo, Pitassi, Santhanam (CCC 2021). We also separate pseudodeterminism from randomness in AND decision trees, and determinism from pseudodeterminism in PARITY decision trees. For a hypercube colouring problem closely related to the pseudodeterministic complexity of a complete problem in $TFNP^{dt}$, we prove that either the monotone block-sensitivity or the anti-monotone block sensitivity is $\Omega(n^{1/3})$; previously an $\Omega(n^{1/2})$ bound was known but for general block-sensitivity.

The range avoidance problem (denoted by Avoid) asks to find a string outside of the range of a given circuit $C:\{0,1\}^n\to\{0,1\}^m$, where $m>n$. Although at least half of the strings of length $m$ are correct answers, it is not clear how to deterministically find one. Recent results of Korten (FOCS'21) and Ren, Wang, and Santhanam (FOCS' 22) show that efficient deterministic algorithms for Avoid would have far-reaching consequences, including strong circuit lower bounds and explicit constructions of combinatorial objects (e.g., Ramsey graphs, extractors, rigid matrices). This strongly motivates the question: does an efficient deterministic algorithm for Avoid actually exist? In this work, we prove under the existence of subexponentially secure indistinguishability obfuscation (iO) that deterministic polynomial-time algorithms for Avoid imply NP=coNP. Combining this with Jain, Lin, and Sahai's recent breakthrough construction of iO from well-founded assumptions (STOC'21, EUROCRYPT'22), we provide the first plausible evidence that Avoid has no efficient deterministic algorithm. Moreover, we also prove the hardness of Avoid based on polynomially-secure iO and a weaker variant of the Nondeterministic Exponential Time Hypothesis (NETH). Extending our techniques, we prove a surprising separation in bounded arithmetic, conditioned on similar assumptions. Assuming subexponentially secure iO and coNP is not infinitely often in AM, we show that Avoid has no deterministic polynomial-time algorithm even when we are allowed $O(1)$ queries to an oracle that can invert the given input circuit on an arbitrarily chosen $m$-bit string. It follows that the dual Weak Pigeonhole Principle, the combinatorial principle underlying Avoid, is not provable in Cook's theory $PV_1$. This gives (under plausible assumptions) the first separation of Cook's theory $PV_1$ for polynomial-time reasoning and Jerabek's theory $APC_1$ for probabilistic polynomial-time reasoning.

In the previous post, Two Three Four posts ago I wrote about three recent breakthroughs in combinatorics and here I want to mention some problems that I posed over the years that are loosely related to these advances.

Rank of incidence matrices and q-analogs

The goal of finding q-analogs of combinatorial results where, roughly speaking, sets are replaced by subspaces of vector spaces over a field with elements, is common both in enumerative combinatorics and in extremal combinatorics. A recent breakthrough we discussed by Keevash, Sah, and Sawhney was about the existence of -analogs of designs (subspace designs).

I will mention a problem (Question 4) in this direction about incidence matrices, following three questions that were largely solved.

Incidence matrices and weighted incidence matrices for sets

The incidence matrix of -subsets vs. -subsets of , is a matrix whose rows correspond to -subsets of , whose columns correspond to -subsets of , and the entry equals 1 if , and equals 0 if .

A weighted incidence matrix of -subsets vs. -subsets of , is a matrix whose rows correspond to -subsets of , whose columns correspond to -subsets of , and if and   if .

Question 1: What is the rank of the incidence matrix of -subsets vs. -subsets of , over a field of characteristic .

This question was beautifully answered by Richard Wilson in 1990 . The problem was posed by Nati Linial and Bruce Rothschild in 1981 and they settled the case .  (The answer for , , that motivated the question, was observed earlier by Perles and by Frankl.) It is unforgivable that I did not present the statement of Wilson’s theorem here on the blog.

Question 2: What is the minimum rank, denoted by , of a weighted incidence matrix of -subsets vs. -subsets of $[n]$ over a field of characteristic .

This question was answered by me in the early 80s (it is related also to various results by others around the same time). The answer is , and remarkably it is independent from the characteristic .

Incidence matrices and weighted incidence matrices for subspaces

The incidence matrix of -dimensional subspaces vs. -dimensional subspaces of ( has entries if and if .

A weighted incidence matrix of -dimensional subspaces vs. -dimensional subspaces of () has entries if and if .

We pose two additional questions which are the “q-analogs” of Questions 1 and 2.

Question 3:  What is the rank of the incidence matrix over a field of characteristic $p$ (you can simply take the field ).

Frumkin and Yakir settled problem 3 when is not a power of .

The problem I want to pose (again) here is:

Question 4:  What is the minimum rank denoted by of a weighted incidence matrix over a field of characteristic .

In particular, I would like to know if the answer does not depend on and if it agrees with some easy lower bounds (obtained from certain identity submatrices) like in the case of a field with one element (namely, subsets).

q-trees

Qoestion 5: What are the q-analogs of trees? (and hypertrees).

The basic idea is first to find weights so that the incidence matrix of 1-subspace vs 2-subspaces has rank , and then the -trees will correspond to collection of 2-spaces with linearly independent columns. (I don’t expect uniqueness.) This is a little related to a -analog of the notion of symmetric matroids that I studied in the late 80s.

A year ago Ferdinand Ihringer, Motaz Mokatren and I made some very preliminary steps in this direction before moving on (separately) to other projects. It will be nice to come back to it.

Remark: There is even greater generalities where problems can be extended from set systems (graphs and hypergraphs) to more general algebraic objects. Those could be related to general primitive permutation groups, to association schemes, and to other objects in algebraic combinatorics.

Unit distances and related problems in discrete geometry.

Let be a normed space. For a set the unit distance graph is the graph whose vertices are points in and two vertices are adjacent if their distance is one.

We can consider the following quantities

1) : The maximum size of a unit distance set in . (In other words, the maximum clique in .)

2) :  The number of colors needed for if two points of unit distance are colored with different colors.

3) : The maximum number of colors needed to color points in a set of diameter 1 if  every color set has diameter smaller than 1. (This is the Borsuk number of .)

4) The maximum number of colors needed to color points in a finite set of diameter 1 if  two points of unit distance are colored with different colors.

5) The maximum number of points of norm 1 with pairwise distances at least 1.

6) The maximum over all sets with points of pairwise distance at least one, of the minimum degree in the unit distance graph .

7) The maximum over all sets with points of pairwise distance at least one of the chromatic number of the unit distance graph of .

Estimating these seven quantities for Euclidean spaces and for other normed spaces are well-known problems. (See my survey article on problems around Borsuk’s problem.) Alon, Bucić, and Sauermann made a remarkable breakthrough on the first problem of the largest clique in a unit distance graphs for arbitrary normed spaces.

Jordan Ellenberg asked: “Does the Alon-Bucic-Sauermann result give you upper bounds for the chromatic number of (the unit distance graph of) with a typical norm? (Or is that already easy for some reason?) “.  But I know little about Jordan’s question.

There is much to say about them but I will not discuss these problems here. I will mention a single annoying problem.

Question 6: Is there an example of a normed space such that ?

(I am not even sure if for the seventh item it makes a difference to consider finite .)

Intersection patterns of standard boxes

In the post that I mentioned we also discussed Tomon’s remarkable result on intersection patterns of standard boxes. Here is some loosely related problem. In short, we want to find topological analogs for results on intersection patterns of standard boxes.

Topological Helly-type theorems is an important direction in geometric and topological combinatorics. The idea is to prove Helly type theorems about convex sets in a much wider topological contexts.

A primary goal of Topological Helly-type theorems is to extend results for nerves of families of convex sets in to the class of -Leray simplcial complexes. Among the results achieved so far are: The upper bound theorem; Eckhoff’s conjecture; Alon and Kleitman’s (p,q)-theorem; colorful and matroidal Helly’s theorem; topological Amenta’s theorem, and more.

Another goal of Topological Helly-type theorems is to study if results on nerves of standard boxes can be extended to flag -Leray simplicial complexes?

In this direction the immediate goal is to extend Eckhoff’s upper bound theorem. (Item 3 in this post.)

Question 7. Conjecture: Let be a Leray flag complex of dimension with $n$ vertices. Then the -vector of obeys Eckhoff’s upper bound theorem for standard boxes.

A closely related question is

Question 8. Conjecture: Let be a -Leray flag complex of dimension , then the -vector of is the -vector of a completely balanced -dimensional -Leray complex.

Studying the equality cases of the conjecture is also of interest and the extremal complexes can also be regarded as some sort of ultra-trees.

Roy Meshulam and I worked together on topological Helly type theorems for more than two decades.

By Gil Kalai

A one-way function is a function that is easy to compute but hard to invert *on average*. We establish the first characterization of a one-way function by *worst-case* hardness assumptions, by introducing a natural meta-computational problem whose NP-hardness (and the worst-case hardness of NP) characterizes the existence of a one-way function. Specifically, we generalize the notion of time-bounded conditional Kolmogorov complexity to *distributional Kolmogorov complexity*, and prove that a one-way function exists if and only if it is NP-hard to approximate the distributional Kolmogorov complexity under randomized polynomial-time reductions and NP is hard in the worst case. We also propose the *Meta-Complexity Padding Conjecture*, which postulates that distributional Kolmogorov complexity is paddable by an approximation-preserving reduction. Under this conjecture, we prove that the worst-case hardness of an approximate version of the Minimum Circuit Size Problem characterizes the existence of a one-way function. Our results extend the emerging paradigm of meta-complexity, which suggests that proving NP-hardness of meta-computational problems (i.e., problems that ask to compute complexity) is sufficient to exclude errorless Heuristica and error-prone Pessiland from Impagliazzo's five worlds. The key technical contribution is to conditionally close the gap between errorless and error-prone average-case complexities by combining Nanashima's proof techniques of showing "limits" of black-box reductions (ITCS'21) with non-black-box worst-case-to-average-case reductions of Hirahara (FOCS'18).

Authors: Kaan Gokcesu, Hakan Gokcesu

This study presents an effective global optimization technique designed for multivariate functions that are H\"older continuous. Unlike traditional methods that construct lower bounding proxy functions, this algorithm employs a predetermined query creation rule that makes it computationally superior. The algorithm's performance is assessed using the average or cumulative regret, which also implies a bound for the simple regret and reflects the overall effectiveness of the approach. The results show that with appropriate parameters the algorithm attains an average regret bound of $O(T^{-\frac{\alpha}{n}})$ for optimizing a H\"older continuous target function with H\"older exponent $\alpha$ in an $n$-dimensional space within a given time horizon $T$. We demonstrate that this bound is minimax optimal.

Authors: Chuang-Chieh Lin, Chi-Jen Lu, Po-An Chen

We extend our previous work on two-party election competition [Lin, Lu & Chen 2021] to the setting of three or more parties. An election campaign among two or more parties is viewed as a game of two or more players. Each of them has its own candidates as the pure strategies to play. People, as voters, comprise supporters for each party, and a candidate brings utility for the the supporters of each party. Each player nominates exactly one of its candidates to compete against the other party's. \emph{A candidate is assumed to win the election with higher odds if it brings more utility for all the people.} The payoff of each player is the expected utility its supporters get. The game is egoistic if every candidate benefits her party's supporters more than any candidate from the competing party does. In this work, we first argue that the election game always has a pure Nash equilibrium when the winner is chosen by the hardmax function, while there exist game instances in the three-party election game such that no pure Nash equilibrium exists even the game is egoistic. Next, we propose two sufficient conditions for the egoistic election game to have a pure Nash equilibrium. Based on these conditions, we propose a fixed-parameter tractable algorithm to compute a pure Nash equilibrium of the egoistic election game. Finally, perhaps surprisingly, we show that the price of anarchy of the egoistic election game is upper bounded by the number of parties. Our findings suggest that the election becomes unpredictable when more than two parties are involved and, moreover, the social welfare deteriorates with the number of participating parties in terms of possibly increasing price of anarchy. This work alternatively explains why the two-party system is prevalent in democratic countries.

Authors: Marc Lambert (DGA, SIERRA), Silvère Bonnabel (CAOR, ISEA), Francis Bach (LIENS, SIERRA)

We consider the problem of computing a Gaussian approximation to the posterior distribution of a parameter given a large number N of observations and a Gaussian prior, when the dimension of the parameter d is also large. To address this problem we build on a recently introduced recursive algorithm for variational Gaussian approximation of the posterior, called recursive variational Gaussian approximation (RVGA), which is a single pass algorithm, free of parameter tuning. In this paper, we consider the case where the parameter dimension d is high, and we propose a novel version of RVGA that scales linearly in the dimension d (as well as in the number of observations N), and which only requires linear storage capacity in d. This is afforded by the use of a novel recursive expectation maximization (EM) algorithm applied for factor analysis introduced herein, to approximate at each step the covariance matrix of the Gaussian distribution conveying the uncertainty in the parameter. The approach is successfully illustrated on the problems of high dimensional least-squares and logistic regression, and generalized to a large class of nonlinear models.

Authors: Daniel Lemire

We sometimes need to compute the most significant digits of the product of small integers with a multiplier requiring much storage: e.g., a large integer (e.g., $5^{100}$) or an irrational number ($\pi$). We only need to access the most significant digits of the multiplier-as long as the integers are sufficiently small. We provide an efficient algorithm to compute the range of integers given a truncated multiplier and a desired number of digits.

Authors: Giuseppe Lancia, Marcello Dalpasso

We discuss the way to group all 25 possible 4-OPT moves into 7 orbits of equivalent moves. We then describe two implementations, one for a $\Theta(n^3)$ algorithm by de Berg's et al. and one of a $\Theta(n^2)$ algorithm by Glover, for finding the best 4-OPT move via dynamic programming.

Authors: Tommaso Lanciano, Atsushi Miyauchi, Adriano Fazzone, Francesco Bonchi

The Densest Subgraph Problem requires to find, in a given graph, a subset of vertices whose induced subgraph maximizes a measure of density. The problem has received a great deal of attention in the algorithmic literature over the last five decades, with many variants proposed and many applications built on top of this basic definition. Recent years have witnessed a revival of research interest on this problem with several interesting contributions, including some groundbreaking results, published in 2022 and 2023. This survey provides a deep overview of the fundamental results and an exhaustive coverage of the many variants proposed in the literature, with a special attention on the most recent results. The survey also presents a comprehensive overview of applications and discusses some interesting open problems for this evergreen research topic.

This September, Bocconi will start a new M.Sc. in Artificial Intelligence. It will be a two-year computer science degree meant for students with Bachelor degrees in computer science, engineering, math, statistics, physics and related quantitative fields.

In the first year, courses on algorithms, mathematical methods, optimization, information theory, and software engineering will build a foundation in math and CS, then courses on deep learning, reinforcement learning, natural language processing and computer vision and image processing will go in depth on machine learning and some of its applications. In the second year there are various options and elective courses, with the possibility to study, for example, cryptography and blockchains, or bio-medical applications. As common for the second year of Bocconi’s M.Sc. degrees, there will be options for exchange programs to spend a semester abroad. Students also take a seminar on ethics in AI, a project-oriented AI lab, and a foreign language (not English and not the student’s native language) course. The language of instruction is English.

Tomorrow at 5pm CET there will be an online information session: those interested can sign up here.

More information about the degree are at www.unibocconi.eu/ai-msc.

Applications open today and are due by May 25th.

By luca

Existing proofs that deduce BPL=L from circuit lower bounds convert randomized algorithms into deterministic algorithms with large constant overhead in space. We study space-bounded derandomization with minimal footprint, and ask what is the minimal possible space overhead for derandomization. We show that $BPSPACE[S] \subseteq DSPACE[c \cdot S]$ for $c \approx 2$, assuming space-efficient cryptographic PRGs, and, either: (1) lower bounds against bounded-space algorithms with advice, or: (2) lower bounds against certain uniform compression algorithms. Under additional assumptions regarding the power of catalytic computation, in a new setting of parameters that was not studied before, we are even able to get $c \approx 1$. Our results are constructive: Given a candidate hard function (and a candidate cryptographic PRG) we show how to transform the randomized algorithm into an efficient deterministic one. This follows from new PRGs and targeted PRGs for space-bounded algorithms, which we combine with novel space-efficient evaluation methods. A central ingredient in all our constructions is hardness amplification reductions in logspace-uniform $TC^0$, that were not known before.

Jönköping University (JU) advertises one position as PhD student in Computer Science, in collaboration with the theoretical computer science laboratory, Linköping university (LiU). The PhD student will join a research project in the intersection of artificial intelligence, complexity theory, and universal algebra, directed by Johannes Schmidt (JU) and Victor Lagerkvist (LiU).

Website: https://ju.varbi.com/se/what:job/jobID:601050/where:4/
Email: victor.lagerkvist@liu.se

By shacharlovett

Last night, the demonstrations in Israel regarding the “judicial reforms” escalated after the prime minister Netanyahu fired the defense minister Galant who called to stop the legislation. My wife and I enjoyed a concert and after it we heard loud calls “Bibi fired Galant” and even “The dictator fired Galant,” and were surprised by the news and the huge groups of young people, very angry for a very good reason. And, of course, we joined them. The picture above provided by Alon Rosen is from a major highway in Tel Aviv that was blocked for 9 hours. Whether the picture is genuine or not, it shows the anarchist nature of at least some of the protestors.  (We know for sure that some computer scientists were there.) I am not sure if a proof of this bold claim was also provided.

By Gil Kalai

Authors: Olympio Hacquard, Vadim Lebovici

In this article, we study Euler characteristic techniques in topological data analysis. Pointwise computing the Euler characteristic of a family of simplicial complexes built from data gives rise to the so-called Euler characteristic profile. We show that this simple descriptor achieve state-of-the-art performance in supervised tasks at a very low computational cost. Inspired by signal analysis, we compute hybrid transforms of Euler characteristic profiles. These integral transforms mix Euler characteristic techniques with Lebesgue integration to provide highly efficient compressors of topological signals. As a consequence, they show remarkable performances in unsupervised settings. On the qualitative side, we provide numerous heuristics on the topological and geometric information captured by Euler profiles and their hybrid transforms. Finally, we prove stability results for these descriptors as well as asymptotic guarantees in random settings.

Authors: Tobias Weber

We present the free and open source software TAS-Paths, a novel system which calculates optimal, collision-free paths for the movement of triple-axis spectrometers. The software features an easy to use graphical user interface, but can also be scripted and used as a library. It allows the user to plan and visualise the motion of the instrument before the experiment and can be used during measurements to circumvent obstacles. The instrument path is calculated in angular configuration space in order to keep a maximum angular distance from any obstacle.

Authors: Vitaliy Kurlin

A finite set of unlabelled points in Euclidean space is the simplest representation of many real objects from mineral rocks to sculptures. Since most solid objects are rigid, their natural equivalence is rigid motion or isometry maintaining all inter-point distances. More generally, any finite metric space is an example of a metric-measure space that has a probability measure and a metric satisfying all axioms.

This paper develops Simplexwise Distance Distributions (SDDs) for any finite metric spaces and metric-measures spaces. These SDDs classify all known non-equivalent spaces that were impossible to distinguish by simpler invariants. We define metrics on SDDs that are Lipschitz continuous and allow exact computations whose parametrised complexities are polynomial in the number of given points.

Authors: Mohammad Pedramfar, Vaneet Aggarwal

This paper investigates the problem of combinatorial multiarmed bandits with stochastic submodular (in expectation) rewards and full-bandit delayed feedback, where the delayed feedback is assumed to be composite and anonymous. In other words, the delayed feedback is composed of components of rewards from past actions, with unknown division among the sub-components. Three models of delayed feedback: bounded adversarial, stochastic independent, and stochastic conditionally independent are studied, and regret bounds are derived for each of the delay models. Ignoring the problem dependent parameters, we show that regret bound for all the delay models is $\tilde{O}(T^{2/3} + T^{1/3} \nu)$ for time horizon $T$, where $\nu$ is a delay parameter defined differently in the three cases, thus demonstrating an additive term in regret with delay in all the three delay models. The considered algorithm is demonstrated to outperform other full-bandit approaches with delayed composite anonymous feedback.

Authors: Saeyoung Rho, Rachel Cummings, Vishal Misra

Synthetic control is a causal inference tool used to estimate the treatment effects of an intervention by creating synthetic counterfactual data. This approach combines measurements from other similar observations (i.e., donor pool ) to predict a counterfactual time series of interest (i.e., target unit) by analyzing the relationship between the target and the donor pool before the intervention. As synthetic control tools are increasingly applied to sensitive or proprietary data, formal privacy protections are often required. In this work, we provide the first algorithms for differentially private synthetic control with explicit error bounds. Our approach builds upon tools from non-private synthetic control and differentially private empirical risk minimization. We provide upper and lower bounds on the sensitivity of the synthetic control query and provide explicit error bounds on the accuracy of our private synthetic control algorithms. We show that our algorithms produce accurate predictions for the target unit, and that the cost of privacy is small. Finally, we empirically evaluate the performance of our algorithm, and show favorable performance in a variety of parameter regimes, as well as providing guidance to practitioners for hyperparameter tuning.

Authors: Marco Gaido

In the big data era, the key feature that each algorithm needs to have is the possibility of efficiently running in parallel in a distributed environment. The popular Silhouette metric to evaluate the quality of a clustering, unfortunately, does not have this property and has a quadratic computational complexity with respect to the size of the input dataset. For this reason, its execution has been hindered in big data scenarios, where clustering had to be evaluated otherwise. To fill this gap, in this paper we introduce the first algorithm that computes the Silhouette metric with linear complexity and can easily execute in parallel in a distributed environment. Its implementation is freely available in the Apache Spark ML library.

    Homepage    Code    Paper

In our latest paper, we revisit the problem of data attribution and introduce TRAK—a scalable and effective method for attributing machine learning predictions to training data. TRAK achieves dramatically better speed-efficacy tradeoffs than prior methods, allowing us to apply it across a variety of settings, from image classifiers to language models.

As machine learning models become more capable (and simultaneously, more complex and opaque), the question of “why did my model make this prediction?” is becoming increasingly important. And the key to answering this question often lies within the data that the model was trained on.

Consequently, there’s been a lot of interest in (and work on) data attribution: how do you attribute a given prediction back to the individual data points in the training set?

Data attribution methods help us understand how the composition of the training data impacts model predictions. In particular, these methods have been shown to be useful for variety of downstream applications, such as identifying brittle model predictions, assigning data valuations, detecting mislabeled data, and comparing learning algorithms, among many others.

What is a data attribution method, exactly? One way to define a data attribution method is as a function that takes in a specific example $z$ and outputs a set of scores (one per training example) that denote the “importance” of each training example to a model’s prediction on $z$. In the context of image classification model, an example output of a data attribution method could look like this:

Prior works on data attribution, such as influence functions, Shapley values, empirical influences, and datamodels, all fit naturally into this definition.

Now, given all these data attribution methods and their various uses, what’s the need for yet another one?

Two desiderata for data attribution

There are two natural dimensions along which we’d want to evaluate data attribution methods: efficacy and speed.

• Efficacy: We want methods that provide data attributions that are reliable and faithful to the model’s decision process. (We’ll make this more precise soon.)
• Speed: At the same time, we’d like methods that are going to scale. Indeed, the ever-increasing scale of models and datasets makes only data attribution methods with a (very) modest dependence on model and dataset size practical.

Evaluating speed is pretty straightforward: we can just use wall-clock time In our paper, we also consider an implementation-agnostic metric that still leads to the same conclusions. on a single A100 as a measure of speed.

Evaluating efficacy, on the other hand, turns out to be somewhat tricky. Indeed, when we look at prior works, there is no unifying metric, and many works rely on qualitative heuristics such as visual inspection or proxies such as the recall rate for identifying mislabelled examples.

So how should one evaluate the efficacy of data attribution methods? Well, Inspired by our earlier work on this topic, we adopt the perspective that the overarching goal of data attribution is to make accurate counterfactual predictions: e.g., answers to questions of the form “what would happen to this prediction if a given set images were removed from the training set”?

To capture this intuition, in our paper, we propose measuring efficacy with a new metric that we call linear datamodeling score (or LDS), which measures this predictiveness as a single value between zero and one Intuitively, when LDS=1, it means that the corresponding method can perfectly predict model behavior given only the examples are included in the training set. .

Efficacy vs. Speed tradeoffs

With the above metrics in hand, let’s take a look at existing data attribution methods:

As we can see, attaining both efficacy and speed is a challenge for all data attribution methods that we evaluated—there’s nothing in the top left corner!

Indeed, on one hand, resampling-based methods (the green and purple points in the top right) are very effective, but also very costly. After all, these method requires re-training the model many times—and while this might be feasible when we’re studying ResNets on CIFAR-10 or ImageNet, it’s unclear what to do when studying models like CLIP or GPT-N on datasets like Open Images or Common Crawl.

On the other hand, there are methods like influence functions or TracIn that are fast but not very effective (they fall into the bottom left part of the above plot). Fundamentally, this is because the approximations made by these methods don’t quite capture the structure of complex models such as deep neural networks.

The above results raise the question:

Do we really have to pay such a heavy price for accurate data attribution?

TRAK: Effective, efficient data attribution

In our new paper, we introduce TRAK (Tracing with the Randomly-Projected After Kernel), a new data attribution that significantly improves upon existing tradeoffs between efficacy and speed in data attribution.

We’ll leave the math to the paper, but the principle behind TRAK is quite simple: we approximate the model of interest with an instance of kernel regression (using the so-called “after kernel”); we randomly project the corresponding features to a lower-dimensional space; and then we apply (known) heuristics for data attributions in the kernel regression regime to perform data attribution on the original model.

Here is our previous plot with TRAK added to it (note the x axis scale!):

As we can see, TRAK fares pretty well here: it is 100x faster than models of comparable efficacy, and (at least) 10x more effective than models of comparable speed. As an example: for BERT models finetuned on the QNLI dataset, TRAK scores computed in just 17 hours on a single A100 GPU are more effective than re-training based datamodels computed in 125 GPU-days. TRAK is also significantly more effective than comparably fast methods, such as influence function-based methods or TracIn.

Applying TRAK across models and modalities

TRAK applies out-of-the-box to a wide variety of machine learning problems—including across modalities (e.g. language & vision among others), architectures (e.g. CNNs, Transformers, etc) and tasks (classification, contrastive learning, question answering, etc).

In our paper, we apply TRAK to ResNets trained on CIFAR and ImageNet, BERT-base models trained on QNLI, CLIP models trained on MS COCO, and mT5 models fine-tuned on a fact tracing benchmark. In each of these applications, we show that TRAK is significantly more effective at counterfactual prediction than existing baselines.

Next, we’ll take a closer look at two of such applications: CLIP, and (transformer-based) language models—two families of models that have become very popular and useful in the last few years.

Application #1: Attributing CLIP

CLIP (Contrastive Langauge-Image Pre-training) representations are a powerful tool for translating between vision and language domains. State-of-the-art CLIP models are trained on gigantic datasets of image-caption pairs, and properties of the training datasets seem to play a big role in the quality of the resulting representations.

But which training examples actually play the key roles in learning a given image-caption pair association? We can use TRAK to study this question. Below, for a few different image-caption pairs, we show the top training examples identified by TRAK:

You can see that nearest neighbors identified both by TRAK and by the CLIP representations themselves are semantically similar to the target images. But good attribution is more than just finding similar examples—they must actually be important to how the model makes decisions.

To evaluate this, we first, for each image-caption pair we remove the $k=400$ examples with the most positive TRAK scores; train a new CLIP model on the rest of the training set; and measure the model’s alignment (in terms of cosine similarity) on the image-caption pair being studied. The resulting models are on average 36% less aligned on the corresponding image-caption pairs. Even with removing just $k=50$ examples, you can see that the cosine similarity degrades quite a bit (a 16% drop).

Now, if we do the same but instead remove the most similar examples according to CLIP (or remove similar examples according to TracIn, an existing data attribution method), the resulting drop in cosine similarity is much less profound: compare 36% from TRAK to 11% for CLIP representations and 4% for TracIn scores, respectively.

TRAK thus identifies training examples that are counterfactually importantWhile we only studied the above counterfactual question in our paper, we think that our results open the door to many interesting questions---e.g., Can we find a much smaller subset of LAION-7B that will get us similar embeddings?!

Application #2: TRAK for Model-Faithful Fact Tracing

Next, we look at another application of TRAK that we found to be particularly interesting: the problem of fact tracing. That is, tracing factual assertions made by a language model back to corresponding data sources in the training set expressing those facts.

Specifically, we applied TRAK to a fact-tracing benchmark called FTRACE-TRex. Briefly, the goal of this benchmark is to identify the data sources responsible for a given fact expressed by a large language model.

The test set of FTRACE-TRex is a set of “queries”. Each query pertains to a particular fact, and is annotated with a set of “ground-truth proponent” training examples that express the same fact. So if “Paris is the capital of France” was a test set query, its ground-truth proponents in the training set might include, say,

1. “The capital of France is Paris,”
2. “The beautiful capital city of Paris, France, comes alive at night,”
3. “Paris, France is one of the busiest capital cities in Europe”

The FTRACE-TRex benchmark captures a data attribution method’s ability to surface these ground-truth proponents as the “most important” training examples for their corresponding queries. (That is, a good data attribution method should assign high scores to a query’s ground-truth proponents, relative to the rest of the training set.)

To our surprise, TRAK, while outperforming the previous best data attribution method (TracIn) on this task, did worse on this benchmark than a simple information-retrieval baseline (BM25)—this baseline is based only on the lexical overlap between the query and the possible data sources, and doesn’t even look at the model at all!

To understand the possible roots of TRAK’s underperformance here, we carried out a counterfactual analysis. What we found was that when we removed the training examples that TRAK identified as the most important (despite these being the “wrong” ones according to the FTRACE-TRex benchmark), the model was indeed less likely to express the corresponding facts. More crucially, though, this effect was actually stronger when we removed TRAK-identified examples than when we removed BM25-identified examples, and even stronger than when we removed the ground-truth primary sources!

We’ll leave the details of our experiment to the paper, but our result highlights a difference between “fact tracing” and data attribution (which might be more appropriately called “behavior tracing”). That is, finding a data source that factually supports a language model’s output is a different task than identifying the actual data sources that caused the model to generate that output. One might try to solve the former task with techniques such as information retrieval or web search (to “cite” sources). But the latter task is fundamentally one that cannot be decoupled from the model—and TRAK seems to be a promising approach here.

More broadly, we think that TRAK can be a useful tool in getting a more data-driven understanding of learning mechanisms underlying LLMs.

Attributing with TRAK: The PyTorch API

With the evaluation and examples above, hopefully we made a case that TRAK can be an effective and efficient data attribution method. But what does it take to apply it to your task?

We made sure that using TRAK is as easy as possible. To this end, we’re releasing trak as a fastFor our engineering-oriented reader: this involved writing a custom CUDA kernel for fast random projections, to avoid materializing a random matrix with billions of entries., minimal PyTorch-based API that allows users to compute TRAK scores with just a few lines of code:

We provide built-in TRAK functions for popular applications such as analyzing image classifiers, CLIP models, and text classifiers. The API also makes it easy to adapt TRAK for new, custom tasks.

You can get started with installation here. See our code and documentation, as well as tutorials and examples for more details.

Conclusion

In this post, we considered the problem of data attribution—i.e., tracing the behavior of machine learning models back to their training data. Our new method, TRAK, can provide attributions that are accurate and orders of magnitude more efficient than comparably effective methods.

Prior works have already shown the wide utility and potential of data attribution methods, including explaining predictions, debugging model behavior, assigning data valuations, and filtering or optimizing data. But, the main bottleneck in deploying these methods was their lack of scalability or predictiveness in modern settings. We believe that TRAK significantly reduces that bottleneck and that using TRAK in these downstream applications will accelerate and unlock many new capabilities, particularly in settings where training is very expensive, such as large language models.

We are excited about the possibilities enabled by TRAK. See the paper for more details, or get started right away applying TRAK to your problem with our library!

A great teacher and a great leader

Bill Wulf just passed away. We send our best thoughts to his dear wife Anita Jones and the rest of his family. He is greatly missed.

From the UVa obit: This image was algorithmically composed of more than 2,000 photos to illustrate Wulf’s influence on computer science, engineering and the University of Virginia.

CMU

Wulf started his great career as a faculty at CMU in 1968. He earned the first Ph.D. from the University of Virginia in the then newly founded Department of Applied Mathematics and Computer Science.

I met him after I started at CMU as a graduate student. He taught one of the required classes that I took. I still recall his ability to lecture on systems—an area that I did not expect to work in—it is not theory. But I recall his ability to explain and get us to be excited about systems. Thanks Bill.

Beyond CMU

Wulf had several impacts on CS. In 1970, when compiler technology was arguably only a dozen years old, he pioneered methods of optimizing the object code. He wrote a book about this titled, The Design of an Optimizing Compiler. He and Anita created the startup Tartan Laboratories with John Nestor to channel compiler optimization, especially for the then-new Ada programming language. Guy Steele is among several notable former employees of Tartan.

Wulf was elected to NAE in 1993 “for professional leadership and for contributions to programming systems and computer architecture”. He then served as NAE president from 1996 to 2007. He helped guide the NAE and get it redirected and made it a better organization.

He also did a famous job of resigning from the University of Virginia to protest the recent conduct of the UVa Board of Visitors in removing President Teresa Sullivan.

See this for the original news and his appeal, I urge my fellow faculty to join me. The links from that page are unrecoverable, but see this article in the Washington Post, which quotes his entire statement on why he refused to change his mind even after Sullivan was reinstated.

Open Problems

Again we thanks Wulf for his work that helped make CS a better place. He will be missed.

By rjlipton