Theory of Computing Report

July 25 – August 31, 2024 Chicago, IL https://focs.computer.org/2024/call-for-workshops/ Submission deadline: August 22, 2024 We invite proposals for five hour workshops to be held on the first day of FOCS 2024 (Oct 27 2024) to be held in Chicago. The proposal are supposed to be short (two pages max) and describe a plan for talks … Continue reading Call for Workshops at FOCS 2024

By shacharlovett

The Fulkerson prize is given to: outstanding papers in the area of discrete mathematics and is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of \$1,500 each are presented at each (triennial) International Symposium of the MOS.

This year:

* Ben Cousins and Santosh Vempala for Gaussian cooling and $O^{*}(n^{3})$ algorithms for volume and Gaussian volume.

* Zilin Jiang, Jonathan Tidor, Yuan Yao, Shengtong Zhang, and Yufei Zhao for Equiangular lines with a fixed angle.

* Nathan Keller and Noam Lifshitz for The junta method for hypergraphs and the Erdos—Chvatal simplex conjecture.

Originally, the prizes were paid out of a memorial fund administered by the AMS that was established by friends of the late Delbert Ray Fulkerson (1924-1976) to encourage mathematical excellence in the fields of research exemplified by his work.

Previous Prizes

1979:

* Richard M. Karp for classifying many important NP-complete problems.

* Kenneth Appel and Wolfgang Haken for the four color theorem.

* Paul Seymour for generalizing the max-flow min-cut theorem to matroids.

1982:

* D.B. Judin, Arkadi Nemirovski, Leonid Khachiyan, Martin Grotschel, Laszlo Lovasz and Alexander Schrijver for the ellipsoid method in linear programming and combinatorial optimization.

* G. P. Egorychev and D. I. Falikman for proving van der Waerden’s conjecture that the matrix with all entries equal has the smallest permanent of any doubly stochastic matrix.

1985:

* Jozsef Beck for tight bounds on the discrepancy of arithmetic progressions.

* H. W. Lenstra Jr. for using the geometry of numbers to solve integer programs with few variables in time polynomial in the number of constraints.

* Eugene M. Luks for a polynomial time graph isomorphism algorithm for graphs of bounded maximum degree.

1988:

* Eva Tardos for finding minimum cost circulations in strongly polynomial time.

* Narendra Karmarkar for Karmarkar’s algorithm for linear programming.

1991:

* Martin E. Dyer, Alan M. Frieze and Ravindran Kannan for random-walk-based approximation algorithms for the volume of convex bodies.

* Alfred Lehman for 0,1-matrix analogues of the theory of perfect graphs.

* Nikolai E. Mnev for Mnev’s universality theorem, that every semialgebraic set is equivalent to the space of realizations of an oriented matroid.

1994:

* Louis Billera for finding bases of piecewise-polynomial function spaces over triangulations of space.

* Gil Kalai for making progress on the Hirsch conjecture by proving subexponential bounds on the diameter of d-dimensional polytopes with n facets.

* Neil Robertson, Paul Seymour and Robin Thomas for the six-color case of Hadwiger’s conjecture.

1997:

* Jeong Han Kim for finding the asymptotic growth rate of the Ramsey numbers R(3,t).

2000:

* Michel X. Goemans and David P. Williamson for approximation algorithms based on semidefinite programming.

* Michele Conforti, Gerard Cornuejols, and M. R. Rao for recognizing balanced 0-1 matrices in polynomial time.

2003:

* J. F. Geelen, A. M. H. Gerards and A. Kapoor for the GF(4) case of Rota’s conjecture on matroid minors.

*Bertrand Guenin for a forbidden minor characterization of the weakly bipartite graphs (graphs whose bipartite subgraph polytope is 0-1).

*Satoru Iwata, Lisa Fleischer, Satoru Fujishige, and Alexander Schrijver for showing submodular minimization to be strongly polynomial.

2006:

* Manindra Agrawal, Neeraj Kayal and Nitin Saxena, for the AKS primality test.

* Mark Jerrum, Alistair Sinclair and Eric Vigoda, for approximating the permanent.

* Neil Robertson and Paul Seymour, for the Robertson—Seymour theorem showing that graph minors form a well-quasi-ordering.

2009:

* Maria Chudnovsky, Neil Robertson, Paul Seymour, and Robin Thomas, for the strong perfect graph theorem.

* Daniel A. Spielman and Shang-Hua Teng, for smoothed analysis of linear programming algorithms.

* Thomas C. Hales and Samuel P. Ferguson, for proving the Kepler conjecture on the densest possible sphere packings.

2012:

* Sanjeev Arora, Satish Rao, and Umesh Vazirani for improving the approximation ratio for graph separators and related problems

* Anders Johansson, Jeff Kahn, and Van H. Vu for determining the threshold of edge density above which a random graph can be covered by disjoint copies of a given smaller graph.

* Laszlo Lovasz and Balazs Szegedy for characterizing subgraph multiplicity in sequences of dense graphs.

2015:

* Francisco Santos Leal for a counter-example of the Hirsch conjecture.

2018:

* Robert Morris, Yoshiharu Kohayakawa, Simon Griffiths, Peter Allen, and Julia Bottcher for The chromatic thresholds of graphs

* Thomas Rothvoss for his work on the extension complexity of the matching polytope.

2021:

* Bela Csaba, Daniela Kuhn, Allan Lo, Deryk Osthus, and Andrew Treglown for Proof of the 1-factorization and Hamilton decomposition conjectures.

* Jin-Yi Cai and Xi Chen for Complexity of Counting CSP with Complex Weights.

*Ken-Ichi Kawarabayashi and Mikkel Thorup for Deterministic Edge Connectivity in Near-Linear Time.

Open Problems

Congrats to Ben and Santosh again. Wonderful.

By rjlipton

This is the final post about Paul Meehl’s course “Philosophical Psychology.” Here’s the full table of contents of my blogging through the class.

My friends, we find ourselves at the end of July and the end of Meehl Blogging. There is one more lecture in the series, but the video is corrupted, so it’s hard for me to figure out what to say. No matter, I think psychoanalysis makes for a fitting end, and I’m calling it there.

I’ve spent the last few days collecting my thoughts and pondering a coda. I don’t have a poetic summary just yet. I thought this blog series would take a few weeks, but it ended up consuming three months. I guess that’s a semester class! Maybe I can get course credit? Kidding aside, one of the great joys in life is taking a new class, learning new things, and completely reshaping how I think about a subject. It’s always good to remind myself this remains possible no matter how old I get.  But I’m going to have to take an incomplete on my term paper as I can’t do this course justice just yet.

Let me give a quick high-level take on my current estimation of my most valuable takeaways.

Lakatosian Defense. Meehl’s synthesis of 20th-century philosophy of science, what he calls metatheory, is better aligned with my views than anyone else I’ve encountered.  This “equation” that I’ve posted a dozen times has completely reshaped how I think about scientific evidence and argumentation.

Meehl pulls so many pieces together in this simple formulation: Popper, Duhem-Quine, Reichenbach, Salmon, Kuhn, Feyerabend, Lakatos. From this vantage point, you can tie the logical aspects to the social aspect. Deduction to induction. You can reconcile post-Latourian science studies with logical positivism. It’s a beautiful, elegant framing that pulled together so much of what I’ve been thinking about for the past half-decade.

The poverty of null hypothesis testing. Before engaging with these lectures, Meehl was one of my prime gotos for critiquing the tyranny of frequentist hypothesis testing. But hearing him talk about it helped me understand the broader context of his interest and the nuances of his critique. It’s wild how we torture ourselves with this broken inference framework. The Fisher, Neyman, and Pearson program from the 1930s is just broken. It isn’t fixable. But social conventions stick us with this, guaranteeing we will always be confused. These lectures highlight the absurdity of applying a Lakatosian strategy to understand social relations. It’s the wrong toolset and has led to nothing but widespread confusion and invasive bureaucratic kudzu. Let me not get stuck here again today… perhaps this will be the topic of my term paper.

Prediction is quantitative, inference is qualitative. The last three lectures on probability, prediction, and psychoanalytic inference, might have been the most valuable part of the class for me. Finally, for the first time in my career, I feel sure-footed about probability. I’m serious. Once you realize that Carnap’s Probability 1 isn’t numbers, you can be more relaxed about the entire probabilistic endeavor. Statistical prediction is a powerful concept but has limited scope, no matter what the AGI dorks tell you. Probabilistic inference can be qualitative and still helpful for guiding the practice of inference. Meehl makes a compelling argument for a dappled world of probability. Quantifying the unknown is an art form and an ethos. It can never be rigorous. And that’s ok!

Why we’re stuck. Meehl’s 1989 complaints and critiques about science and research are depressingly similar to those science reformers complain about on Twitter today. You could make the case the problems were the same in 1970. Why did we get stuck? This is my favorite question about the history of science, and the answer seems to be non-scientific factors that scientists pretend they are isolated from—the Cold War, the American Empire, hyperfinancialization, computerization. We’ve lived in a time of unprecedented technological advancement and stagnation. Though unintentional, because he didn’t want the class filmed in the first place, Meehl’s lectures helped me get more appreciation about what has flourished, what has withered, and what we might want to do next.

More to come. In the meantime, I’d love to hear what you all took away. Let me know which parts you found most interesting, and which parts you most disagreed with.

And with that, I’m going to take a few weeks “off” to finish a few other writing projects. I may pop back in here if there’s something wrong on the internet, but I don’t have planned regular blogging until late August.

And that’s because late August is when the semester begins! This fall, I’m excited to blog about my class on Convex Optimization in the age of LLMs. This should make for an interesting blog project where I’ll try to digest a very mathematical and technical topic with as few equations as possible. It should be a fun mathematical communication experiment. I hope you’ll enjoy reading along.

Subscribe now

By Ben Recht

The input to the Tree Evaluation problem is a binary tree of height $h$ in which each internal vertex is associated with a function mapping pairs of $\ell$-bit strings to $\ell$-bit strings,and each leaf is assigned an $\ell$-bit string. The desired output is the value of the root, where the value of each internal node is defined by applying the corresponding function to the value of its children. A recent result of Cook and Mertz (ECCC, TR23-174) asserts that the Tree Evaluation problem can be solved in space $O(\ell+h\cdot \log\ell)$, where the input length is $\exp(\Theta(h+\ell))$. Building on our recent exposition of their result (ECCC, TR24-109), we now obtain an $o((h+\ell)\cdot \log(h+\ell))$ space bound. Specifically, we shave off an $\Theta(\log\log(h+\ell))$ factor. The improvement is obtained by improving the procedure of Cook and Mertz for a generalized tree evaluation problem that refers to $d$-ary trees. We then reduce the binary case to the $d$-ary case while cutting the height of the tree by a factor of $\log_2d$. (The main result reported in this memo was obtained by Manuel Stoeckl, a student at Dartmouth, half a year before us. Manuel felt that this result is a minor observation and did not find the time to write it down. He also declined our invitation to co-author this memo.)

Authors: Samuel Epstein

This paper looks at the intersection of algorithmic information theory and physics, namely quantum mechanics, thermodynamics, and black holes. We discuss theorems which characterize the barrier between the quantum world and the classical realm. The notion of a "semi-classical subspace" is introduced. The No Synchronization Law is detailed, which says separate and isolated physical systems evolving over time cannot have thermodynamic algorithmic entropies that are in synch. We look at future work involving the Kolmogorov complexity of black holes.

Authors: Christoph Berkholz, Moritz Lichter, Harry Vinall-Smeeth

We study the refutation complexity of graph isomorphism in the tree-like resolution calculus. Tor\'an and W\"orz (TOCL 2023) showed that there is a resolution refutation of narrow width $k$ for two graphs if and only if they can be distinguished in ($k+1$)-variable first-order logic (FO$^{k+1}$) and hence by a count-free variant of the $k$-dimensional Weisfeiler-Leman algorithm. While DAG-like narrow width $k$ resolution refutations have size at most $n^k$, tree-like refutations may be much larger. We show that there are graphs of order n, whose isomorphism can be refuted in narrow width $k$ but only in tree-like size $2^{\Omega(n^{k/2})}$. This is a supercritical trade-off where bounding one parameter (the narrow width) causes the other parameter (the size) to grow above its worst case. The size lower bound is super-exponential in the formula size and improves a related supercritical width versus tree-like size trade-off by Razborov (JACM 2016). To prove our result, we develop a new variant of the $k$-pebble EF-game for FO$^k$ to reason about tree-like refutation size in a similar way as the Prover-Delayer games in proof complexity. We analyze this game on a modified variant of the compressed CFI graphs introduced by Grohe, Lichter, Neuen, and Schweitzer (FOCS 2023). Using a recent improved robust compressed CFI construction of Janett, Nordstr\"om, and Pang (unpublished manuscript), we obtain a similar bound for width $k$ (instead of the stronger but less common narrow width) and make the result more robust.

Authors: Marcus Schaefer, Jean Cardinal, Tillmann Miltzow

We survey the complexity class $\exists \mathbb{R}$, which captures the complexity of deciding the existential theory of the reals. The class $\exists \mathbb{R}$ has roots in two different traditions, one based on the Blum-Shub-Smale model of real computation, and the other following work by Mn\"{e}v and Shor on the universality of realization spaces of oriented matroids. Over the years the number of problems for which $\exists \mathbb{R}$ rather than NP has turned out to be the proper way of measuring their complexity has grown, particularly in the fields of computational geometry, graph drawing, game theory, and some areas in logic and algebra. $\exists \mathbb{R}$ has also started appearing in the context of machine learning, Markov decision processes, and probabilistic reasoning. We have aimed at collecting a comprehensive compendium of problems complete and hard for $\exists \mathbb{R}$, as well as a long list of open problems. The compendium is presented in the third part of our survey; a tour through the compendium and the areas it touches on makes up the second part. The first part introduces the reader to the existential theory of the reals as a complexity class, discussing its history, motivation and prospects as well as some technical aspects.

Authors: Tim Randolph, Karol Węgrzycki

We study the parameterized complexity of algorithmic problems whose input is an integer set $A$ in terms of the doubling constant $C := |A + A|/|A|$, a fundamental measure of additive structure. We present evidence that this new parameterization is algorithmically useful in the form of new results for two difficult, well-studied problems: Integer Programming and Subset Sum. First, we show that determining the feasibility of bounded Integer Programs is a tractable problem when parameterized in the doubling constant. Specifically, we prove that the feasibility of an integer program $I$ with $n$ polynomially-bounded variables and $m$ constraints can be determined in time $n^{O_C(1)} poly(|I|)$ when the column set of the constraint matrix has doubling constant $C$. Second, we show that the Subset Sum and Unbounded Subset Sum problems can be solved in time $n^{O_C(1)}$ and $n^{O_C(\log \log \log n)}$, respectively, where the $O_C$ notation hides functions that depend only on the doubling constant $C$. We also show the equivalence of achieving an FPT algorithm for Subset Sum with bounded doubling and achieving a milestone result for the parameterized complexity of Box ILP. Finally, we design near-linear time algorithms for $k$-SUM as well as tight lower bounds for 4-SUM and nearly tight lower bounds for $k$-SUM, under the $k$-SUM conjecture. Several of our results rely on a new proof that Freiman's Theorem, a central result in additive combinatorics, can be made efficiently constructive. This result may be of independent interest.

Authors: Thierry Lecroq, Francesco Pio Marino

Computing regularities in strings is essential for a better understanding of their structures. Among regularities, periods and covers are the easiest to compute and the more informative. Lately new interesting string matching results have been achieved using different sampling techniques. One of these technique, called Character-Distance-Sampling (\texttt{CDS}) consists of representing a string by storing the distance between the positions of selected characters called pivots. Here we select as pivots only the first character of the string and use its \texttt{CDS} representation for computing its period and its shortest cover. Experimental results show that the proposed methods are much faster than classical methods for computing these two features.

Authors: Jonatan Frank, Andor Diera, David Richerby, Ansgar Scherp

A structural graph summary is a small graph representation that preserves structural information necessary for a given task. The summary is used instead of the original graph to complete the task faster. We introduce multi-view structural graph summaries and propose an algorithm for merging two summaries. We conduct a theoretical analysis of our algorithm. We run experiments on three datasets, contributing two new ones. The datasets are of different domains (web graph, source code, and news) and sizes; the interpretation of multi-view depends on the domain and are pay-level domains on the web, control vs.\@ data flow of the code, and news broadcasters. We experiment with three graph summary models: attribute collection, class collection, and their combination. We observe that merging two structural summaries has an upper bound of quadratic complexity; but under reasonable assumptions, it has linear-time worst-case complexity. The running time of merging has a strong linear correlation with the number of edges in the two summaries. Therefore, the experiments support the assumption that the upper bound of quadratic complexity is not tight and that linear complexity is possible. Furthermore, our experiments show that always merging the two smallest summaries by the number of edges is the most efficient strategy for merging multiple structural summaries.

Authors: Leyla Biabani, Ami Paz

The $k$-center problem is a central optimization problem with numerous applications for machine learning, data mining, and communication networks. Despite extensive study in various scenarios, it surprisingly has not been thoroughly explored in the traditional distributed setting, where the communication graph of a network also defines the distance metric. We initiate the study of the $k$-center problem in a setting where the underlying metric is the graph's shortest path metric in three canonical distributed settings: the LOCAL, CONGEST, and CLIQUE models. Our results encompass constant-factor approximation algorithms and lower bounds in these models, as well as hardness results for the bi-criteria approximation setting.

Authors: Masaru Kikuchi, Shunsuke Inenaga

The all-pairs suffix-prefix (APSP) problem is a classical problem in string processing which has important applications in bioinformatics. Given a set $\mathcal{S} = \{S_1, \ldots, S_k\}$ of $k$ strings, the APSP problem asks one to compute the longest suffix of $S_i$ that is a prefix of $S_j$ for all $k^2$ ordered pairs $\langle S_i, S_j \rangle$ of strings in $\mathcal{S}$. In this paper, we consider the dynamic version of the APSP problem that allows for insertions of new strings to the set of strings. Our objective is, each time a new string $S_i$ arrives to the current set $\mathcal{S}_{i-1} = \{S_1, \ldots, S_{i-1}\}$ of $i-1$ strings, to compute (1) the longest suffix of $S_i$ that is a prefix of $S_j$ and (2) the longest prefix of $S_i$ that is a suffix of $S_j$ for all $1 \leq j \leq i$. We propose an $O(n)$-space data structure which computes (1) and (2) in $O(|S_i| \log \sigma + i)$ time for each new given string $S_i$, where $n$ is the total length of the strings.

Authors: Ravi Kumar, Manish Purohit, Zoya Svitkina

In this work we study the problem of using machine-learned predictions to improve the performance of online algorithms. We consider two classical problems, ski rental and non-clairvoyant job scheduling, and obtain new online algorithms that use predictions to make their decisions. These algorithms are oblivious to the performance of the predictor, improve with better predictions, but do not degrade much if the predictions are poor.

Authors: Alessandro Epasto, Quanquan C. Liu, Tamalika Mukherjee, Felix Zhou

The graph continual release model of differential privacy seeks to produce differentially private solutions to graph problems under a stream of updates where new private solutions are released after each update. Streaming graph algorithms in the non-private literature also produce (approximately) accurate solutions when provided updates in a stream, but they additionally try to achieve two other goals: 1) output vertex or edge subsets as approximate solutions to the problem (not just real-valued estimates) and 2) use space that is sublinear in the number of edges or the number of vertices. Thus far, all previously known edge-differentially private algorithms for graph problems in the continual release setting do not meet the above benchmarks. Instead, they require computing exact graph statistics on the input [SLMVC18, FHO21, JSW24]. In this paper, we leverage sparsification to address the above shortcomings. Our edge-differentially private algorithms use sublinear space with respect to the number of edges in the graph while some also achieve sublinear space in the number of vertices in the graph. In addition, for most of our problems, we also output differentially private vertex subsets. We make novel use of assorted sparsification techniques from the non-private streaming and static graph algorithms literature and achieve new results in the sublinear space, continual release setting for a variety of problems including densest subgraph, $k$-core decomposition, maximum matching, and vertex cover. In addition to our edge-differential privacy results, we use graph sparsification based on arboricity to obtain a set of results in the node-differential privacy setting, illustrating a new connection between sparsification and privacy beyond minimizing space. We conclude with polynomial additive error lower bounds for edge-privacy in the fully dynamic setting.

Here is a great question invented by Michele Piccione and Ariel Rubinstein. (Let me use this opportunity to recommend their mind boggling 1997 paper on the absent-minded driver.)

The question (TYI 55)

The proportion of newborns with a specific genetic trait is 1%. Two conditionally independent screening tests, A and B, are used to identify this trait in all newborns. However, the tests are not precise. Specifically, it has been found that:

70% of the newborns who are found to be positive according to test A have the trait.
20% of the newborns who are found to be positive according to test B have the trait.

Suppose that a newborn is found to be positive according to both tests. What is your estimate of the probability that this newborn has the trait?

I will try to conduct a poll over Twitter (X). (It looks as it is no longer possible to have a poll over here.) Here is going to be the link to the twitter poll. (Seven days only.)

Michele Piccione and Ariel Rubinstein

Click here for the previous post on Christian Elsholtz, Zach Hunter, Laura Proske, and Lisa Sauermann’s remarkable improvement for Behrend’s construction.

I have a feeling that TYI55 has the potential to be a blockbuster like TYI30 on Mossel’s amazing dice problem.

The Very Short Poll

What is your estimate that the new born has the trait?

(Please give your answer (just the number) as a comment)

The Short Poll

What is your estimate that the new born has the trait

(i) Below 40%

(ii) Between 40% and 80%

(iii) Above 80%

On twitter

The Long Poll

What is your estimate that the new born has the trait

(a) 14%

(b) Above 14% but below 20%

(c) 20%

(d) Above 20% and below 45%

(e) 45%

(f) Above 45% below 70%

(g)  70%

(h) Above 70% below 76%

(i) 76%

(j) Above 76% below 94%

(k) 94%

(l) Above 94%

(If twitter will support it I will also post this long poll on twitter.)

_______________________________

Here (a) is the product of the two probabilities ; (c) is the minimum; (e) is the average; (g) is the maximum; and (i) is one minus the product of the complemented probabilities .

_______________________________

After you tested your own intuition, here is the link to Michele and Ariel’s paper. Failing to Correctly Aggregate Signals, Michele Piccione and Ariel Rubinstein  pdf

By Gil Kalai

Authors: Kapil Goswami, Gagan Anekonda Veereshi, Peter Schmelcher, Rick Mukherjee

The travelling salesman problem (TSP) is a popular NP-hard-combinatorial optimization problem that requires finding the optimal way for a salesman to travel through different cities once and return to the initial city. The existing methods of solving TSPs on quantum systems are either gate-based or binary variable-based encoding. Both approaches are resource-expensive in terms of the number of qubits while performing worse compared to existing classical algorithms even for small-size problems. We present an algorithm that solves an arbitrary TSP using a single qubit by invoking the principle of quantum parallelism. The cities are represented as quantum states on the Bloch sphere while the preparation of superposition states allows us to traverse multiple paths at once. The underlying framework of our algorithm is a quantum version of the classical Brachistochrone approach. Optimal control methods are employed to create a selective superposition of the quantum states to find the shortest route of a given TSP. The numerical simulations solve a sample of four to nine cities for which exact solutions are obtained. The algorithm can be implemented on any quantum platform capable of efficiently rotating a qubit and allowing state tomography measurements. For the TSP problem sizes considered in this work, our algorithm is more resource-efficient and accurate than existing quantum algorithms with the potential for scalability. A potential speed-up of polynomial time over classical algorithms is discussed.

Authors: Seiji Shaw, Aidan Curtis, Leslie Pack Kaelbling, Tomás Lozano-Pérez, Nicholas Roy

When using sampling-based motion planners, such as PRMs, in configuration spaces, it is difficult to determine how many samples are required for the PRM to find a solution consistently. This is relevant in Task and Motion Planning (TAMP), where many motion planning problems must be solved in sequence. We attempt to solve this problem by proving an upper bound on the number of samples that are sufficient, with high probability, to find a solution by drawing on prior work in deterministic sampling and sample complexity theory. We also introduce a numerical algorithm to compute a tighter number of samples based on the proof of the sample complexity theorem we apply to derive our bound. Our experiments show that our numerical bounding algorithm is tight within two orders of magnitude on planar planning problems and becomes looser as the problem's dimensionality increases. When deployed as a heuristic to schedule samples in a TAMP planner, we also observe planning time improvements in planar problems. While our experiments show much work remains to tighten our bounds, the ideas presented in this paper are a step towards a practical sample bound.

Authors: Michele Barbato, Alberto Ceselli, Rosario Messana

We consider the following problem in computational geometry: given, in the d-dimensional real space, a set of points marked as positive and a set of points marked as negative, such that the convex hull of the positive set does not intersect the negative set, find K hyperplanes that separate, if possible, all the positive points from the negative ones. That is, we search for a convex polyhedron with at most K faces, containing all the positive points and no negative point. The problem is known in the literature for pure convex polyhedral approximation; our interest stems from its possible applications in constraint learning, where points are feasible or infeasible solutions of a Mixed Integer Program, and the K hyperplanes are linear constraints to be found. We cast the problem as an optimization one, minimizing the number of negative points inside the convex polyhedron, whenever exact separation cannot be achieved. We introduce models inspired by support vector machines and we design two mathematical programming formulations with binary variables. We exploit Dantzig-Wolfe decomposition to obtain extended formulations, and we devise column generation algorithms with ad-hoc pricing routines. We compare computing time and separation error values obtained by all our approaches on synthetic datasets, with number of points from hundreds up to a few thousands, showing our approaches to perform better than existing ones from the literature. Furthermore, we observe that key computational differences arise, depending on whether the budget K is sufficient to completely separate the positive points from the negative ones or not. On 8-dimensional instances (and over), existing convex hull algorithms become computational inapplicable, while our algorithms allow to identify good convex hull approximations in minutes of computation.

Authors: James Davies, Yelena Yuditsky

We prove that for every positive integer $d$ and forest $F$, the class of intersection graphs of axis-aligned boxes in $\mathbb{R}^d$ with no induced $F$ subgraph is (polynomially) $\chi$-bounded.

Authors: Maximilian Brock, Martin Brückmann, Elmar Langetepe, Raphael Wude

Due to some significantly contradicting research results, we reconsider the problem of the online exploration of a simple grid cell environment. In this model an agent attains local information about the direct four-neigbourship of a current grid cell and can also successively build a map of all detected cells. Beginning from a starting cell at the boundary of the environment, the agent has to visit any cell of the grid environment and finally has to return to its starting position. The performance of an online strategy is given by competitive analysis. We compare the number of overall cell visits (number of steps) of an online strategy to the number of such visits in the optimal offline solution under full information of the environment in advance. The corresponding worst-case ratio gives the competitive ratio. The aforementioned contradiction among two publications turns out to be as follows: There is a journal publication that claims to present an optimal competitive strategy with ratio 7/6 and a former conference paper that presents a lower bound of 20/17. In this note we extract the flaw in the upper bound and also present a new slightly improved and (as we think) simplified general lower bound of 13/11.

Authors: Paul Bastide

In the distance query model, we are given access to the vertex set of a $n$-vertex graph $G$, and an oracle that takes as input two vertices and returns the distance between these two vertices in $G$. We study how many queries are needed to reconstruct the edge set of $G$ when $G$ is sampled according to the $G(n,p)$ Erd\H{o}s-Renyi-Gilbert distribution. Our approach applies to a large spectrum of values for $p$ starting slightly above the connectivity threshold: $p \geq \frac{2000 \log n}{n}$. We show that there exists an algorithm that reconstructs $G \sim G(n,p)$ using $O( \Delta^2 n \log n )$ queries in expectation, where $\Delta$ is the expected average degree of $G$. In particular, for $p \in [\frac{2000 \log n}{n}, \frac{\log^2 n}{n}]$ the algorithm uses $O(n \log^5 n)$ queries.

Authors: Sabyasachi Basu, Daniel Paul-Pena, Kun Qian, C. Seshadhri, Edward W Huang, Karthik Subbian

Graphs are a fundamental data structure used to represent relationships in domains as diverse as the social sciences, bioinformatics, cybersecurity, the Internet, and more. One of the central observations in network science is that real-world graphs are globally sparse, yet contains numerous "pockets" of high edge density. A fundamental task in graph mining is to discover these dense subgraphs. Most common formulations of the problem involve finding a single (or a few) "optimally" dense subsets. But in most real applications, one does not care for the optimality. Instead, we want to find a large collection of dense subsets that covers a significant fraction of the input graph. We give a mathematical formulation of this problem, using a new definition of regularly triangle-rich (RTR) families. These families capture the notion of dense subgraphs that contain many triangles and have degrees comparable to the subgraph size. We design a provable algorithm, RTRExtractor, that can discover RTR families that approximately cover any RTR set. The algorithm is efficient and is inspired by recent results that use triangle counts for community testing and clustering. We show that RTRExtractor has excellent behavior on a large variety of real-world datasets. It is able to process graphs with hundreds of millions of edges within minutes. Across many datasets, RTRExtractor achieves high coverage using high edge density datasets. For example, the output covers a quarter of the vertices with subgraphs of edge density more than (say) $0.5$, for datasets with 10M+ edges. We show an example of how the output of RTRExtractor correlates with meaningful sets of similar vertices in a citation network, demonstrating the utility of RTRExtractor for unsupervised graph discovery tasks.

Invited Speaker Nutan Limaye, Conference Chair Valentine Kabanets, 2024 PC Chair Rahul Santhanam, myself, 2025 PC Chair Srikanth Srinivasan and 2025 Local Arrangements chair Swastik Kopparty enjoy some tapas.

I have a long history with the Computational Complexity conference. I attended the first 26 meetings (1996-2011) and 30 of the first 31. I chaired the conference committee from 2000-2006. According to DBLP I still have the most papers appearing in the conference (32). I even donated the domain name for the conference (with the caveat that I could keep the subdomain for this blog).

Only Eric Allender had a longer streak having attended the first 37 conferences through 2022 in Philadelphia (if you count the two online during the pandemic) before he retired.

But I haven't been back to Complexity since that 31st conference in Tokyo in 2016. Due to my administrative roles, various conflicts and changes in the field you just start missing conferences. But with the conference at the University of Michigan in Ann Arbor within driving distance of Chicago it was time to go home for the 39th meeting. And it's a good thing I drove as more than one person had flight delays due to the Crowdstrike bug.

The complexity conference remains relatively stable at about 75-100 registrants, the majority students and young researchers. I've moved from wise-old sage to who is that guy. But I'm having great fun talking to old acquaintances and new. I'm impressed with the newer generations of complexity theorists--the field is in good hands.

Best paper goes to Michael Forbes Low-Depth Algebraic Circuit Lower Bounds over Any Field. the work of Limaye, Srinivasan and Tavenas I talked about last month gave an explicit polynomials with superpolynomial-size over constant depth algebraic circuits but it required polynomials over large fields. Forbes extended the lower bounds to all field sizes.

Best student paper goes to Ted Pyne from MIT for Derandomizing Logspace with a Small Shared Hard Drive for showing how to reduce space for randomized log-space algorithms on catalytic machines.

Check out all the papers in the online proceedings.

From a relatively quiet business meeting: 36 papers accepted out of 104 submissions, a bit up from previous years. 75 attendees including 42 students, similar to recent years. 2025 conference at the Fields Institute in Toronto August 5-8. 2026 in Lisbon or Auckland.

The loss of Luca Trevisan, PC Chair 2005 and local arrangements chair in 2013 in San Jose, loomed large in the business meeting and at the conference.

By Lance Fortnow

Authors: Soumyadip Ghosh, Lior Horesh, Vassilis Kalantzis, Yingdong Lu, Tomasz Nowicki

This paper presents an extension of the classical Ulan-von Neumann Markov chain Monte-Carlo algorithm for the computation of the matrix inverse. The algorithm presented in this paper, termed as \emph{regenerative Ulam-von Neumann algorithm}, utilizes the regenerative structure of classical, non-truncated Neumann series defined by a non-singular matrix and produces an unbiased estimator of the matrix inverse. Furthermore, the accuracy of the proposed algorithm depends on a single parameter that controls the total number of Markov transitions simulated thus avoiding the challenge of balancing between the total number of Markov chain replications and its corresponding length as in the classical Ulam-von Neumann algorithm. To efficiently utilize the Markov chain transition samples in the calculation of the regenerative quantities, the proposed algorithm quantifies automatically the contribution of each Markov transition to all regenerative quantities by a carefully designed updating scheme that utilized three separate matrices containing the current weights, total weights, and regenerative cycle count, respectively. A probabilistic analysis of the performance of the algorithm, including the variance of the estimator, is provided. Finally, numerical experiments verify the qualitative effectiveness of the proposed scheme.

Authors: Eliot W. Robson, Jack Spalding-Jamieson, Da Wei Zheng

We investigate the problem of carving an $n$-face triangulated three-dimensional polytope using a tool to make cuts modelled by either a half-plane or sweeps from an infinite ray. In the case of half-planes cuts, we present a deterministic algorithm running in $O(n^2)$ time and a randomized algorithm running in $O(n^{3/2+\varepsilon})$ expected time for any $\varepsilon>0$. In the case of cuts defined by sweeps of infinite rays, we present an algorithm running in $O(n^5)$ time.

Authors: Dmitriy Kunisky, Daniel A. Spielman, Xifan Yu

We consider the problem of inferring an unknown ranking of $n$ items from a random tournament on $n$ vertices whose edge directions are correlated with the ranking. We establish, in terms of the strength of these correlations, the computational and statistical thresholds for detection (deciding whether an observed tournament is purely random or drawn correlated with a hidden ranking) and recovery (estimating the hidden ranking with small error in Spearman's footrule or Kendall's tau metric on permutations). Notably, we find that this problem provides a new instance of a detection-recovery gap: solving the detection problem requires much weaker correlations than solving the recovery problem. In establishing these thresholds, we also identify simple algorithms for detection (thresholding a degree 2 polynomial) and recovery (outputting a ranking by the number of "wins" of a tournament vertex, i.e., the out-degree) that achieve optimal performance up to constants in the correlation strength. For detection, we find that the above low-degree polynomial algorithm is superior to a natural spectral algorithm. We also find that, whenever it is possible to achieve strong recovery (i.e., to estimate with vanishing error in the above metrics) of the hidden ranking, then the above "Ranking By Wins" algorithm not only does so, but also outputs a close approximation of the maximum likelihood estimator, a task that is NP-hard in the worst case.

Authors: L. Sunil Chandran, Rishikesh Gajjala, Shravan Mehra, Saladi Rahul

The focus of this paper is to increase our understanding of the Longest Processing Time First (LPT) heuristic. LPT is a classical heuristic for the fundamental problem of uniform machine scheduling. For different machine speeds, LPT was first considered by Gonzalez et al (SIAM J. Computing, 1977). Since then, extensive work has been done to improve the approximation factor of the LPT heuristic. However, all known implementations of the LPT heuristic take $O(mn)$ time, where $m$ is the number of machines and $n$ is the number of jobs. In this work, we come up with the first near-linear time implementation for LPT. Specifically, the running time is $O((n+m)(\log^2{m}+\log{n}))$. Somewhat surprisingly, the result is obtained by mapping the problem to dynamic maintenance of lower envelope of lines, which has been well studied in the computational geometry community. Our second contribution is to analyze the performance of LPT for the Drones Warehouse Problem (DWP), which is a natural generalization of the uniform machine scheduling problem motivated by drone-based parcel delivery from a warehouse. In this problem, a warehouse has multiple drones and wants to deliver parcels to several customers. Each drone picks a parcel from the warehouse, delivers it, and returns to the warehouse (where it can also get charged). The speeds and battery lives of the drones could be different, and due to the limited battery life, each drone has a bounded range in which it can deliver parcels. The goal is to assign parcels to the drones so that the time taken to deliver all the parcels is minimized. We prove that the natural approach of solving this problem via the LPT heuristic has an approximation factor of $\phi$, where $\phi \approx 1.62$ is the golden ratio.

Authors: Elfarouk Harb, Zhengcheng Huang, Da Wei Zheng

We introduce a new balanced separator theorem for unit-disk graphs involving two shortest paths combined with the 1-hop neighbours of those paths and two other vertices. This answers an open problem of Yan, Xiang and Dragan [CGTA '12] and improves their result that requires removing the 3-hop neighborhood of two shortest paths. Our proof uses very different ideas, including Delaunay triangulations and a generalization of the celebrated balanced separator theorem of Lipton and Tarjan [J. Appl. Math. '79] to systems of non-intersecting paths.

Authors: Ahmed El Alaoui, David Gamarnik

We show that two related classes of algorithms, stable algorithms and Boolean circuits with bounded depth, cannot produce an approximate sample from the uniform measure over the set of solutions to the symmetric binary perceptron model at any constraint-to-variable density. This result is in contrast to the question of finding \emph{a} solution to the same problem, where efficient (and stable) algorithms are known to succeed at sufficiently low density. This result suggests that the solutions found efficiently -- whenever this task is possible -- must be highly atypical, and therefore provides an example of a problem where search is efficiently possible but approximate sampling from the set of solutions is not, at least within these two classes of algorithms.

Authors: Abhishek Dhawan

We present a simple $(1+\varepsilon)\Delta$-edge-coloring algorithm for graphs of maximum degree $\Delta = \Omega(\log n / \varepsilon)$ with running time $O\left(m\,\log^3 n/\varepsilon^3\right)$. Our algorithm improves upon that of [Duan, He, and Zhang; SODA19], which was the first near-linear time algorithm for this problem. While our results are weaker than the current state-of-the-art, our approach is significantly simpler, both in terms of analysis as well as implementation, and may be of practical interest.

Authors: Thomas Bellitto, Johanne Cohen, Bruno Escoffier, Minh-Hang Nguyen, Mikael Rabie

This paper formalises the Canadian Traveller problem as a positional two-player game on graphs. We consider two variants depending on whether an edge is blocked. In the locally-informed variant, the traveller learns if an edge is blocked upon reaching one of its endpoints, while in the uninformed variant, they discover this only when the edge is supposed to appear. We provide a polynomial algorithm for each shortest path variant in the uninformed case. This algorithm also solves the case of directed acyclic non-temporal graphs. In the locally-informed case, we prove that finding a winning strategy is PSPACE-complete. Moreover, we establish that the problem is polynomial-time solvable when $k=1$ but NP-hard for $k\geq 2$. Additionally, we show that the standard (non-temporal) Canadian Traveller Problem is NP-hard when there are $k\geq 4$ blocked edges, which is, to the best of our knowledge, the first hardness result for CTP for a constant number of blocked edges.

Authors: Roberto Bruno, Roberto De Prisco, Alfredo De Santis, Ugo Vaccaro

Alphabetic codes and binary search trees are combinatorial structures that abstract search procedures in ordered sets endowed with probability distributions. In this paper, we design new linear-time algorithms to construct alphabetic codes, and we show that the obtained codes are not too far from being optimal. Moreover, we exploit our results on alphabetic codes to provide new bounds on the average cost of optimal binary search trees. Our results improve on the best-known bounds on the average cost of optimal binary search trees present in the literature.

Authors: Roberto Bruno

Dimension reduction is a technique used to transform data from a high-dimensional space into a lower-dimensional space, aiming to retain as much of the original information as possible. This approach is crucial in many disciplines like engineering, biology, astronomy, and economics. In this paper, we consider the following dimensionality reduction instance: Given an n-dimensional probability distribution p and an integer m

Authors: Malte Luttermann, Johann Machemer, Marcel Gehrke

Lifted probabilistic inference exploits symmetries in probabilistic graphical models to allow for tractable probabilistic inference with respect to domain sizes. To exploit symmetries in, e.g., factor graphs, it is crucial to identify commutative factors, i.e., factors having symmetries within themselves due to their arguments being exchangeable. The current state of the art to check whether a factor is commutative with respect to a subset of its arguments iterates over all possible subsets of the factor's arguments, i.e., $O(2^n)$ iterations for a factor with $n$ arguments in the worst case. In this paper, we efficiently solve the problem of detecting commutative factors in a factor graph. In particular, we introduce the detection of commutative factors (DECOR) algorithm, which allows us to drastically reduce the computational effort for checking whether a factor is commutative in practice. We prove that DECOR efficiently identifies restrictions to drastically reduce the number of required iterations and validate the efficiency of DECOR in our empirical evaluation.

Authors: Nima Anari, Frederic Koehler, Thuy-Duong Vuong

Trickle-down is a phenomenon in high-dimensional expanders with many important applications -- for example, it is a key ingredient in various constructions of high-dimensional expanders or the proof of rapid mixing for the basis exchange walk on matroids and in the analysis of log-concave polynomials. We formulate a generalized trickle-down equation in the abstract context of linear-tilt localization schemes. Building on this generalization, we improve the best-known results for several Markov chain mixing or sampling problems -- for example, we improve the threshold up to which Glauber dynamics is known to mix rapidly in the Sherrington-Kirkpatrick spin glass model. Other applications of our framework include improved mixing results for the Langevin dynamics in the $O(N)$ model, and near-linear time sampling algorithms for the antiferromagnetic and fixed-magnetization Ising models on expanders. For the latter application, we use a new dynamics inspired by polarization, a technique from the theory of stable polynomials.

Authors: Benjamin Scheidt, Nicole Schweikardt

Color Refinement, also known as Naive Vertex Classification, is a classical method to distinguish graphs by iteratively computing a coloring of their vertices. While it is mainly used as an imperfect way to test for isomorphism, the algorithm permeated many other, seemingly unrelated, areas of computer science. The method is algorithmically simple, and it has a well-understood distinguishing power: It is logically characterized by Cai, F\"urer and Immerman (1992), who showed that it distinguishes precisely those graphs that can be distinguished by a sentence of first-order logic with counting quantifiers and only two variables. A combinatorial characterization is given by Dvo\v{r}\'ak (2010), who shows that it distinguishes precisely those graphs that can be distinguished by the number of homomorphisms from some tree. In this paper, we introduce Relational Color Refinement (RCR, for short), a generalization of the Color Refinement method from graphs to arbitrary relational structures, whose distinguishing power admits the equivalent combinatorial and logical characterizations as Color Refinement has on graphs: We show that RCR distinguishes precisely those structures that can be distinguished by the number of homomorphisms from an acyclic relational structure. Further, we show that RCR distinguishes precisely those structures that can be distinguished by a sentence of the guarded fragment of first-order logic with counting quantifiers.

This post digs into Lecture 11 of Paul Meehl’s course “Philosophical Psychology.” The video for Lecture 11 is here. Here’s the full table of contents of my blogging through the class.

The International Conference on Machine Learning is this week. So let me set today’s stage with an AI problem. Suppose I have a sequence of symbols that I model as generated by some semi-parametric process. My goal is to infer the latent state of that process. I can choose a set of actions to probe the system and see how the sequence changes. What is the optimal algorithm for inferring the latent state? 

I’m sure there’s some poster in Vienna1 right now that has this model in the abstract. They probably use LLMs or something. Whatever the case, this model is also Paul Meehl’s formulation of the psychoanalytic interview as a problem in inference.

The sequence in psychoanalysis is the words uttered by the patient. The latents are the repressed memories or emotions impinging on the observed utterances. The patient is talking about what they intend to talk about, but the therapist seeks to infer the latent sequence that is impacting unintentional parts of the monologue. There are pauses, blanks, and rate of speech that are all possibly caused by the latent stream. The therapist can occasionally interject to see if they can steer the conversation toward confirming their suspicions. Can the therapist infer the latents? The abstract model of psychoanalysis is a complex game of Bayesian inference with a clinical chatbot.

Meehl gives several examples of how such Bayesian-ish inferences work in psychoanalysis through his own case studies, and I can’t do them justice in a blog.  It’s worth watching the lecture to fully immerse yourself in the complexity and nuance. 

Sometimes, the examples are obvious. A woman drops her wedding ring in the toilet. She calls her husband by the wrong name. She has a headache after date night. While you could come up with lots of behavioral explanations for each of these events (acute clumsiness, temporary disassociation, food poisoning), a considerably simpler model is that one latent issue (insecurity about her marriage) explains the disconnected events.

Sometimes, especially when it comes to dream interpretation, the inferences are far more complex and entangled. Meehl describes linking a patient’s dream about a dying asian man to the cover of Time magazine featuring Burmese prime minister U Nu, which he linked to the patient being astounded and incensed by the sorts of deductions Meehl would make in therapy (“you knew!”), which he linked to the patient's general inferiority complexes for not finishing college.

The examples of Lecture 11 illustrate the craft of psychoanalysis. It needs a lot of training and skill to perform well. How can we evaluate if it works? Does it actually work to ameliorate mental health problems? Here is the main philosophy of science problem. Meehl was disappointed to say that, almost 100 years after Freud, no one knew the answer. Another four decades later, and I don’t think we have much more clarification. 

Mental health and therapy are certainly less stigmatized than they were in the 1980s. Such conditions and treatments are considered “real” and “scientific” by a large medical community. But psychodynamics remains part of the “less scientific” corner of mental health therapies, losing favor to more “testable” interventions like cognitive behavioral therapy and an army of pharmaceuticals. But do those therapies actually work better? Why do we think so?

You can’t deny that psychoanalysis is empirical. The protocols are based in observation and intervention. The case studies provide plenty of clear evidence. You could videotape sessions if you needed absolute concrete “evidence.” But the evidence is never quantitative. Even though therapists make inferences, they can’t convert psychoanalytic sessions into numbers. Probability 1, as we’ve discussed now, is barely quantitative. It might not be quantitative at all.

You can’t dismiss psychoanalysis on the basis of its inherent subjectivity. All Bayesian inference is subjective! Subjectivity is the foundation of the entire Bayesian statistics program. Is a sophisticated mathematical model of a patient’s utterances (say, a multi-plate latent Dirichlet model) less subjective than proposing they are impinged by an Oedipus complex? Of course not. Even the most radical millenarian rationalists commit to the inherent subjectivity of inference.

Perhaps you can say that adherents of psychoanalysis cherry pick the positive examples. Psychodynamic therapy can take years to work, and it’s hard to tabulate its success rates. Perhaps its effects are heterogeneous, where it only works for some people and not others. The entire enterprise could be resting on 100 years of motivated reasoning. But there are enough revelatory examples in talk therapy, examples where people’s anxieties vanish in a single session, to think that something is going on.

There’s such a sharp contrast between Lectures 10 and 11. In Lecture 10 we discussed problems with clear-cut outcomes and simple interventions. For these, we could just tabulate statistics and predict what to do. Everything reduced to simple probability calculations. Find the smallest reference classes with stable frequencies and use these frequencies as degrees of confidence about the future. We could tell a clean quantitative story and even outperform clinical judgment.

Psychoanalysis is the entire other end of the spectrum. It requires a highly trained analyst, multiple interactions over potentially long time horizons, open-ended decision-making with unclear and flexible rules, high subjectivity, and little quantification. You can do RCTs of psychodynamic therapy. Unsurprisingly, there aren’t that many of them, and the assembled evidence is inconclusive.

In our age of randomized trial-o-mania, treatments gain popularity solely because they can more easily survive randomized trialing. But, because I cannot say it enough times, randomized trials provide an impoverished view of causality. Simply measured interventions are rarer than we’d like them to be. Even if we know the effect of a single drug on some disease, we rarely have an evidence base for two drugs. What about actual clinical practice? There are so many complex protocols that aren’t easily RCTed. Coaching, tutoring, artistry, craftsmanship. We don’t need RCTs to know these skills work. RCTs and other quantitative experiments have their time and place, but it’s worth noting that we can find things that work without such rigid statistical dogma. 

The frustrating thing for many scientists is there will always be a fine line between math and metaphor. But mathematical metaphors untethered from quantification are undervalued. Being able to manipulate metaphors with mathematical poetry is a valuable means of understanding method. Mathematical metaphors can tell us what matters. They can tell us what doesn’t matter. They can simplify how we train clinicians. They can provide good heuristics for what we try next. They can help us understand what works.

Subscribe now

By Ben Recht

Authors: Sebastian Ordyniak, Giacomo Paesani, Mateusz Rychlicki, Stefan Szeider

This paper presents a comprehensive theoretical investigation into the parameterized complexity of explanation problems in various machine learning (ML) models. Contrary to the prevalent black-box perception, our study focuses on models with transparent internal mechanisms. We address two principal types of explanation problems: abductive and contrastive, both in their local and global variants. Our analysis encompasses diverse ML models, including Decision Trees, Decision Sets, Decision Lists, Ordered Binary Decision Diagrams, Random Forests, and Boolean Circuits, and ensembles thereof, each offering unique explanatory challenges. This research fills a significant gap in explainable AI (XAI) by providing a foundational understanding of the complexities of generating explanations for these models. This work provides insights vital for further research in the domain of XAI, contributing to the broader discourse on the necessity of transparency and accountability in AI systems.

Authors: Zohair Raza Hassan

Often regarded as the study of how order emerges from randomness, Ramsey theory has played an important role in mathematics and computer science, giving rise to applications in numerous domains such as logic, parallel processing, and number theory. The core of graph Ramsey theory is arrowing: For fixed graphs $F$ and $H$, the $(F, H)$-Arrowing problem asks whether a given graph, $G$, has a red/blue coloring of the edges of $G$ such that there are no red copies of $F$ and no blue copies of $H$. For some cases, the problem has been shown to be coNP-complete, or solvable in polynomial time. However, a more systematic approach is needed to categorize the complexity of all cases. We focus on $(P_3, H)$-Arrowing as $F = P_3$ is the simplest meaningful case for which the complexity question remains open, and the hardness for this case likely extends to general $(F, H)$-Arrowing for nontrivial $F$. In this pursuit, we also gain insight into the complexity of a class of matching removal problems, since $(P_3, H)$-Arrowing is equivalent to $H$-free Matching Removal. We show that $(P_3, H)$-Arrowing is coNP-complete for all $2$-connected $H$ except when $H = K_3$, in which case the problem is in P. We introduce a new graph invariant to help us carefully combine graphs when constructing the gadgets for our reductions. Moreover, we show how $(P_3,H)$-Arrowing hardness results can be extended to other $(F,H)$-Arrowing problems. This allows for more intuitive and palatable hardness proofs instead of ad-hoc constructions of SAT gadgets, bringing us closer to categorizing the complexity of all $(F, H)$-Arrowing problems.

Authors: Charles Arnal

In this short note, we show that the distance function to any finite set $X\subset \mathbb{R}^n$ is a topological Morse function, regardless of whether $X$ is in general position. We also precisely characterize its topological critical points and their indices, and relate them to the differential critical points of the function.

Authors: Natan Rubin

We use the polynomial method of Guth and Katz to establish stronger and {\it more efficient} regularity and density theorems for such $k$-uniform hypergraphs $H=(P,E)$, where $P$ is a finite point set in ${\mathbb R}^d$, and the edge set $E$ is determined by a semi-algebraic relation of bounded description complexity. In particular, for any $0<\epsilon\leq 1$ we show that one can construct in $O\left(n\log (1/\epsilon)\right)$ time, an equitable partition $P=U_1\uplus \ldots\uplus U_K$ into $K=O(1/\epsilon^{d+1+\delta})$ subsets, for any $0<\delta$, so that all but $\epsilon$-fraction of the $k$-tuples $U_{i_1},\ldots,U_{i_k}$ are {\it homogeneous}: we have that either $U_{i_1}\times\ldots\times U_{i_k}\subseteq E$ or $(U_{i_1}\times\ldots\times U_{i_k})\cap E=\emptyset$. If the points of $P$ can be perturbed in a general position, the bound improves to $O(1/\epsilon^{d+1})$, and the partition is attained via a {\it single partitioning polynomial} (albeit, at expense of a possible increase in worst-case running time). In contrast to the previous such regularity lemmas which were established by Fox, Gromov, Lafforgue, Naor, and Pach and, subsequently, Fox, Pach and Suk, our partition of $P$ does not depend on the edge set $E$ provided its semi-algebraic description complexity does not exceed a certain constant. As a by-product, we show that in any $k$-partite $k$-uniform hypergraph $(P_1\uplus\ldots\uplus P_k,E)$ of bounded semi-algebraic description complexity in ${\mathbb R}^d$ and with $|E|\geq \epsilon \prod_{i=1}^k|P_i|$ edges, one can find, in expected time $O\left(\sum_{i=1}^k|P_i|\log (1/\epsilon)+(1/\epsilon)\log(1/\epsilon)\right)$, subsets $Q_i\subseteq P_i$ of cardinality $|Q_i|\geq |P_i|/\epsilon^{d+1+\delta}$, so that $Q_1\times\ldots\times Q_k\subseteq E$.

Authors: Gary P. T. Choi, Mahmoud Shaqfa

Spectral analysis of open surfaces is gaining momentum for studying surface morphology in engineering, computer graphics, and medical domains. This analysis is enabled using proper parameterization approaches on the target analysis domain. In this paper, we propose the usage of customizable parameterization coordinates that allow mapping open surfaces into oblate or prolate hemispheroidal surfaces. For this, we proposed the usage of Tutte, conformal, area-preserving, and balanced mappings for parameterizing any given simply connected open surface onto an optimal hemispheroid. The hemispheroidal harmonic bases were introduced to spectrally expand these parametric surfaces by generalizing the known hemispherical ones. This approach uses the radius of the hemispheroid as a degree of freedom to control the size of the parameterization domain of the open surfaces while providing numerically stable basis functions. Several open surfaces have been tested using different mapping combinations. We also propose optimization-based mappings to serve various applications on the reconstruction problem. Altogether, our work provides an effective way to represent and analyze simply connected open surfaces.

Authors: Tomer Ezra, Stefano Leonardi, Michał Pawłowski, Matteo Russo, Seeun William Umboh

The online joint replenishment problem (JRP) is a fundamental problem in the area of online problems with delay. Over the last decade, several works have studied generalizations of JRP with different cost functions for servicing requests. Most prior works on JRP and its generalizations have focused on the clairvoyant setting. Recently, Touitou [Tou23a] developed a non-clairvoyant framework that provided an $O(\sqrt{n \log n})$ upper bound for a wide class of generalized JRP, where $n$ is the number of request types. We advance the study of non-clairvoyant algorithms by providing a simpler, modular framework that matches the competitive ratio established by Touitou for the same class of generalized JRP. Our key insight is to leverage universal algorithms for Set Cover to approximate arbitrary monotone subadditive functions using a simple class of functions termed \textit{disjoint}. This allows us to reduce the problem to several independent instances of the TCP Acknowledgement problem, for which a simple 2-competitive non-clairvoyant algorithm is known. The modularity of our framework is a major advantage as it allows us to tailor the reduction to specific problems and obtain better competitive ratios. In particular, we obtain tight $O(\sqrt{n})$-competitive algorithms for two significant problems: Multi-Level Aggregation and Weighted Symmetric Subadditive Joint Replenishment. We also show that, in contrast, Touitou's algorithm is $\Omega(\sqrt{n \log n})$-competitive for both of these problems.

Authors: Daniil Dmitriev, Rares-Darius Buhai, Stefan Tiegel, Alexander Wolters, Gleb Novikov, Amartya Sanyal, David Steurer, Fanny Yang

We study the problem of estimating the means of well-separated mixtures when an adversary may add arbitrary outliers. While strong guarantees are available when the outlier fraction is significantly smaller than the minimum mixing weight, much less is known when outliers may crowd out low-weight clusters - a setting we refer to as list-decodable mixture learning (LD-ML). In this case, adversarial outliers can simulate additional spurious mixture components. Hence, if all means of the mixture must be recovered up to a small error in the output list, the list size needs to be larger than the number of (true) components. We propose an algorithm that obtains order-optimal error guarantees for each mixture mean with a minimal list-size overhead, significantly improving upon list-decodable mean estimation, the only existing method that is applicable for LD-ML. Although improvements are observed even when the mixture is non-separated, our algorithm achieves particularly strong guarantees when the mixture is separated: it can leverage the mixture structure to partially cluster the samples before carefully iterating a base learner for list-decodable mean estimation at different scales.

Authors: Andriy Miranskyy, Mushahid Khan, Udson Mendes

Quantum computers are gaining importance in various applications like quantum machine learning and quantum signal processing. These applications face significant challenges in loading classical datasets into quantum memory. With numerous algorithms available and multiple quality attributes to consider, comparing data loading methods is complex. Our objective is to compare (in a structured manner) various algorithms for loading classical datasets into quantum memory (by converting statevectors to circuits). We evaluate state preparation algorithms based on five key attributes: circuit depth, qubit count, classical runtime, statevector representation (dense or sparse), and circuit alterability. We use the Pareto set as a multi-objective optimization tool to identify algorithms with the best combination of properties. To improve comprehension and speed up comparisons, we also visually compare three metrics (namely, circuit depth, qubit count, and classical runtime). We compare seven algorithms for dense statevector conversion and six for sparse statevector conversion. Our analysis reduces the initial set of algorithms to two dense and two sparse groups, highlighting inherent trade-offs. This comparison methodology offers a structured approach for selecting algorithms based on specific needs. Researchers and practitioners can use it to help select data-loading algorithms for various quantum computing tasks.

Authors: Moritz Buchem, Franziska Eberle, Hugo Kooki Kasuya Rosado, Kevin Schewior, Andreas Wiese

We consider a new scheduling problem on parallel identical machines in which the number of machines is initially not known, but it follows a given probability distribution. Only after all jobs are assigned to a given number of bags, the actual number of machines is revealed. Subsequently, the jobs need to be assigned to the machines without splitting the bags. This is the stochastic version of a related problem introduced by Stein and Zhong [SODA 2018, TALG 2020] and it is, for example, motivated by bundling jobs that need to be scheduled by data centers. We present two PTASs for the stochastic setting, computing job-to-bag assignments that (i) minimize the expected maximum machine load and (ii) maximize the expected minimum machine load (like in the Santa Claus problem), respectively. The former result follows by careful enumeration combined with known PTASs. For the latter result, we introduce an intricate dynamic program that we apply to a suitably rounded instance.

Authors: Philip Whittington

In today's data-centric world, fast and effective compression of data is paramount. To measure success towards the second goal, Kempa and Prezza [STOC2018] introduce the string attractor, a combinatorial object unifying dictionary-based compression. Given a string $T \in \Sigma^n$, a string attractor ($k$-attractor) is a set of positions $\Gamma\subseteq [1,n]$, such that every distinct substring (of length at most $k$) has at least one occurrence that contains one of the selected positions. String attractors are shown to be approximated by and thus measure the quality of many important dictionary compression algorithms such as Lempel-Ziv 77, the Burrows-Wheeler transform, straight line programs, and macro schemes. In order to handle massive amounts of data, compression often has to be achieved in a streaming fashion. Thus, practically applied compression algorithms, such as Lempel-Ziv 77, have been extensively studied in an online setting. To the best of our knowledge, there has been no such work, and therefore are no theoretical underpinnings, for the string attractor problem. We introduce a natural online variant of both the $k$-attractor and the string attractor problem. First, we show that the Lempel-Ziv factorization corresponds to the best online algorithm for this problem, resulting in an upper bound of $\mathcal{O}(\log(n))$ on the competitive ratio. On the other hand, there are families of sparse strings which have constant-size optimal attractors, e.g., prefixes of the infinite Sturmian words and Thue-Morse words, which are created by iterative application of a morphism. We consider the most famous of these Sturmian words, the Fibonacci word, and show that any online algorithm has a cost growing with the length of the word, for a matching lower bound of $\Omega(\log(n))$. For the online $k$-attractor problem, we show tight (strict) $k$-competitiveness.

Authors: Jakub Balabán, Robert Ganian, Mathis Rocton

The approximate computation of twin-width has attracted significant attention already since the moment the parameter was introduced. A recently proposed approach (STACS 2024) towards obtaining a better understanding of this question is to consider the approximability of twin-width via fixed-parameter algorithms whose running time depends not on twin-width itself, but rather on parameters which impose stronger restrictions on the input graph. The first step that article made in this direction is to establish the fixed-parameter approximability of twin-width (with an additive error of 1) when the runtime parameter is the feedback edge number. Here, we make several new steps in this research direction and obtain: - An asymptotically tight bound between twin-width and the feedback edge number; - A significantly improved fixed-parameter approximation algorithm for twin-width under the same runtime parameter (i.e., the feedback edge number) which circumvents many of the technicalities of the original result and simultaneously avoids its formerly non-elementary runtime dependency; - An entirely new fixed-parameter approximation algorithm for twin-width when the runtime parameter is the vertex integrity of the graph.

Authors: Bailu Ding, Jiaqi Zhai

Retrieval plays a fundamental role in recommendation systems, search, and natural language processing by efficiently finding relevant items from a large corpus given a query. Dot products have been widely used as the similarity function in such retrieval tasks, thanks to Maximum Inner Product Search (MIPS) that enabled efficient retrieval based on dot products. However, state-of-the-art retrieval algorithms have migrated to learned similarities. Such algorithms vary in form; the queries can be represented with multiple embeddings, complex neural networks can be deployed, the item ids can be decoded directly from queries using beam search, and multiple approaches can be combined in hybrid solutions. Unfortunately, we lack efficient solutions for retrieval in these state-of-the-art setups. Our work investigates techniques for approximate nearest neighbor search with learned similarity functions. We first prove that Mixture-of-Logits (MoL) is a universal approximator, and can express all learned similarity functions. We next propose techniques to retrieve the approximate top K results using MoL with a tight bound. We finally compare our techniques with existing approaches, showing that MoL sets new state-of-the-art results on recommendation retrieval tasks, and our approximate top-k retrieval with learned similarities outperforms baselines by up to two orders of magnitude in latency, while achieving > .99 recall rate of exact algorithms.

Authors: Mark Braverman, Mahsa Derakhshan, Tristan Pollner, Amin Saberi, David Wajc

We study the polynomial-time approximability of the optimal online stochastic bipartite matching algorithm, initiated by Papadimitriou et al. (EC'21). Here, nodes on one side of the graph are given upfront, while at each time $t$, an online node and its edge weights are drawn from a time-dependent distribution. The optimal algorithm is $\textsf{PSPACE}$-hard to approximate within some universal constant. We refer to this optimal algorithm, which requires time to think (compute), as a philosopher, and refer to polynomial-time online approximations of the above as philosopher inequalities. The best known philosopher inequality for online matching yields a $0.652$-approximation. In contrast, the best possible prophet inequality, or approximation of the optimum offline solution, is $0.5$. Our main results are a $0.678$-approximate algorithm and a $0.685$-approximation for a vertex-weighted special case. Notably, both bounds exceed the $0.666$-approximation of the offline optimum obtained by Tang, Wu, and Wu (STOC'22) for the vertex-weighted problem. Building on our algorithms and the recent black-box reduction of Banihashem et al. (SODA'24), we provide polytime (pricing-based) truthful mechanisms which $0.678$-approximate the social welfare of the optimal online allocation for bipartite matching markets. Our online allocation algorithm relies on the classic pivotal sampling algorithm (Srinivasan FOCS'01, Gandhi et al. J.ACM'06), along with careful discarding to obtain negative correlations between offline nodes. Consequently, the analysis boils down to examining the distribution of a weighted sum $X$ of negatively correlated Bernoulli variables, specifically lower bounding its mass below a threshold, $\mathbb{E}[\min(1,X)]$, of possible independent interest. Interestingly, our bound relies on an imaginary invocation of pivotal sampling.