Theory of Computing Report

The Faculty of Science at the University of Calgary invites applications for a Tenure-Track Assistant Professor (Research and Teaching) in Computer Science position with a focus on Theoretical Foundations of Computer Science. Specific research areas of interest are algorithms, data structures, and complexity theory.

We’ll continue accepting applications until the position is filled.

Website: https://careers.ucalgary.ca/jobs/14820363-tenure-track-assistant-professor-in-theoretical-foundations-of-computer-science-faculty-of-science
Email: cpsc.hiring@ucalgary.ca

By shacharlovett

 I quote Lance's blog post (here) about Computing and the Nobels

a) On Wednesday October 9th half of the Chemistry Nobel was awarded to computer scientists Demis Hassabis and John Jumper for the protein-folding prediction algorithm AlphaFold, which I (Lance) consider the most impressive and game-changing application of machine learning.

b) The day before John Hopfield and Geoffrey Hinton were awarded the Physics Nobel for the development of neural nets that lead to AlphaFold, Large-Language models, and so much more.

Bottom line: The Nobel Prize in CHEM and PHYSICS went to COMPUTER SCIENTISTS. That's probably not quite right since I am sure that the people involved KNEW lots of Chemistry and Physics. 

In Feb 10, 1974 there was an episode of Columbo called Mind Over Mayhem (see here for a summary) where one of the plot threads was the following: 

a) Carl Finch, a great scientist, dies (of natural causes) and in his files is a ground breaking theory of molecular matter.

b) Neil Cahill who was working with Finch as a computer programmer knows about the file and codes up stuff in it and claims the work as his own.   He is initially not caught and he wins the Scientist of the Year Award. 

c) I won't get into who gets murdered or how Columbo catches them.(Has anyone in the real world been murdered because of an academic dispute?)

When I first saw it I had two thoughts:

1) If Neil had claimed co-authorship that would be more honest and hence would not need to be covered up or lead to murder. AND Neil would STILL get credit

2) More important for now: a computer programmer who coded up stuff was considered NOT part of the research in 1974. And now? Well the description of what the Nobel's did seems far more impressive than what Neil Cahill did, though since Neil Cahill is fictional it's hard to say. 

The question of  how much credit should a programmer on a project get? was unintentionally raised way back in 1974. And now? I have not seen ANY objection to computer scientists winning Nobel Prizes in Chem and Physics so the question seems to not be controversial. I agree with this though I am surprised by the lack of controversy. I also note that I used the term Programmer which is not accurate. They were computer scientists. Having said that, programmers also deserve credit. How much is hard to say. The distinction between computer scientists and programmers is also hard to say. But if programmers were considered part of the research in 1974, a fictional murder could have been prevented. 

(ADDED LATER: Lance saw this post after I posted it and emailed me a link to an article that DID hae some objections to giving a Nobel Prize for AI work. I disagree with the objections, but in the interest of being giving intelligent opposing viewpoints,   the link is here.) 

By gasarch

Authors: Louis Golowich, Ting-Chun Lin

For every integer $r\geq 2$ and every $\epsilon>0$, we construct an explicit infinite family of quantum LDPC codes supporting a transversal $C^{r-1}Z$ gate with length $N$, dimension $K\geq N^{1-\epsilon}$, distance $D\geq N^{1/r}/\operatorname{poly}(\log N)$, and stabilizer weight $w\leq\operatorname{poly}(\log N)$. The previous state of the art construction (in most parameter regimes) was the $r$-dimensional color code, which has only constant dimension $K=O(1)$, and otherwise has the same parameters up to polylogarithmic factors. Our construction provides the first known codes with low-weight stabilizers that are capable of magic state distillation with arbitrarily small yield parameter $\gamma=\log(N/K)/\log(D)>0$. A classical analogue of transversal $C^{r-1}Z$ gates is given by the multiplication property, which requires component-wise products of classical codewords to belong to another similar code. As a byproduct of our techniques, we also obtain a new construction of classical locally testable codes with such a multiplication property. We construct our codes as products of chain complexes associated to classical LDPC codes, which in turn we obtain by imposing local Reed-Solomon codes on a specific spectral expander that we construct. We prove that our codes support the desired transversal $C^{r-1}Z$ gates by using the multiplication property to combine local circuits based on the topological structure.

Authors: Ting-Chun Lin

A major goal in quantum computing is to build a fault-tolerant quantum computer. One approach involves quantum low-density parity-check (qLDPC) codes that support transversal non-Clifford gates. In this work, we provide a large family of such codes. The key insight is to interpret the logical operators of qLDPC codes as geometric surfaces and use the intersection number of these surfaces to define the non-Clifford operation. At a more abstract level, this construction is based on defining the cup product on the chain complex induced from a sheaf.

Authors: Jiehua Chena, Christian Hatschka, Sofia Simola

We survey two key problems-Multi-Winner Determination and Hedonic Games in Computational Social Choice, with a special focus on their parameterized complexity, and propose some research challenges in the field.

Authors: Santiago Cifuentes, Samson Wang, Thais L. Silva, Mario Berta, Leandro Aolita

We investigate the dividing line between classical and quantum computational power in estimating properties of matrix functions. More precisely, we study the computational complexity of two primitive problems: given a function $f$ and a Hermitian matrix $A$, compute a matrix element of $f(A)$ or compute a local measurement on $f(A)|0\rangle^{\otimes n}$, with $|0\rangle^{\otimes n}$ an $n$-qubit reference state vector, in both cases up to additive approximation error. We consider four functions -- monomials, Chebyshev polynomials, the time evolution function, and the inverse function -- and probe the complexity across a broad landscape covering different problem input regimes. Namely, we consider two types of matrix inputs (sparse and Pauli access), matrix properties (norm, sparsity), the approximation error, and function-specific parameters. We identify BQP-complete forms of both problems for each function and then toggle the problem parameters to easier regimes to see where hardness remains, or where the problem becomes classically easy. As part of our results we make concrete a hierarchy of hardness across the functions; in parameter regimes where we have classically efficient algorithms for monomials, all three other functions remain robustly BQP-hard, or hard under usual computational complexity assumptions. In identifying classically easy regimes, among others, we show that for any polynomial of degree $\mathrm{poly}(n)$ both problems can be efficiently classically simulated when $A$ has $O(\log n)$ non-zero coefficients in the Pauli basis. This contrasts with the fact that the problems are BQP-complete in the sparse access model even for constant row sparsity, whereas the stated Pauli access efficiently constructs sparse access with row sparsity $O(\log n)$. Our work provides a catalog of efficient quantum and classical algorithms for fundamental linear-algebra tasks.

Authors: Zheng Wei, Xiaodong Wei

In engineering design, one of the most daunting problems in the design-through-analysis workflow is to deal with trimmed NURBS (Non-Uniform Rational B-Splines), which often involve topological/geometric issues and lead to inevitable gaps and overlaps in the model. Given the dominance of the trimming technology in CAD systems, reconstructing such a model as a watertight representation is highly desired. While remarkable progress has been made in recent years, especially with the advancement of isogeometric analysis (IGA), there still lack a fully automatic and scalable tool to achieve this reconstruction goal. To address this issue, we present a semi-automatic and scalable reparameterization pipeline based on a scalable and feature-aligned meshing tool, QuadriFlow [1]. On top of it, we provide support for open surfaces to deal with engineering shell structures, and perform sophisticated patch simplification to remove undesired tiny/slender patches. As a result, we obtain a watertight spline surface (multi-patch NURBS or unstructured splines) with a simple quadrilateral layout. Through several challenging models from industry applications, we demonstrate the efficacy and efficiency of the proposed pipeline as well as its integration with IGA. Our source code is publicly available on GitHub [2].

Authors: Noah Toyonaga, L Mahadevan

We introduce an additive approach for the design of a class of transformable structures based on two-bar linkages ("scissor mechanisms") joined at vertices to form a two dimensional lattice. Our discussion traces an underlying mathematical similarity between linkage mechanisms, origami, and kirigami and inspires our name for these structures: karigami. We show how to design karigami which unfold from a one dimensional collapsed state to two-dimensional surfaces of single and double curvature. Our algorithm for growing karigami structures is provably complete in providing the ability to explore the full space of possible mechanisms, and we use it to computationally design and physically realize a series of examples of varying complexity.

Authors: Nicolas Bousquet, Sébastien Zeitoun

In local certification, vertices of a $n$-vertex graph perform a local verification to check if a given property is satisfied by the graph. This verification is performed thanks to certificates, which are pieces of information that are given to the vertices. In this work, we focus on the local certification of $P_5$-freeness, and we prove a $O(n^{3/2})$ upper bound on the size of the certificates, which is (to our knowledge) the first subquadratic upper bound for this property.

Authors: Shyam Narayanan, Václav Rozhoň, Jakub Tětek, Mikkel Thorup

Suppose we have a memory storing $0$s and $1$s and we want to estimate the frequency of $1$s by sampling. We want to do this I/O-efficiently, exploiting that each read gives a block of $B$ bits at unit cost; not just one bit. If the input consists of uniform blocks: either all 1s or all 0s, then sampling a whole block at a time does not reduce the number of samples needed for estimation. On the other hand, if bits are randomly permuted, then getting a block of $B$ bits is as good as getting $B$ independent bit samples. However, we do not want to make any such assumptions on the input. Instead, our goal is to have an algorithm with instance-dependent performance guarantees which stops sampling blocks as soon as we know that we have a probabilistically reliable estimate. We prove our algorithms to be instance-optimal among algorithms oblivious to the order of the blocks, which we argue is the strongest form of instance optimality we can hope for. We also present similar results for I/O-efficiently estimating mean with both additive and multiplicative error, estimating histograms, quantiles, as well as the empirical cumulative distribution function. We obtain our above results on I/O-efficient sampling by reducing to corresponding problems in the so-called sequential estimation. In this setting, one samples from an unknown distribution until one can provide an estimate with some desired error probability. We then provide non-parametric instance-optimal results for several fundamental problems: mean and quantile estimation, as well as learning mixture distributions with respect to $\ell_\infty$ and the so-called Kolmogorov-Smirnov distance.

Authors: Bernhard Haeupler, Richard Hladík, Vaclav Rozhon, Robert E. Tarjan, Jakub Tětek

While Dijkstra's algorithm has near-optimal time complexity for the problem of finding the shortest $st$-path, in practice, other algorithms are often superior on huge graphs. A prominent such example is the bidirectional search, which executes Dijkstra's algorithm from both endpoints in parallel and stops when these executions meet. In this paper, we give a strong theoretical justification for the use of such bidirectional search algorithms. We prove that for weighted multigraphs, both directed and undirected, a careful implementation of bidirectional search is instance-optimal with respect to the number of edges it explores. That is, we prove that no correct algorithm can outperform our implementation of bidirectional search on any single instance by more than a constant factor. For unweighted graphs, we show that bidirectional search is instace-optimal up to a factor of $O(\Delta)$ where $\Delta$ is the maximum degree of the graph. We also show that this is the best possible.

Authors: Xiaxin Li, Arya Mazumdar

In Group Testing, the objective is to identify K defective items out of N, K<

Authors: Joan Vendrell, Russell Bent, Solmaz Kia

We consider an optimal flow distribution problem in which the goal is to find a radial configuration that minimizes resistance-induced quadratic distribution costs while ensuring delivery of inputs from multiple sources to all sinks to meet their demands. This problem has critical applications in various distribution systems, such as electricity, where efficient energy flow is crucial for both economic and environmental reasons. Due to its complexity, finding an optimal solution is computationally challenging and NP-hard. In this paper, we propose a novel algorithm called FORWARD, which leverages graph theory to efficiently identify feasible configurations in polynomial time. By drawing parallels with random walk processes on electricity networks, our method simplifies the search space, significantly reducing computational effort while maintaining performance. The FORWARD algorithm employs a combination of network preprocessing, intelligent partitioning, and strategic sampling to construct radial configurations that meet flow requirements, finding a feasible solution in polynomial time. Numerical experiments demonstrate the effectiveness of our approach, highlighting its potential for real-world applications in optimizing distribution networks.

The Department of Computer Science at the National University of Singapore (NUS) invites applications for tenure-track and educator-track positions. We seek candidates in theoretical computer science with strong research potential. NUS offers significant research funding, a vibrant PhD program, and excellent collaboration opportunities. Apply by 1 December 2024 at https://faces.comp.nus.edu.sg/

Website: https://careers.comp.nus.edu.sg/
Email: divesh@comp.nus.edu.sg

By shacharlovett

Moshe Vardi wrote a short interesting essay “What is theoretical computer science?” (It followed by interesting posts on Facebook.) Moshe argues that

Thinking of theoretical computer science (TCS) as a branch of mathematics is harmful to the discipline.

I personally do not regard TCS as part of mathematics and I also don’t think that thinking of TCS as part of mathematics is harmful. Certainly there are parts of TCS that are also parts of mathematics as well. (I will try to add a schematic Venn-diagram a bit later.)

Here are some unorganized quotes from the essay, my thoughts and related links.

1. Theory and practice in TCS; my ICM18 paper. Moshe raises interesting issues about the interface between theory and practice in computer science and more broadly in Science and Engineering. This is a topic that greatly interest me and I devoted to three examples:  linear programming, voting and games, and quantum computation, my ICM18 paper Three puzzles on mathematics, computations, and games.
2. Aesthetic values as a primary motivation. Moshe advises to remember the warning of  John von Neuman regarding the danger of mathematics driven solely by internal esthetics: “There is a grave danger that the subject will develop along the line of least resistance.” (See here for the full quote of von Neuman). Personally, I don’t see alternatives to internal aesthetic as a major driving force on all scales for mathematics.
3. Physics inspiration. Moshe writes: “As computer scientists, we should look for inspiration from physics rather than from mathematics. Theoretical physics is highly mathematical, but it aims to explain and predict the real world. Theories that fail at this “explain/predict” task would ultimately be discarded. Analogously, I’d argue that the role of TCS is to explain/predict real-life computing.”
4. Physics heuristic methods. Theoretical physics is characterized by powerful non-rigorous mathematical methods that give amazing predictions. These predictions are quite often confirmed and sometimes refuted. Such methods had some influence for algorithms and theoretical computer science but so far their influence has been limited. One very nice area of applications is to the study of algorithms for random SAT problems. Here is a famous 2002 paper Analytic and algorithmic solution of random satisfiability problems by Mézard, Parisi, and Zecchina.‏
5.  SAT solvers. Moshe writes: “Over the past 30 years, however, we have made tremendous progress in SAT solving, which is today an industrial reality. NP-completeness theory, however, does not explain or predict the unreasonable effectiveness of SAT solvers.”  In my view it is a great problem to understand when and why SAT solvers work. Probably mathematical ideas would be required to study this problem (but everything will go; in my three puzzles paper I suggested the gradual understanding over seven decades of the success of the simplex algorithm as a sort of  role model for understanding the success of SAT solvers). 
6. Theory and practice: what is a proof? We talked about the practice and theory for proving mathematical theorems in this (sort of) debate between me and Avi Wigderson, and in several other posts (I,II,III).
7. The very old debate: Karp’s committee vs. Wigderson & Goldreich. There was a related very interesting debate almost thirty years ago that is discussed in this blog post over the blog Computational Complexity (CC) that present the two positions as follows:

   (Karp’s committee:) In order for TOC to prosper in the coming years, it is essential to strengthen our communication with the rest of computer science and with other disciplines, and to increase our impact on key application areas.

   (Oded and Avi’s view:) In order for TOC to prosper in the coming years, it is essential that Theoretical Computer Scientists concentrate their research efforts in Theory of Computing and that they enjoy the freedom to do so. 

8. Koblitz vs. Goldreich: In the context of Cryptography there was an interesting Koblitz-Goldreich debate, see this post from CC. Cryptography (including cryptoanalysis) is a great subject, and I have a long term plan to write about it over here.
9. The European “Theory A” and “Theory B”. Moshe mentioned that in Europe there are two types of “theoretical computer science” (“Theory A” and “Theory B”). I always found these different possibilities for a scientific theory of computer science quite exciting. Actually, some advances in linear programming (mentioned in my paper quoted above) grew from progress in both “Theory A” and “Theory B”.
10. Computing volume in high dimensions. (This is a problem I heard from Moshe a decade ago.) Two of the greatest achievements in the theory of algorithms are the polynomial time algorithms for computing volume in high dimensions (Dyer, Friese, Kannan) and for approximating permanents of nonnegative matrices (Jerrum, Sinclair, Vigoda).  Let me mention that the current spectacular world record for volume computations is steps by Ben Cousins and Santosh Vempala. The question to be asked is: are there practically good algorithms for these tasks?
11. Randomness, statistics, and derandomization.  A good place to check theory vs. practice is in the context of randomization. What are the TCS notions of “randomness” and how they compare in theory and in practice with notions of randomness from probability theory and from statistics? How practical is the theory of “derandomization?”

Moshe’s article is part of the opinion section of the Communication ACM, where Moshe has a regular column. Let me also mention the European counterpart “The Bulletin of the European association of Theoretical Computer Science”. 

A schematic Venn diagram of TCS, CS, Mathematics and other fields. Of course, every field represented here by a circle is by itself a complex fractal-like object. Avi Wigderson’s lovely book “Mathematics and Computation” gives a great description of some mathematical areas of TCS with a special chapter on connections between TCS and mathematics and another chapter on connections between TCS and other sciences. See also this post.

By Gil Kalai

Multiple postdoc and PhD positions are available in the Theory and Foundations (FoCS) group and in the Centre for Discrete Mathematics and its Applications (DIMAP) at the University of Warwick. Strong candidates interested in Theoretical Computer Science will be considered.

Website: https://www.dcs.warwick.ac.uk/~igorcarb/links-positions.html
Email: igorcarb@gmail.com

By shacharlovett

In this paper we study syntactic branching programs of bounded repetition representing CNFs of bounded treewidth. For this purpose we introduce two new structural graph parameters $d$-pathwidth and clique preserving $d$-pathwidth denoted by $pw_d(G)$ and $cpw_d(G)$ where $G$ is a graph. We show that $cpw_2(G) \leq O(tw(G) \Delta(G))$ where $tw(G)$ and $\Delta(G)$ are, respectively the treewidth and maximal degree of $G$. Using this upper bound, we demonstrate that each CNF $\psi$ can be represented as a conjunction of two OBDDs (quite a restricted class of read-twice branching programs) of size $2^{O(\Delta(\psi) \cdot tw(\psi)^2)}$ where $tw(\psi)$ is the treewidth of the primal graph of $\psi$ and each variable occurs in $\psi$ at most $\Delta(\psi)$ times. Next, we use $d$-pathwidth to obtain lower bounds for monotone branching programs. In particular, we consider the monotone version of syntactic nondeterministic read $d$ times branching programs (just forbidding negative literals as edge labels) and introduce a further restriction that each computational path can be partitioned into at most $d$ read-once subpaths. We call the resulting model separable monotone read $d$ times branching programs and abbreviate them $d$-SMNBPs. For each graph $G$ without isolated vertices, we introduce a CNF $\psi(G)$ whose clauses are $(u \vee e \vee v)$ for each edge $e=\{u,v\}$ of $G$. We prove that a $d$-SMNBP representing $\psi(G)$ is of size at least $\Omega(c^{pw_d(G)})$ where $c=(8/7)^{1/12}$. We use this 'generic' lower bound to obtain an exponential lower bound for a 'concrete' class of CNFs $\psi(K_n)$. In particular, we demonstrate that for each $0<a<1$, the size of $n^{a}$-SMNBP representing $\psi(K_n)$ is at least $c^{n^b}$ where $b$ is an arbitrary constant such that $a+b<1$. This lower bound is tight in the sense $\psi(K_n)$ can be represented by a poly-sized $n$-SMNBP.

We survey recent and classical results and techniques concerning binary codes in the large distance (or, high-noise) regime, and the closely related notion of $\varepsilon$-balanced codes. Our (hopefully small-biased) column will mainly discuss encoding, and decoding from adversarial errors. A previous version of this text originally appeared as an ACM SIGACT News Complexity Theory Column.

We study uniquely decodable codes and list decodable codes in the high-noise regime, specifically codes that are uniquely decodable from $\frac{1-\varepsilon}{2}$ fraction of errors and list decodable from $1-\varepsilon$ fraction of errors. We present several improved explicit constructions that achieve near-optimal rates, as well as efficient or even linear-time decoding algorithms. Our contributions are as follows. 1. Explicit Near-Optimal Linear Time Uniquely Decodable Codes: We construct a family of explicit $\mathbb{F}_2$-linear codes with rate $\Omega(\varepsilon)$ and alphabet size $2^{\mathrm{poly} \log(1/\varepsilon)}$, that are capable of correcting $e$ errors and $s$ erasures whenever $2e + s < (1 - \varepsilon)n$ in linear-time. To the best of our knowledge, this is the first fully explicit linear time decodable code over an alphabet of size $2^{o(1/\varepsilon)}$, that beats the $O(\varepsilon^2)$ rate barrier. 2. Explicit Near-Optimal List Decodable Codes: We construct a family of explicit list decodable codes with rate $\Omega(\varepsilon)$ and alphabet size $2^{\mathrm{poly} \log(1/\varepsilon)}$, that are capable of list decoding from $1-\varepsilon$ fraction of errors with a list size $L = \exp\exp\exp(\log^{\ast}n)$ in polynomial time. To the best of our knowledge, this is the first fully explicit list decodable code with polynomial-time list decoding over an alphabet of size $2^{o(1/\varepsilon)}$, that beats the $O(\varepsilon^2)$ rate barrier. 3. List Decodable Code with Near-Optimal List Size: We construct a family of explicit list decodable codes with an optimal list size of $O(1/\varepsilon)$, albeit with a suboptimal rate of $O(\varepsilon^2)$, capable of list decoding from $1-\varepsilon$ fraction of errors in polynomial time. Furthermore, we introduce a new combinatorial object called multi-set disperser, and use it to give a family of list decodable codes with near-optimal rate $\frac{\varepsilon}{\log^2(1/\varepsilon)}$ and list size $\frac{\log^2(1/\varepsilon)}{\varepsilon}$, that can be constructed in probabilistic polynomial time and decoded in deterministic polynomial time. Our techniques are based on plurality analysis and graph-concatenated codes, which are widely used in the literature. We also introduce new decoding algorithms that may prove valuable for other graph-based codes.

Dear all,

We are pleased to announce a program “Algorithmics of Fair Division and Social Choice”, to be held at the Institute for Mathematical Sciences, National University of Singapore between November 25 – December 13, 2024:

Algorithmics of Fair Division and Social Choice

The program consists of tutorials and two workshops (one on fair division; one on voting, matching, and preference aggregation). We are fortunate to have the following tutorial speakers:

• Felix Brandt (Technical University of Munich, Germany)
• Piotr Faliszewski (AGH University of Science and Technology, Poland)
• Ayumi Igarashi (University of Tokyo, Japan)
• Minming Li (City University of Hong Kong, Hong Kong)

The program is open to all, and registration is free.

Best regards,

Xiaohui Bei

Edith Elkind

Warut Suksompong

By felixbrandt

Yes, he’s the guy from The Elegant Universe book and TV series. Our conversation is 1 hour 40 minutes; as usual I strongly recommend listening at 2x speed. The topics, chosen by Brian, include quantum computing (algorithms, hardware, error-correction … the works), my childhood, the interpretation of quantum mechanics, the current state of AI, the future of sentient life in the cosmos, and mathematical Platonism. I’m happy with how it turned out; in particular, my verbal infelicities seem to have been at a minimum this time. I recommend skipping the YouTube comments if you want to stay sane, but do share your questions and reactions in the comments here. Thanks to Brian and his team for doing this. Enjoy!

By Scott

The next TCS+ talk will take place this coming Wednesday, October 23th at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Thomas Steinke from Google DeepMind will speak about “The Discrete Gaussian for Differential Privacy” (abstract below).

You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: A key tool for building differentially private systems is adding Gaussian noise to the output of a function evaluated on a sensitive dataset. Unfortunately, using a continuous distribution presents several practical challenges. First and foremost, finite computers cannot exactly represent samples from continuous distributions, and previous work has demonstrated that seemingly innocuous numerical errors can entirely destroy privacy. Moreover, when the underlying data is itself discrete (e.g., population counts), adding continuous noise makes the result less interpretable.

With these shortcomings in mind, we introduce and analyze the discrete Gaussian in the context of differential privacy. Specifically, we theoretically and experimentally show that adding discrete Gaussian noise provides essentially the same privacy and accuracy guarantees as the addition of continuous Gaussian noise. We also present an simple and efficient algorithm for exact sampling from this distribution. This demonstrates its applicability for privately answering counting queries, or more generally, low-sensitivity integer-valued queries.

By plustcs

We investigate the computational complexity of estimating the trace of quantum state powers $\text{tr}(\rho^q)$ for an $n$-qubit mixed quantum state $\rho$, given its state-preparation circuit of size $\text{poly}(n)$. This quantity is closely related to and often interchangeable with the Tsallis entropy $\text{S}_q(\rho) = \frac{1-\text{tr}(\rho^q)}{q-1}$, where $q = 1$ corresponds to the von Neumann entropy. For any non-integer $q \geq 1 + \Omega(1)$, we provide a quantum estimator for $\text{S}_q(\rho)$ with time complexity $\text{poly}(n)$, exponentially improving the prior best results of $\exp(n)$ due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), and Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation. Our quantum algorithm reveals a sharp phase transition between the case of $q=1$ and constant $q>1$ in the computational complexity of the Quantum $q$-Tsallis Entropy Difference Problem (TsallisQED$_q$), particularly deciding whether the difference $\text{S}_q(\rho_0) - \text{S}_q(\rho_1)$ is at least $0.001$ or at most $-0.001$: - For any $1+\Omega(1) \leq q \leq 2$, TsallisQED$_q$ is BQP-complete, which implies that Purity Estimation is also BQP-complete. - For any $1 \leq q \leq 1 + \frac{1}{n-1}$, TsallisQED$_q$ is QSZK-hard, leading to hardness of approximating von Neumann entropy because $\text{S}_q(\rho) \leq \text{S}(\rho)$ unless $\text{BQP} = \text{QSZK}$. The hardness results are derived from reductions based on new inequalities for the quantum $q$-Jensen-(Shannon-)Tsallis divergence with $1\leq q \leq 2$, which are of independent interest.

Authors: Yupan Liu, Qisheng Wang

We investigate the computational complexity of estimating the trace of quantum state powers $\text{tr}(\rho^q)$ for an $n$-qubit mixed quantum state $\rho$, given its state-preparation circuit of size $\text{poly}(n)$. This quantity is closely related to and often interchangeable with the Tsallis entropy $\text{S}_q(\rho) = \frac{1-\text{tr}(\rho^q)}{q-1}$, where $q = 1$ corresponds to the von Neumann entropy. For any non-integer $q \geq 1 + \Omega(1)$, we provide a quantum estimator for $\text{S}_q(\rho)$ with time complexity $\text{poly}(n)$, exponentially improving the prior best results of $\exp(n)$ due to Acharya, Issa, Shende, and Wagner (ISIT 2019), Wang, Guan, Liu, Zhang, and Ying (TIT 2024), and Wang, Zhang, and Li (TIT 2024), and Wang and Zhang (ESA 2024). Our speedup is achieved by introducing efficiently computable uniform approximations of positive power functions into quantum singular value transformation. Our quantum algorithm reveals a sharp phase transition between the case of $q=1$ and constant $q>1$ in the computational complexity of the Quantum $q$-Tsallis Entropy Difference Problem (TsallisQED$_q$), particularly deciding whether the difference $\text{S}_q(\rho_0) - \text{S}_q(\rho_1)$ is at least $0.001$ or at most $-0.001$: - For any $1+\Omega(1) \leq q \leq 2$, TsallisQED$_q$ is $\mathsf{BQP}$-complete, which implies that Purity Estimation is also $\mathsf{BQP}$-complete. - For any $1 \leq q \leq 1 + \frac{1}{n-1}$, TsallisQED$_q$ is $\mathsf{QSZK}$-hard, leading to hardness of approximating von Neumann entropy because $\text{S}_q(\rho) \leq \text{S}(\rho)$, as long as $\mathsf{BQP} \subsetneq \mathsf{QSZK}$. The hardness results are derived from reductions based on new inequalities for the quantum $q$-Jensen-(Shannon-)Tsallis divergence with $1\leq q \leq 2$, which are of independent interest.

Authors: Itai Arad, Miklos Santha

We introduce $k$-local quasi-quantum states: a superset of the regular quantum states, defined by relaxing the positivity constraint. We show that a $k$-local quasi-quantum state on $n$ qubits can be 1-1 mapped to a distribution of assignments over $n$ variables with an alphabet of size $4$, which is subject to non-linear constraints over its $k$-local marginals. Therefore, solving the $k$-local Hamiltonian over the quasi-quantum states is equivalent to optimizing a distribution of assignment over a classical $k$-local CSP. We show that this optimization problem is essentially classical by proving it is NP-complete. Crucially, just as ordinary quantum states, these distributions lack a simple tensor-product structure and are therefore not determined straightforwardly by their local marginals. Consequently, our classical optimization problem shares some unique aspects of Hamiltonian complexity: it lacks an easy search-to-decision reduction, and it is not clear that its 1D version can be solved with dynamical programming (i.e., it could remain NP-hard). Our main result is a PCP theorem for the $k$-local Hamiltonian over the quasi-quantum states in the form of a hardness-of-approximation result. The proof suggests the existence of a subtle promise-gap amplification procedure in a model that shares many similarities with the quantum local Hamiltonian problem, thereby providing insights on the quantum PCP conjecture.

Authors: Guy Blanc, Gregory Valiant

We resolve a fundamental question about the ability to perform a statistical task, such as learning, when an adversary corrupts the sample. Such adversaries are specified by the types of corruption they can make and their level of knowledge about the sample. The latter distinguishes between sample-adaptive adversaries which know the contents of the sample when choosing the corruption, and sample-oblivious adversaries, which do not. We prove that for all types of corruptions, sample-adaptive and sample-oblivious adversaries are \emph{equivalent} up to polynomial factors in the sample size. This resolves the main open question introduced by \cite{BLMT22} and further explored in \cite{CHLLN23}. Specifically, consider any algorithm $A$ that solves a statistical task even when a sample-oblivious adversary corrupts its input. We show that there is an algorithm $A'$ that solves the same task when the corresponding sample-adaptive adversary corrupts its input. The construction of $A'$ is simple and maintains the computational efficiency of $A$: It requests a polynomially larger sample than $A$ uses and then runs $A$ on a uniformly random subsample. One of our main technical tools is a new structural result relating two distributions defined on sunflowers which may be of independent interest.

Authors: Swastik Kopparty, Mrinal Kumar, Harry Sha

The classical Reed-Muller codes over a finite field $\mathbb{F}_q$ are based on evaluations of $m$-variate polynomials of degree at most $d$ over a product set $U^m$, for some $d$ less than $|U|$. Because of their good distance properties, as well as the ubiquity and expressive power of polynomials, these codes have played an influential role in coding theory and complexity theory. This is especially so in the setting of $U$ being ${\mathbb{F}}_q$ where they possess deep locality properties. However, these Reed-Muller codes have a significant limitation in terms of the rate achievable -- the rate cannot be more than $\frac{1}{m{!}} = \exp(-m \log m)$. In this work, we give the first constructions of multivariate polynomial evaluation codes which overcome the rate limitation -- concretely, we give explicit evaluation domains $S \subseteq \mathbb{F}_q^m$ on which evaluating $m$-variate polynomials of degree at most $d$ gives a good code. For $m= O(1)$, these new codes have relative distance $\Omega(1)$ and rate $1 - \epsilon$ for any $\epsilon > 0$. In fact, we give two quite different constructions, and for both we develop efficient decoding algorithms for these codes that can decode from half the minimum distance. The first of these codes is based on evaluating multivariate polynomials on simplex-like sets whereas the second construction is more algebraic, and surprisingly (to us), has some strong locality properties, specifically, we show that they are locally testable.

Authors: Matteo Gallet, Georg Grasegger, Jan Legerský, Josef Schicho

Steffen's polyhedron was believed to have the least number of vertices among polyhedra that can flex without self-intersections. Maksimov clarified that the pentagonal bipyramid with one face subdivided into three is the only polyhedron with fewer vertices for which the existence of a self-intersection-free flex was open. Since subdividing a face into three does not change the mobility, we focus on flexible pentagonal bipyramids. When a bipyramid flexes, the distance between the two opposite vertices of the two pyramids changes; associating the position of the bipyramid to this distance yields an algebraic map that determines a nontrivial extension of rational function fields. We classify flexible pentagonal bipyramids with respect to the Galois group of this field extension and provide examples for each class, building on a construction proposed by Nelson. Surprisingly, one of our constructions yields a flexible pentagonal bipyramid that can be extended to an embedded flexible polyhedron with 8 vertices. The latter hence solves the open question.

Authors: Sixtus Dakurah, Jessi Cisewski-Kehe

A time-delay embedding (TDE), grounded in the framework of Takens's Theorem, provides a mechanism to represent and analyze the inherent dynamics of time-series data. Recently, topological data analysis (TDA) methods have been applied to study this time series representation mainly through the lens of persistent homology. Current literature on the fusion of TDE and TDA are adept at analyzing uniformly-spaced time series observations. This work introduces a novel {\em subsequence} embedding method for irregularly-spaced time-series data. We show that this method preserves the original state space topology while reducing spurious homological features. Theoretical stability results and convergence properties of the proposed method in the presence of noise and varying levels of irregularity in the spacing of the time series are established. Numerical studies and an application to real data illustrates the performance of the proposed method.

Authors: Simon D. Fink, Ignaz Rutter, Sandhya T. P

In the Partially Embedded Planarity problem, we are given a graph $G$ together with a topological drawing of a subgraph $H$ of $G$. The task is to decide whether the drawing can be extended to a drawing of the whole graph such that no two edges cross. Angelini et al. gave a linear-time algorithm for solving this problem in 2010 (SODA '10). While their paper constitutes a significant result, the algorithm described therein is highly complex: it uses several layers of decompositions according to connectivity of both $G$ and $H$, its description spans more than 30 pages, and can hardly be considered implementable. We give an independent linear-time algorithm that works along the well-known vertex-addition planarity test by Booth and Lueker. We modify the PC-tree as underlying data structure used for representing all planar drawing possibilities in a natural way to also respect the restrictions given by the prescribed drawing of the subgraph $H$. The testing algorithm and its proof of correctness only require small adaptations from the comparatively much simpler generic planarity test, of which several implementations exist. If the test succeeds, an embedding can be constructed using the same approaches that are used for the generic planarity test.

Authors: Daoyuan Chen, Simon Meierhans, Maximilian Probst Gutenberg, Thatchaphol Saranurak

Expander decompositions have become one of the central frameworks in the design of fast algorithms. For an undirected graph $G=(V,E)$, a near-optimal $\phi$-expander decomposition is a partition $V_1, V_2, \ldots, V_k$ of the vertex set $V$ where each subgraph $G[V_i]$ is a $\phi$-expander, and only an $\widetilde{O}(\phi)$-fraction of the edges cross between partition sets. In this article, we give the first near-optimal \emph{parallel} algorithm to compute $\phi$-expander decompositions in near-linear work $\widetilde{O}(m/\phi^2)$ and near-constant span $\widetilde{O}(1/\phi^4)$. Our algorithm is very simple and likely practical. Our algorithm can also be implemented in the distributed Congest model in $\tilde{O}(1/\phi^4)$ rounds. Our results surpass the theoretical guarantees of the current state-of-the-art parallel algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20], while being the first to ensure that only an $\tilde{O}(\phi)$ fraction of edges cross between partition sets. In contrast, previous algorithms [Chang-Saranurak PODC'19, Chang-Saranurak FOCS'20] admit at least an $O(\phi^{1/3})$ fraction of crossing edges, a polynomial loss in quality inherent to their random-walk-based techniques. Our algorithm, instead, leverages flow-based techniques and extends the popular sequential algorithm presented in [Saranurak-Wang SODA'19].

Authors: Stéphane Devismes, Yoann Dieudonné, Arnaud Labourel

A mobile agent, starting from a node $s$ of a simple undirected connected graph $G=(V,E)$, has to explore all nodes and edges of $G$ using the minimum number of edge traversals. To do so, the agent uses a deterministic algorithm that allows it to gain information on $G$ as it traverses its edges. During its exploration, the agent must always respect the constraint of knowing a path of length at most $D$ to go back to node $s$. The upper bound $D$ is fixed as being equal to $(1+\alpha)r$, where $r$ is the eccentricity of node $s$ (i.e., the maximum distance from $s$ to any other node) and $\alpha$ is any positive real constant. This task has been introduced by Duncan et al. [ACM Trans. Algorithms 2006] and is known as \emph{distance-constrained exploration}. The \emph{penalty} of an exploration algorithm running in $G$ is the number of edge traversals made by the agent in excess of $|E|$. Panaite and Pelc [J. Algorithms 1999] gave an algorithm for solving exploration without any constraint on the moves that is guaranteed to work in every graph $G$ with a (small) penalty in $\mathcal{O}(|V|)$. Hence, a natural question is whether we could obtain a distance-constrained exploration algorithm with the same guarantee as well. In this paper, we provide a negative answer to this question. We also observe that an algorithm working in every graph $G$ with a linear penalty in $|V|$ cannot be obtained for the task of \emph{fuel-constrained exploration}, another variant studied in the literature. This solves an open problem posed by Duncan et al. [ACM Trans. Algorithms 2006] and shows a fundamental separation with the task of exploration without constraint on the moves.

Authors: Atsuki Sato, Yusuke Matsui

Bloom filter is a widely used classic data structure for approximate membership queries. Learned Bloom filters improve memory efficiency by leveraging machine learning, with the partitioned learned Bloom filter (PLBF) being among the most memory-efficient variants. However, PLBF suffers from high computational complexity during construction, specifically $O(N^3k)$, where $N$ and $k$ are hyperparameters. In this paper, we propose three methods: fast PLBF, fast PLBF++, and fast PLBF#, that reduce the construction complexity to $O(N^2k)$, $O(Nk \log N)$, and $O(Nk \log k)$, respectively. Fast PLBF preserves the original PLBF structure and memory efficiency. Although fast PLBF++ and fast PLBF# may have different structures, we theoretically prove they are equivalent to PLBF under ideal data distribution. Furthermore, we theoretically bound the difference in memory efficiency between PLBF and fast PLBF++ for non-ideal scenarios. Experiments on real-world datasets demonstrate that fast PLBF, fast PLBF++, and fast PLBF# are up to 233, 761, and 778 times faster to construct than original PLBF, respectively. Additionally, fast PLBF maintains the same data structure as PLBF, and fast PLBF++ and fast PLBF# achieve nearly identical memory efficiency.

Authors: Manuel Lafond

Given a bipartite graph $G$, the \textsc{Bicluster Editing} problem asks for the minimum number of edges to insert or delete in $G$ so that every connected component is a bicluster, i.e. a complete bipartite graph. This has several applications, including in bioinformatics and social network analysis. In this work, we study the parameterized complexity under the natural parameter $k$, which is the number of allowed modified edges. We first show that one can obtain a kernel with $4.5k$ vertices, an improvement over the previously known quadratic kernel. We then propose an algorithm that runs in time $O^*(2.581^k)$. Our algorithm has the advantage of being conceptually simple and should be easy to implement.

For a long time there has been a tension in graph drawing between theoretical and practical methods. Typical theoretical results show that graphs in certain special classes can be drawn with guaranteed bounds on certain measures of the drawing quality: for instance, the edges may be shaped as polylines with a hard limit on the number of bends per polyline, on the number of crossings per edge, and on the angle of each crossing. In practice we just want to draw arbitrary graphs and produce something legible. Few crossings and avoiding sharp angles are still good, but polylines are not: it can be difficult to distinguish bends from vertices or follow edges that repeatedly bend. For this reason, when straight line segments are inadequate, practical heuristics often use smooth curves rather than polylines, and especially spline curves.

Even when drawing graphs manually rather than in an automated way, splines can be very powerful at making a drawing more legible. Here’s an example I drew manually in 2010 for Wikipedia, a drawing of the Heawood graph demonstrating that it has crossing number \(\le 3\) despite the much higher number of crossings (14) of the more-symmetrical lead image of the linked Wikipedia article. For this example, replacing each spline with a line segment would preserve the low crossing number, but produce an uglier drawing with many sharp angles and nearby crossings. Instead, splines can be guided farther away from the other features of the drawing, producing a drawing with near-symmetry (only the bottom vertex is asymmetrically placed), near-right angle crossings, and all features well separated from each other.

My own research in this area has been very much on the theoretical side of things, but for a long time I’ve been exploring different ways of doing theory on graph drawings with curves instead of bends. This has included both confluent drawing, in which adjacencies follow curved paths through a drawing that resembles railroad tracks, and Lombardi drawing, in which edges are drawn conventionally as curves, but these curves are restricted to be circular arcs meeting at equal angles at each vertex. This works well for certain low-degree or symmetric graphs, knot diagrams, or even symmetric knot diagrams of torus knots. But graph drawing guru Peter Eades has argued (I think correctly) that for general-purpose graph drawing implementations, circular arcs are too rigid: instead, cubic Bezier splines are much more popular, and for good reason. It’s much easier to set up a spline between two vertices than a circular arc, you have greater and easier control of how the spline approaches its endpoints and how it gets between them, and yet spines are not so wiggly as to be difficult to follow by eye.

So what is my response to Eades’ critique? It is to continue doing theory, providing guarantees on measures of quality for drawings of special graphs, but now with splines instead of circular arcs. It’s still a different thing from implementing and testing practical but unguaranteeable heuristics, but with a course correction that I hope keeps the theory more closely in touch with practice.

Specifically, in the recent Symposium on Graph Drawing, I published a paper now also available on the arXiv: “Drawing Planar Graphs and 1-Planar Graphs Using Cubic Bézier Curves with Bounded Curvature” (arXiv:2410.12083), with Michael Goodrich and Abraham Illickan, a new student of Mike. Here, a 1-planar graph is a graph that can be drawn in the plane with at most one crossing per edge; these graphs have been heavily studied since Ringel first defined them in 1965. Planar graphs can always be drawn with straight edges (Fáry’s theorem), but some 1-planar graphs such as the one below require curves or bends.

However, these curves do not need to be complicated: as our paper shows, cubic splines are enough. More, the splines can be chosen to ensure that all crossings are at right angles. An additional result of the paper is a drawing method for planar graphs with splines that meet at not-too-sharp angles, in a grid of polynomial area. However you draw a planar graph, the angles at its vertices are at least going to be inversely proportional to the degree, and our method achieves that. In contrast, for straight-line planar drawings, the angles may be much sharper: known methods produce angles that are exponentially sharp as a function of the degree, and inverse-cubic in the degree is necessary. Achieving angles that are bounded by any function of the degree, with straight edges, may require some edges to be exponentially longer than others. So, at least for these problems, splines are much more powerful than straight edges.

(Discuss on Mastodon)

By David Eppstein

One PhD position for UK Home students is available at the School for Electronic Engineering and Computer Science, Queen Mary University of London, supervised by Marc Roth. The project associated with the position will be on the parameterised and fine-grained complexity of computational counting problems arising in the analysis of large networks.

Website: https://www.roth-marc.com/phd-studentship-vacancy
Email: m.roth@qmul.ac.uk

By shacharlovett

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

We’ve hit the middle of the semester, and so I need to find my bearings. The class has a midterm on Monday, and today’s lecture is a midterm review. Next Thursday, we’ll have a “Fall Break.” I’ll probably still blog a bit next week as I have an inflammatory draft on science and statistics that I need to get out of my inbox. Class reconvenes on the following Tuesday, moving into the third part of the semester: a survey of algorithms.

Since today’s class is a midterm review, let me use this blog to jot down my reflections on the class content so far.

Declarative Programming

Boyd and Vandenberghe’s declarative programming introduction to convex optimization solidly holds up 20 years later. This focus yields a streamlined introduction to convex analysis, which is a great way to introduce this subject. And I’ve seen few better ways to make modeling a first class citizen in an optimization class. Modeling should be a first class citizen! As much as optimizers like to write papers where we’re just handed abstract minimization problems out of the ether, modeling is the most important part of this class for most people.

I’m still not sure what the right balance of theory and application is for this class. An alternative approach, and one which I might do at the undergraduate level, would be to first teach linear programming, then cover unconstrained convex programming, and finish with convex programming with nonlinear convex objective functions and linear constraints. If I had done it this way, I’d have skipped a lot of the convex analysis and separating hyperplane theory, but I'd still have been able to introduce the KKT conditions and basic duality. At the midsemester break, I’m wondering if this would be a better way to teach the material at the graduate level too. 

Solve stuff early

In retrospect, my biggest pedagogical oversight so far has been avoiding programming assignments. I should have introduced solving optimization problems in the homework once we hit Chapter 4. I think I had a blindspot because I’m used to teaching algorithmic-centric optimization classes, where the students have to program solvers by hand. However, the whole point of the declarative approach to convex optimization is that you don’t have to care about the algorithm (until you run into scaling issues). For small, simple problems, everyone can just run cvxpy in a Jupyter Notebook. Cvxpy doesn’t require you to understand what the solver is doing. I think this is obvious, but I’m making a note to my future self to introduce cvxpy earlier next time I do this class.

A farewell to Semidefinite Programming

I had forgotten how much of the book leans on semidefinite programming for examples. Given all of the other material to cover, teaching people about Schur complement tricks and nonlinear matrix manipulation felt like too much. The extra emphasis on semidefinite programming in the text is a reflection of its times, as everyone loved SDPs in the early 2000s. I mostly skipped these problems because it's simply too much to cover in a semester, and sadly, SDPs are no longer trendy. Ensuing technology trends pulled us away from interior point methods and SDPs and towards streaming algorithms we could run to place ads.

Is everything quadratic cost and linear constraints?

When you skip semidefinite programming, most of the remaining examples are linear and quadratic optimization. At the beginning of the semester, Jeremy Kun commented that he thought all you’d need to learn is linear programming and unconstrained nonlinear programming. Midway through the class, I think he’s about half right: you could probably get away with mostly linear programming with quadratic objective functions. If you wanted to get extra fancy, we saw a few examples with second-order-cone constraints. That sums up the majority of the application examples.

So much statistics

The book’s notable nonlinear, nonquadratic examples revolve around entropy and its Fenchel conjugate. This highlights how statistics has been one of the major consumers of convex optimization. As I’ve said, this makes sense because if you’re already working with probability distributions, then convex combinations have to play a central role.

The applications covered in the book are also heavily focused on statistics. Two of the three application chapters “could” be called statistics, depending on how much of a statistical imperialist you are. Even in Chapter 8, there’s a long section on pattern classification pitched as a “geometric problem. 

So little control

By contrast, a notably downplayed application in Boyd and Vandenberghe is control systems. They talk a little bit about control in the introduction and have a short section on linear control in Chapter 10 (we’ll get there). This is particularly odd given that Boyd and Vandenberghe were both trained as control theorists. I’ll have to ask them why they left this out. 

A chapter on simple applications in control, for instance, based on Boyd’s optimal control class, would have been relevant given the current academic interest in using machine learning in control systems. Simple examples from optimal control, such as the linear quadratic regulator or simple Markov decision processes, would be very relevant. I think I’m going to do a week on this topic at the end of the semester.

Subscribe now

By Ben Recht

Authors: Srinivasan Arunachalam, Louis Schatzki

We consider the task of distributed inner product estimation when allowed limited quantum communication. Here, Alice and Bob are given $k$ copies of an unknown $n$-qubit quantum states $\vert \psi \rangle,\vert \phi \rangle$ respectively. They are allowed to communicate $q$ qubits and unlimited classical communication, and their goal is to estimate $|\langle \psi|\phi\rangle|^2$ up to constant accuracy. We show that $k=\Theta(\sqrt{2^{n-q}})$ copies are essentially necessary and sufficient for this task (extending the work of Anshu, Landau and Liu (STOC'22) who considered the case when $q=0$). Additionally, we consider estimating $|\langle \psi|M|\phi\rangle|^2$, for arbitrary Hermitian $M$. For this task we show that certain norms on $M$ characterize the sample complexity of estimating $|\langle \psi|M|\phi\rangle|^2$ when using only classical~communication.

Authors: Omkar Baraskar, Agrim Dewan, Chandan Saha, Pulkit Sinha

An $s$-sparse polynomial has at most $s$ monomials with nonzero coefficients. The Equivalence Testing problem for sparse polynomials (ETsparse) asks to decide if a given polynomial $f$ is equivalent to (i.e., in the orbit of) some $s$-sparse polynomial. In other words, given $f \in \mathbb{F}[\mathbf{x}]$ and $s \in \mathbb{N}$, ETsparse asks to check if there exist $A \in \mathrm{GL}(|\mathbf{x}|, \mathbb{F})$ and $\mathbf{b} \in \mathbb{F}^{|\mathbf{x}|}$ such that $f(A\mathbf{x} + \mathbf{b})$ is $s$-sparse. We show that ETsparse is NP-hard over any field $\mathbb{F}$, if $f$ is given in the sparse representation, i.e., as a list of nonzero coefficients and exponent vectors. This answers a question posed in [Gupta-Saha-Thankey, SODA'23] and [Baraskar-Dewan-Saha, STACS'24]. The result implies that the Minimum Circuit Size Problem (MCSP) is NP-hard for a dense subclass of depth-$3$ arithmetic circuits if the input is given in sparse representation. We also show that approximating the smallest $s_0$ such that a given $s$-sparse polynomial $f$ is in the orbit of some $s_0$-sparse polynomial to within a factor of $s^{\frac{1}{3} - \epsilon}$ is NP-hard for any $\epsilon > 0$; observe that $s$-factor approximation is trivial as the input is $s$-sparse. Finally, we show that for any constant $\sigma \geq 5$, checking if a polynomial (given in sparse representation) is in the orbit of some support-$\sigma$ polynomial is NP-hard. Support of a polynomial $f$ is the maximum number of variables present in any monomial of $f$. These results are obtained via direct reductions from the $3$-SAT problem.

Authors: Itay Shalit

The Gottesman-Knill theorem shows that Clifford circuits operating on stabilizer states can be efficiently simulated classically. However, in the setting of interactive protocols, it has remained unclear whether Clifford strategies with shared entanglement between provers offer any advantage over classical ones. We provide a negative answer to this question, demonstrating that even when Clifford provers are additionally allowed to perform general classical operations on measured qubits $-$ a computational model for which we introduce the complexity class $\text{Clifford-MIP}^\ast$ $-$ there is no advantage over classical strategies. Our results imply that $\text{Clifford-MIP}^\ast = \text{MIP}$. Furthermore, we utilize our findings to resolve an open question posed by Kalai et al. (STOC 2023). We show that quantum advantage in any non-local game requires at least two quantum provers operating outside the $\text{Clifford-MIP}^\ast$ computational model. This rules out a suggested approach for significantly improving the efficiency of tests for quantum advantage that are based on compiling non-local games.

Authors: Peter Werner, Thomas Cohn, Rebecca H. Jiang, Tim Seyde, Max Simchowitz, Russ Tedrake, Daniela Rus

We propose two novel algorithms for constructing convex collision-free polytopes in robot configuration space. Finding these polytopes enables the application of stronger motion-planning frameworks such as trajectory optimization with Graphs of Convex Sets [1] and is currently a major roadblock in the adoption of these approaches. In this paper, we build upon IRIS-NP (Iterative Regional Inflation by Semidefinite & Nonlinear Programming) [2] to significantly improve tunability, runtimes, and scaling to complex environments. IRIS-NP uses nonlinear programming paired with uniform random initialization to find configurations on the boundary of the free configuration space. Our key insight is that finding near-by configuration-space obstacles using sampling is inexpensive and greatly accelerates region generation. We propose two algorithms using such samples to either employ nonlinear programming more efficiently (IRIS-NP2 ) or circumvent it altogether using a massively-parallel zero-order optimization strategy (IRIS-ZO). We also propose a termination condition that controls the probability of exceeding a user-specified permissible fraction-in-collision, eliminating a significant source of tuning difficulty in IRIS-NP. We compare performance across eight robot environments, showing that IRIS-ZO achieves an order-of-magnitude speed advantage over IRIS-NP. IRISNP2, also significantly faster than IRIS-NP, builds larger polytopes using fewer hyperplanes, enabling faster downstream computation. Website: https://sites.google.com/view/fastiris

Authors: Zhiyuan Lyu, Lok Ming Lui, Gary P. T. Choi

Surface parameterization is a fundamental task in geometry processing and plays an important role in many science and engineering applications. In recent years, the density-equalizing map, a shape deformation technique based on the physical principle of density diffusion, has been utilized for the parameterization of simply connected and multiply connected open surfaces. More recently, a spherical density-equalizing mapping method has been developed for the parameterization of genus-0 closed surfaces. However, for genus-0 closed surfaces with extreme geometry, using a spherical domain for the parameterization may induce large geometric distortion. In this work, we develop a novel method for computing density-equalizing maps of genus-0 closed surfaces onto an ellipsoidal domain. This allows us to achieve ellipsoidal area-preserving parameterizations and ellipsoidal parameterizations with controlled area change. We further propose an energy minimization approach that combines density-equalizing maps and quasi-conformal maps, which allows us to produce ellipsoidal density-equalizing quasi-conformal maps for achieving a balance between density-equalization and quasi-conformality. Using our proposed methods, we can significantly improve the performance of surface remeshing for genus-0 closed surfaces. Experimental results on a large variety of genus-0 closed surfaces are presented to demonstrate the effectiveness of our proposed methods.

Authors: David Eppstein, Michael T. Goodrich, Abraham M. Illickan

We study algorithms for drawing planar graphs and 1-planar graphs using cubic B\'ezier curves with bounded curvature. We show that any n-vertex 1-planar graph has a 1-planar RAC drawing using a single cubic B\'ezier curve per edge, and this drawing can be computed in $O(n)$ time given a combinatorial 1-planar drawing. We also show that any n-vertex planar graph G can be drawn in $O(n)$ time with a single cubic B\'ezier curve per edge, in an $O(n)\times O(n)$ bounding box, such that the edges have ${\Theta}(1/degree(v))$ angular resolution, for each $v \in G$, and $O(\sqrt{n})$ curvature.

Authors: José Soto, Victor Verdugo

In the online 2-bounded auction problem, we have a collection of items represented as nodes in a graph and bundles of size two represented by edges. Agents are presented sequentially, each with a random weight function over the bundles. The goal of the decision-maker is to find an allocation of bundles to agents of maximum weight so that every item is assigned at most once, i.e., the solution is a matching in the graph. When the agents are single-minded (i.e., put all the weight in a single bundle), we recover the maximum weight prophet matching problem under edge arrivals (a.k.a. prophet matching). In this work, we provide new and improved upper bounds on the competitiveness achievable by an algorithm for the general online 2-bounded auction and the (single-minded) prophet matching problems. For adversarial arrival order of the agents, we show that no algorithm for the online 2-bounded auction problem achieves a competitiveness larger than $4/11$, while no algorithm for prophet matching achieves a competitiveness larger than $\approx 0.4189$. Using a continuous-time analysis, we also improve the known bounds for online 2-bounded auctions for random order arrivals to $\approx 0.5968$ in the general case, a bound of $\approx 0.6867$ in the IID model, and $\approx 0.6714$ in prophet-secretary model.

Authors: Weiyuan Gong, Jonas Haferkamp, Qi Ye, Zhihan Zhang

We study the sample complexity of the prototypical tasks quantum purity estimation and quantum inner product estimation. In purity estimation, we are to estimate $tr(\rho^2)$ of an unknown quantum state $\rho$ to additive error $\epsilon$. Meanwhile, for quantum inner product estimation, Alice and Bob are to estimate $tr(\rho\sigma)$ to additive error $\epsilon$ given copies of unknown quantum state $\rho$ and $\sigma$ using classical communication and restricted quantum communication. In this paper, we show a strong connection between the sample complexity of purity estimation with bounded quantum memory and inner product estimation with bounded quantum communication and unentangled measurements. We propose a protocol that solves quantum inner product estimation with $k$-qubit one-way quantum communication and unentangled local measurements using $O(median\{1/\epsilon^2,2^{n/2}/\epsilon,2^{n-k}/\epsilon^2\})$ copies of $\rho$ and $\sigma$. Our protocol can be modified to estimate the purity of an unknown quantum state $\rho$ using $k$-qubit quantum memory with the same complexity. We prove that arbitrary protocols with $k$-qubit quantum memory that estimate purity to error $\epsilon$ require $\Omega(median\{1/\epsilon^2,2^{n/2}/\sqrt{\epsilon},2^{n-k}/\epsilon^2\})$ copies of $\rho$. This indicates the same lower bound for quantum inner product estimation with one-way $k$-qubit quantum communication and classical communication, and unentangled local measurements. For purity estimation, we further improve the lower bound to $\Omega(\max\{1/\epsilon^2,2^{n/2}/\epsilon\})$ for any protocols using an identical single-copy projection-valued measurement. Additionally, we investigate a decisional variant of quantum distributed inner product estimation without quantum communication for mixed state and provide a lower bound on the sample complexity.

Authors: Adam Bouland, Tudor Giurgica-Tiron, John Wright

We study a generalization of entanglement testing which we call the "hidden cut problem." Taking as input copies of an $n$-qubit pure state which is product across an unknown bipartition, the goal is to learn precisely where the state is unentangled, i.e. to determine which of the exponentially many possible cuts separates the state. We give a polynomial-time quantum algorithm which can find the cut using $O(n/\epsilon^2)$ many copies of the state, which is optimal up to logarithmic factors. Our algorithm also generalizes to learn the entanglement structure of arbitrary product states. In the special case of Haar-random states, we further show that our algorithm requires circuits of only constant depth. To develop our algorithm, we introduce a state generalization of the hidden subgroup problem (StateHSP) which might be of independent interest, in which one is given a quantum state invariant under an unknown subgroup action, with the goal of learning the hidden symmetry subgroup. We show how the hidden cut problem can be formulated as a StateHSP with a carefully chosen Abelian group action. We then prove that Fourier sampling on the hidden cut state produces similar outcomes as a variant of the well-known Simon's problem, allowing us to find the hidden cut efficiently. Therefore, our algorithm can be interpreted as an extension of Simon's algorithm to entanglement testing. We discuss possible applications of StateHSP and hidden cut problems to cryptography and pseudorandomness.

Authors: Moritz Mühlenthaler, Mark H. Siggers, Thomas Suzan

Given a graph $G$ and two graph homomorphisms $\alpha$ and $\beta$ from $G$ to a fixed graph $H$, the problem $H$-Recoloring asks whether there is a transformation from $\alpha$ to $\beta$ that changes the image of a single vertex at each step and keeps a graph homomorphism throughout. The complexity of the problem depends among other things on the presence of loops on the vertices. We provide a simple reduction that, using a known algorithmic result for $H$-Recoloring for square-free irreflexive graphs $H$, yields a polynomial-time algorithm for $H$-Recoloring for square-free reflexive graphs $H$. This generalizes all known algorithmic results for $H$-Recoloring for reflexive graphs $H$. Furthermore, the construction allows us to recover some of the known hardness results. Finally, we provide a partial inverse of the construction for bipartite instances.

Authors: Paul Bastide, Carla Groenland

In distance query reconstruction, we wish to reconstruct the edge set of a hidden graph by asking as few distance queries as possible to an oracle. Given two vertices $u$ and $v$, the oracle returns the shortest path distance between $u$ and $v$ in the graph. The length of a tree decomposition is the maximum distance between two vertices contained in the same bag. The treelength of a graph is defined as the minimum length of a tree decomposition of this graph. We present an algorithm to reconstruct an $n$-vertex connected graph $G$ parameterized by maximum degree $\Delta$ and treelength $k$ in $O_{k,\Delta}(n \log^2 n)$ queries (in expectation). This is the first algorithm to achieve quasi-linear complexity for this class of graphs. The proof goes through a new lemma that could give independent insight on graphs of bounded treelength.

Authors: Sayan Bhattacharya, Martín Costa, Shay Solomon, Tianyi Zhang

Vizing's Theorem from 1964 states that any $n$-vertex $m$-edge graph with maximum degree $\Delta$ can be {\em edge colored} using at most $\Delta + 1$ colors. For over 40 years, the state-of-the-art running time for computing such a coloring, obtained independently by Arjomandi [1982] and by Gabow, Nishizeki, Kariv, Leven and Terada~[1985], was $\tilde O(m\sqrt{n})$. Very recently, this time bound was improved in two independent works, by Bhattacharya, Carmon, Costa, Solomon and Zhang to $\tilde O(mn^{1/3})$, and by Assadi to $\tilde O(n^2)$. In this paper we present an algorithm that computes such a coloring in $\tilde O(mn^{1/4})$ time. Our key technical contribution is a subroutine for extending the coloring to one more edge within time $\tilde O(\Delta^2 + \sqrt{\Delta n})$. The best previous time bound of any color extension subroutine is either the trivial $O(n)$, dominated by the length of a Vizing chain, or the bound $\tilde{O}(\Delta^6)$ by Bernshteyn [2022], dominated by the length of {\em multi-step Vizing chains}, which is basically a concatenation of multiple (carefully chosen) Vizing chains. Our color extension subroutine produces significantly shorter multi-step Vizing chains than in previous works, for sufficiently large $\Delta$.

Authors: Kevin Buchin, Mart Hagedoorn, Guangping Li, Carolin Rehs

Given a graph with edge costs and vertex profits and given a budget B, the Orienteering Problem asks for a walk of cost at most B of maximum profit. Additionally, each profit may be given with a time window within it can be collected by the walk. While the Orienteering Problem and thus the version with time windows are NP-hard in general, it remains open on numerous special graph classes. Since in several applications, especially for planning a route from A to B with waypoints, the input graph can be restricted to tree-like or path-like structures, in this paper we consider orienteering on these graph classes. While the Orienteering Problem with time windows is NP-hard even on undirected paths and cycles, and remains so even if all profits must be collected, we show that for directed paths it can be solved efficiently, even if each profit can be collected in one of several time windows. The same case is shown to be NP-hard for directed cycles. Particularly interesting is the Orienteering Problem on a directed cycle with one time window per profit. We give an efficient algorithm for the case where all time windows are shorter than the length of the cycle, resulting in a 2-approximation for the general setting. We further develop a polynomial-time approximation scheme for this problem and give a polynomial algorithm for the case where all profits must be collected. For the Orienteering Problem with time windows for the edges, we give a quadratic time algorithm for undirected paths and observe that the problem is NP-hard for trees. In the variant without time windows, we show that on trees and thus on graphs with bounded tree-width the Orienteering Problem remains NP-hard. We present, however, an FPT algorithm to solve orienteering with unit profits that we then use to obtain a ($1+\varepsilon$)-approximation algorithm on graphs with arbitrary profits and bounded tree-width.