Last Update

OPML feed of all feeds.

Subscribe to the Atom feed, RSS feed to stay up to date.

Thank you to arXiv for use of its open access interoperability.

Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.

Powered by Pluto.

Source on GitHub.

Maintained by Nima Anari, Arnab Bhattacharyya, Gautam Kamath.

Theory of Computing Report

Monday, November 11

Guest Post: ISAAC’24 in Sydney: Registration deadline soon!

from Kamathematics

Clément Canonne asked to pass along the following registration info for ISAAC 2024, which will be in Sydney in early December. I was lucky to visit Sydney in July 2017 for ICML, and it was one of the most fun conference trips I’ve had! (Painfully long flight from Boston aside…) Definitely attend if you can! … Continue reading "Guest Post: ISAAC’24 in Sydney: Registration deadline soon!"

Clément Canonne asked to pass along the following registration info for ISAAC 2024, which will be in Sydney in early December. I was lucky to visit Sydney in July 2017 for ICML, and it was one of the most fun conference trips I’ve had! (Painfully long flight from Boston aside…) Definitely attend if you can!



The registration for the 35th International Symposium on Algorithms and Computation (ISAAC 2024), to be held in Sydney (Australia) on December 8-11, is open for only a few more weeks!
Besides the conference itself, the registration includes lunches as well as a ticket to the conference banquet: https://www.trybooking.com/events/landing/1249687
Registrations are open until November 29, AoE:
Student: AUD 480 (~USD 325)
Regular: AUD 960 (~USD 650)
(Note: There will be no on-site registration.)
For more details, see https://sites.google.com/view/isaac2024/registration?authuser=0
Looking forward to seeing you at ISAAC in Sydney!

By Gautam

Symmetrization maps and minimal border rank Comon's conjecture

from arXiv: Computational Complexity

Authors: Tomasz Mańdziuk, Emanuele Ventura

One of the fundamental open problems in the field of tensors is the border Comon's conjecture: given a symmetric tensor $F\in(\mathbb{C}^n)^{\otimes d}$ for $d\geq 3$, its border and symmetric border ranks are equal. In this paper, we prove the conjecture for large classes of concise tensors in $(\mathbb{C}^n)^{\otimes d}$ of border rank $n$, i.e., tensors of minimal border rank. These families include all tame tensors and all tensors whenever $n\leq d+1$. Our technical tools are border apolarity and border varieties of sums of powers.

Authors: Tomasz Mańdziuk, Emanuele Ventura

One of the fundamental open problems in the field of tensors is the border Comon's conjecture: given a symmetric tensor $F\in(\mathbb{C}^n)^{\otimes d}$ for $d\geq 3$, its border and symmetric border ranks are equal. In this paper, we prove the conjecture for large classes of concise tensors in $(\mathbb{C}^n)^{\otimes d}$ of border rank $n$, i.e., tensors of minimal border rank. These families include all tame tensors and all tensors whenever $n\leq d+1$. Our technical tools are border apolarity and border varieties of sums of powers.

Super Unique Tarski is in UEOPL

from arXiv: Computational Complexity

Authors: John Fearnley, Rahul Savani

We define the Super-Unique-Tarski problem, which is a Tarski instance in which all slices are required to have a unique fixed point. We show that Super-Unique-Tarski lies in UEOPL under promise-preserving reductions.

Authors: John Fearnley, Rahul Savani

We define the Super-Unique-Tarski problem, which is a Tarski instance in which all slices are required to have a unique fixed point. We show that Super-Unique-Tarski lies in UEOPL under promise-preserving reductions.

DQC1-hardness of estimating correlation functions

from arXiv: Computational Complexity

Authors: Subhayan Roy Moulik, Sergii Strelchuk

Out-of-Time-Order Correlation function measures transport properties of dynamical systems. They are ubiquitously used to measure quantum mechanical quantities, such as scrambling times, criticality in phase transitions, and detect onset of thermalisation. We characterise the computational complexity of estimating OTOCs over all eigenstates and show it is Complete for the One Clean Qubit model (DQC1). We then generalise our setup to establish DQC1-Completeness of N-time Correlation functions over all eigenstates. Building on previous results, the DQC1-Completeness of OTOCs and N-time Correlation functions then allows us to highlight a dichotomy between query complexity and circuit complexity of estimating correlation functions.

Authors: Subhayan Roy Moulik, Sergii Strelchuk

Out-of-Time-Order Correlation function measures transport properties of dynamical systems. They are ubiquitously used to measure quantum mechanical quantities, such as scrambling times, criticality in phase transitions, and detect onset of thermalisation. We characterise the computational complexity of estimating OTOCs over all eigenstates and show it is Complete for the One Clean Qubit model (DQC1). We then generalise our setup to establish DQC1-Completeness of N-time Correlation functions over all eigenstates. Building on previous results, the DQC1-Completeness of OTOCs and N-time Correlation functions then allows us to highlight a dichotomy between query complexity and circuit complexity of estimating correlation functions.

On the Computational Complexity of Schrödinger Operators

from arXiv: Computational Complexity

Authors: Yufan Zheng, Jiaqi Leng, Yizhou Liu, Xiaodi Wu

We study computational problems related to the Schr\"odinger operator $H = -\Delta + V$ in the real space under the condition that (i) the potential function $V$ is smooth and has its value and derivative bounded within some polynomial of $n$ and (ii) $V$ only consists of $O(1)$-body interactions. We prove that (i) simulating the dynamics generated by the Schr\"odinger operator implements universal quantum computation, i.e., it is BQP-hard, and (ii) estimating the ground energy of the Schr\"odinger operator is as hard as estimating that of local Hamiltonians with no sign problem (a.k.a. stoquastic Hamiltonians), i.e., it is StoqMA-complete. This result is particularly intriguing because the ground energy problem for general bosonic Hamiltonians is known to be QMA-hard and it is widely believed that $\texttt{StoqMA}\varsubsetneq \texttt{QMA}$.

Authors: Yufan Zheng, Jiaqi Leng, Yizhou Liu, Xiaodi Wu

We study computational problems related to the Schr\"odinger operator $H = -\Delta + V$ in the real space under the condition that (i) the potential function $V$ is smooth and has its value and derivative bounded within some polynomial of $n$ and (ii) $V$ only consists of $O(1)$-body interactions. We prove that (i) simulating the dynamics generated by the Schr\"odinger operator implements universal quantum computation, i.e., it is BQP-hard, and (ii) estimating the ground energy of the Schr\"odinger operator is as hard as estimating that of local Hamiltonians with no sign problem (a.k.a. stoquastic Hamiltonians), i.e., it is StoqMA-complete. This result is particularly intriguing because the ground energy problem for general bosonic Hamiltonians is known to be QMA-hard and it is widely believed that $\texttt{StoqMA}\varsubsetneq \texttt{QMA}$.

Filtration Order Coface Generation Algorithm

from arXiv: Computational Geometry

Authors: Jordan Matuszewski, Mikael Vejdemo-Johansson

We propose novel algorithms for generating cofaces in the Vietoris-Rips complex. Cofaces -- simplices that contain a given simplex -- have multiple important uses in generating and using a Vietoris-Rips filtered complex: both in creating the coboundary matrix for computing cohomology, and as a more recent approach for generating the simplex stream in the first place. Traditionally, most methods have generated simplices first, and then sorted them in filtration order after the generation step. In this paper, we propose generating simplex streams by generating non-expanding cofaces, which by construction produces simplices in filtration order, and we propose generating additional cofaces in filtration order using sorted neighborhood lists to produce coboundaries directly in filtration order.

Authors: Jordan Matuszewski, Mikael Vejdemo-Johansson

We propose novel algorithms for generating cofaces in the Vietoris-Rips complex. Cofaces -- simplices that contain a given simplex -- have multiple important uses in generating and using a Vietoris-Rips filtered complex: both in creating the coboundary matrix for computing cohomology, and as a more recent approach for generating the simplex stream in the first place. Traditionally, most methods have generated simplices first, and then sorted them in filtration order after the generation step. In this paper, we propose generating simplex streams by generating non-expanding cofaces, which by construction produces simplices in filtration order, and we propose generating additional cofaces in filtration order using sorted neighborhood lists to produce coboundaries directly in filtration order.

ClusterGraph: a new tool for visualization and compression of multidimensional data

from arXiv: Computational Geometry

Authors: Paweł Dłotko, Davide Gurnari, Mathis Hallier, Anna Jurek-Loughrey

Understanding the global organization of complicated and high dimensional data is of primary interest for many branches of applied sciences. It is typically achieved by applying dimensionality reduction techniques mapping the considered data into lower dimensional space. This family of methods, while preserving local structures and features, often misses the global structure of the dataset. Clustering techniques are another class of methods operating on the data in the ambient space. They group together points that are similar according to a fixed similarity criteria, however unlike dimensionality reduction techniques, they do not provide information about the global organization of the data. Leveraging ideas from Topological Data Analysis, in this paper we provide an additional layer on the output of any clustering algorithm. Such data structure, ClusterGraph, provides information about the global layout of clusters, obtained from the considered clustering algorithm. Appropriate measures are provided to assess the quality and usefulness of the obtained representation. Subsequently the ClusterGraph, possibly with an appropriate structure--preserving simplification, can be visualized and used in synergy with state of the art exploratory data analysis techniques.

Authors: Paweł Dłotko, Davide Gurnari, Mathis Hallier, Anna Jurek-Loughrey

Understanding the global organization of complicated and high dimensional data is of primary interest for many branches of applied sciences. It is typically achieved by applying dimensionality reduction techniques mapping the considered data into lower dimensional space. This family of methods, while preserving local structures and features, often misses the global structure of the dataset. Clustering techniques are another class of methods operating on the data in the ambient space. They group together points that are similar according to a fixed similarity criteria, however unlike dimensionality reduction techniques, they do not provide information about the global organization of the data. Leveraging ideas from Topological Data Analysis, in this paper we provide an additional layer on the output of any clustering algorithm. Such data structure, ClusterGraph, provides information about the global layout of clusters, obtained from the considered clustering algorithm. Appropriate measures are provided to assess the quality and usefulness of the obtained representation. Subsequently the ClusterGraph, possibly with an appropriate structure--preserving simplification, can be visualized and used in synergy with state of the art exploratory data analysis techniques.

Unstructured Adiabatic Quantum Optimization: Optimality with Limitations

from arXiv: Data Structures and Algorithms

Authors: Arthur Braida, Shantanav Chakraborty, Alapan Chaudhuri, Joseph Cunningham, Rutvij Menavlikar, Leonardo Novo, Jérémie Roland

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on $n$-bits in time $\text{poly}(n) 2^{n/2}$. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of $\Omega(2^{n/2})$ has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is \#P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

Authors: Arthur Braida, Shantanav Chakraborty, Alapan Chaudhuri, Joseph Cunningham, Rutvij Menavlikar, Leonardo Novo, Jérémie Roland

In the circuit model of quantum computing, amplitude amplification techniques can be used to find solutions to NP-hard problems defined on $n$-bits in time $\text{poly}(n) 2^{n/2}$. In this work, we investigate whether such general statements can be made for adiabatic quantum optimization, as provable results regarding its performance are mostly unknown. Although a lower bound of $\Omega(2^{n/2})$ has existed in such a setting for over a decade, a purely adiabatic algorithm with this running time has been absent. We show that adiabatic quantum optimization using an unstructured search approach results in a running time that matches this lower bound (up to a polylogarithmic factor) for a broad class of classical local spin Hamiltonians. For this, it is necessary to bound the spectral gap throughout the adiabatic evolution and compute beforehand the position of the avoided crossing with sufficient precision so as to adapt the adiabatic schedule accordingly. However, we show that the position of the avoided crossing is approximately given by a quantity that depends on the degeneracies and inverse gaps of the problem Hamiltonian and is NP-hard to compute even within a low additive precision. Furthermore, computing it exactly (or nearly exactly) is \#P-hard. Our work indicates a possible limitation of adiabatic quantum optimization algorithms, leaving open the question of whether provable Grover-like speed-ups can be obtained for any optimization problem using this approach.

On Differentially Private String Distances

from arXiv: Data Structures and Algorithms

Authors: Jerry Yao-Chieh Hu, Erzhi Liu, Han Liu, Zhao Song, Lichen Zhang

Given a database of bit strings $A_1,\ldots,A_m\in \{0,1\}^n$, a fundamental data structure task is to estimate the distances between a given query $B\in \{0,1\}^n$ with all the strings in the database. In addition, one might further want to ensure the integrity of the database by releasing these distance statistics in a secure manner. In this work, we propose differentially private (DP) data structures for this type of tasks, with a focus on Hamming and edit distance. On top of the strong privacy guarantees, our data structures are also time- and space-efficient. In particular, our data structure is $\epsilon$-DP against any sequence of queries of arbitrary length, and for any query $B$ such that the maximum distance to any string in the database is at most $k$, we output $m$ distance estimates. Moreover, - For Hamming distance, our data structure answers any query in $\widetilde O(mk+n)$ time and each estimate deviates from the true distance by at most $\widetilde O(k/e^{\epsilon/\log k})$; - For edit distance, our data structure answers any query in $\widetilde O(mk^2+n)$ time and each estimate deviates from the true distance by at most $\widetilde O(k/e^{\epsilon/(\log k \log n)})$. For moderate $k$, both data structures support sublinear query operations. We obtain these results via a novel adaptation of the randomized response technique as a bit flipping procedure, applied to the sketched strings.

Authors: Jerry Yao-Chieh Hu, Erzhi Liu, Han Liu, Zhao Song, Lichen Zhang

Given a database of bit strings $A_1,\ldots,A_m\in \{0,1\}^n$, a fundamental data structure task is to estimate the distances between a given query $B\in \{0,1\}^n$ with all the strings in the database. In addition, one might further want to ensure the integrity of the database by releasing these distance statistics in a secure manner. In this work, we propose differentially private (DP) data structures for this type of tasks, with a focus on Hamming and edit distance. On top of the strong privacy guarantees, our data structures are also time- and space-efficient. In particular, our data structure is $\epsilon$-DP against any sequence of queries of arbitrary length, and for any query $B$ such that the maximum distance to any string in the database is at most $k$, we output $m$ distance estimates. Moreover, - For Hamming distance, our data structure answers any query in $\widetilde O(mk+n)$ time and each estimate deviates from the true distance by at most $\widetilde O(k/e^{\epsilon/\log k})$; - For edit distance, our data structure answers any query in $\widetilde O(mk^2+n)$ time and each estimate deviates from the true distance by at most $\widetilde O(k/e^{\epsilon/(\log k \log n)})$. For moderate $k$, both data structures support sublinear query operations. We obtain these results via a novel adaptation of the randomized response technique as a bit flipping procedure, applied to the sketched strings.

Separating Coverage and Submodular: Maximization Subject to a Cardinality Constraint

from arXiv: Data Structures and Algorithms

Authors: Yuval Filmus, Roy Schwartz, Alexander V. Smal

We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy algorithm provides an approximation of $1-1/e$ for both problems, and it is known that this guarantee is tight ([Nemhauser--Wolsey '78; Feige '98]). Thus, one would naturally assume that everything is resolved when considering the approximation guarantees of these two problems, as both exhibit the same tight approximation and hardness. In this work we show that this is not the case, and study both problems when the cardinality constraint is a constant fraction $c \in (0,1]$ of the ground set. We prove that monotone submodular maximization subject to a cardinality constraint admits an approximation of $1-(1-c)^{1/c}$; This approximation equals $1$ when $c=1$ and it gracefully degrades to $1-1/e$ when $c$ approaches $0$. Moreover, for every $c=1/s$ (for any integer $s \in \mathbb{N}$) we present a matching hardness. Surprisingly, for $c=1/2$ we prove that Maximum Coverage admits an approximation of $0.7533$, thus separating the two problems. To the best of our knowledge, this is the first known example of a well-studied maximization problem for which coverage and monotone submodular objectives exhibit a different best possible approximation.

Authors: Yuval Filmus, Roy Schwartz, Alexander V. Smal

We consider two classic problems: maximum coverage and monotone submodular maximization subject to a cardinality constraint. [Nemhauser--Wolsey--Fisher '78] proved that the greedy algorithm provides an approximation of $1-1/e$ for both problems, and it is known that this guarantee is tight ([Nemhauser--Wolsey '78; Feige '98]). Thus, one would naturally assume that everything is resolved when considering the approximation guarantees of these two problems, as both exhibit the same tight approximation and hardness. In this work we show that this is not the case, and study both problems when the cardinality constraint is a constant fraction $c \in (0,1]$ of the ground set. We prove that monotone submodular maximization subject to a cardinality constraint admits an approximation of $1-(1-c)^{1/c}$; This approximation equals $1$ when $c=1$ and it gracefully degrades to $1-1/e$ when $c$ approaches $0$. Moreover, for every $c=1/s$ (for any integer $s \in \mathbb{N}$) we present a matching hardness. Surprisingly, for $c=1/2$ we prove that Maximum Coverage admits an approximation of $0.7533$, thus separating the two problems. To the best of our knowledge, this is the first known example of a well-studied maximization problem for which coverage and monotone submodular objectives exhibit a different best possible approximation.

Recursive and iterative approaches to generate rotation Gray codes for stamp foldings and semi-meanders

from arXiv: Data Structures and Algorithms

Authors: Bowie Liu, Dennis Wong, Chan-Tong Lam, Marcus Im

We first present a simple recursive algorithm that generates cyclic rotation Gray codes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known Gray codes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li in [Electron. J. Comb. 19(2), 2012]. We then introduce an iterative algorithm that generates the same rotation Gray codes for stamp foldings and semi-meanders. Both the recursive and iterative algorithms generate stamp foldings and semi-meanders in constant amortized time and $O(n)$-amortized time per string respectively, using a linear amount of memory.

Authors: Bowie Liu, Dennis Wong, Chan-Tong Lam, Marcus Im

We first present a simple recursive algorithm that generates cyclic rotation Gray codes for stamp foldings and semi-meanders, where consecutive strings differ by a stamp rotation. These are the first known Gray codes for stamp foldings and semi-meanders, and we thus solve an open problem posted by Sawada and Li in [Electron. J. Comb. 19(2), 2012]. We then introduce an iterative algorithm that generates the same rotation Gray codes for stamp foldings and semi-meanders. Both the recursive and iterative algorithms generate stamp foldings and semi-meanders in constant amortized time and $O(n)$-amortized time per string respectively, using a linear amount of memory.

Near-Optimal Dimension Reduction for Facility Location

from arXiv: Data Structures and Algorithms

Authors: Lingxiao Huang, Shaofeng H. -C. Jiang, Robert Krauthgamer, Di Yue

Oblivious dimension reduction, \`{a} la the Johnson-Lindenstrauss (JL) Lemma, is a fundamental approach for processing high-dimensional data. We study this approach for Uniform Facility Location (UFL) on a Euclidean input $X\subset\mathbb{R}^d$, where facilities can lie in the ambient space (not restricted to $X$). Our main result is that target dimension $m=\tilde{O}(\epsilon^{-2}\mathrm{ddim})$ suffices to $(1+\epsilon)$-approximate the optimal value of UFL on inputs whose doubling dimension is bounded by $\mathrm{ddim}$. It significantly improves over previous results, that could only achieve $O(1)$-approximation [Narayanan, Silwal, Indyk, and Zamir, ICML 2021] or dimension $m=O(\epsilon^{-2}\log n)$ for $n=|X|$, which follows from [Makarychev, Makarychev, and Razenshteyn, STOC 2019]. Our oblivious dimension reduction has immediate implications to streaming and offline algorithms, by employing known algorithms for low dimension. In dynamic geometric streams, it implies a $(1+\epsilon)$-approximation algorithm that uses $O(\epsilon^{-1}\log n)^{\tilde{O}(\mathrm{ddim}/\epsilon^{2})}$ bits of space, which is the first streaming algorithm for UFL to utilize the doubling dimension. In the offline setting, it implies a $(1+\epsilon)$-approximation algorithm, which we further refine to run in time $( (1/\epsilon)^{\tilde{O}(\mathrm{ddim})} d + 2^{(1/\epsilon)^{\tilde{O}(\mathrm{ddim})}}) \cdot \tilde{O}(n) $. Prior work has a similar running time but requires some restriction on the facilities [Cohen-Addad, Feldmann and Saulpic, JACM 2021]. Our main technical contribution is a fast procedure to decompose an input $X$ into several $k$-median instances for small $k$. This decomposition is inspired by, but has several significant differences from [Czumaj, Lammersen, Monemizadeh and Sohler, SODA 2013], and is key to both our dimension reduction and our PTAS.

Authors: Lingxiao Huang, Shaofeng H. -C. Jiang, Robert Krauthgamer, Di Yue

Oblivious dimension reduction, \`{a} la the Johnson-Lindenstrauss (JL) Lemma, is a fundamental approach for processing high-dimensional data. We study this approach for Uniform Facility Location (UFL) on a Euclidean input $X\subset\mathbb{R}^d$, where facilities can lie in the ambient space (not restricted to $X$). Our main result is that target dimension $m=\tilde{O}(\epsilon^{-2}\mathrm{ddim})$ suffices to $(1+\epsilon)$-approximate the optimal value of UFL on inputs whose doubling dimension is bounded by $\mathrm{ddim}$. It significantly improves over previous results, that could only achieve $O(1)$-approximation [Narayanan, Silwal, Indyk, and Zamir, ICML 2021] or dimension $m=O(\epsilon^{-2}\log n)$ for $n=|X|$, which follows from [Makarychev, Makarychev, and Razenshteyn, STOC 2019]. Our oblivious dimension reduction has immediate implications to streaming and offline algorithms, by employing known algorithms for low dimension. In dynamic geometric streams, it implies a $(1+\epsilon)$-approximation algorithm that uses $O(\epsilon^{-1}\log n)^{\tilde{O}(\mathrm{ddim}/\epsilon^{2})}$ bits of space, which is the first streaming algorithm for UFL to utilize the doubling dimension. In the offline setting, it implies a $(1+\epsilon)$-approximation algorithm, which we further refine to run in time $( (1/\epsilon)^{\tilde{O}(\mathrm{ddim})} d + 2^{(1/\epsilon)^{\tilde{O}(\mathrm{ddim})}}) \cdot \tilde{O}(n) $. Prior work has a similar running time but requires some restriction on the facilities [Cohen-Addad, Feldmann and Saulpic, JACM 2021]. Our main technical contribution is a fast procedure to decompose an input $X$ into several $k$-median instances for small $k$. This decomposition is inspired by, but has several significant differences from [Czumaj, Lammersen, Monemizadeh and Sohler, SODA 2013], and is key to both our dimension reduction and our PTAS.

Fairness in Monotone $k$-submodular Maximization: Algorithms and Applications

from arXiv: Data Structures and Algorithms

Authors: Yanhui Zhu, Samik Basu, A. Pavan

Submodular optimization has become increasingly prominent in machine learning and fairness has drawn much attention. In this paper, we propose to study the fair $k$-submodular maximization problem and develop a $\frac{1}{3}$-approximation greedy algorithm with a running time of $\mathcal{O}(knB)$. To the best of our knowledge, our work is the first to incorporate fairness in the context of $k$-submodular maximization, and our theoretical guarantee matches the best-known $k$-submodular maximization results without fairness constraints. In addition, we have developed a faster threshold-based algorithm that achieves a $(\frac{1}{3} - \epsilon)$ approximation with $\mathcal{O}(\frac{kn}{\epsilon} \log \frac{B}{\epsilon})$ evaluations of the function $f$. Furthermore, for both algorithms, we provide approximation guarantees when the $k$-submodular function is not accessible but only can be approximately accessed. We have extensively validated our theoretical findings through empirical research and examined the practical implications of fairness. Specifically, we have addressed the question: ``What is the price of fairness?" through case studies on influence maximization with $k$ topics and sensor placement with $k$ types. The experimental results show that the fairness constraints do not significantly undermine the quality of solutions.

Authors: Yanhui Zhu, Samik Basu, A. Pavan

Submodular optimization has become increasingly prominent in machine learning and fairness has drawn much attention. In this paper, we propose to study the fair $k$-submodular maximization problem and develop a $\frac{1}{3}$-approximation greedy algorithm with a running time of $\mathcal{O}(knB)$. To the best of our knowledge, our work is the first to incorporate fairness in the context of $k$-submodular maximization, and our theoretical guarantee matches the best-known $k$-submodular maximization results without fairness constraints. In addition, we have developed a faster threshold-based algorithm that achieves a $(\frac{1}{3} - \epsilon)$ approximation with $\mathcal{O}(\frac{kn}{\epsilon} \log \frac{B}{\epsilon})$ evaluations of the function $f$. Furthermore, for both algorithms, we provide approximation guarantees when the $k$-submodular function is not accessible but only can be approximately accessed. We have extensively validated our theoretical findings through empirical research and examined the practical implications of fairness. Specifically, we have addressed the question: ``What is the price of fairness?" through case studies on influence maximization with $k$ topics and sensor placement with $k$ types. The experimental results show that the fairness constraints do not significantly undermine the quality of solutions.

Monotone Submodular Multiway Partition

from arXiv: Data Structures and Algorithms

Authors: Richard Bi, Karthekeyan Chandrasekaran, Soham Joshi

In submodular multiway partition (SUB-MP), the input is a non-negative submodular function $f:2^V \rightarrow \mathbb{R}_{\ge 0}$ given by an evaluation oracle along with $k$ terminals $t_1, t_2, \ldots, t_k\in V$. The goal is to find a partition $V_1, V_2, \ldots, V_k$ of $V$ with $t_i\in V_i$ for every $i\in [k]$ in order to minimize $\sum_{i=1}^k f(V_i)$. In this work, we focus on SUB-MP when the input function is monotone (termed MONO-SUB-MP). MONO-SUB-MP formulates partitioning problems over several interesting structures -- e.g., matrices, matroids, graphs, and hypergraphs. MONO-SUB-MP is NP-hard since the graph multiway cut problem can be cast as a special case. We investigate the approximability of MONO-SUB-MP: we show that it admits a $4/3$-approximation and does not admit a $(10/9-\epsilon)$-approximation for every constant $\epsilon>0$. Next, we study a special case of MONO-SUB-MP where the monotone submodular function of interest is the coverage function of an input graph, termed GRAPH-COVERAGE-MP. GRAPH-COVERAGE-MP is equivalent to the classic multiway cut problem for the purposes of exact optimization. We show that GRAPH-COVERAGE-MP admits a $1.125$-approximation and does not admit a $(1.00074-\epsilon)$-approximation for every constant $\epsilon>0$ assuming the Unique Games Conjecture. These results separate GRAPH-COVERAGE-MP from graph multiway cut in terms of approximability.

Authors: Richard Bi, Karthekeyan Chandrasekaran, Soham Joshi

In submodular multiway partition (SUB-MP), the input is a non-negative submodular function $f:2^V \rightarrow \mathbb{R}_{\ge 0}$ given by an evaluation oracle along with $k$ terminals $t_1, t_2, \ldots, t_k\in V$. The goal is to find a partition $V_1, V_2, \ldots, V_k$ of $V$ with $t_i\in V_i$ for every $i\in [k]$ in order to minimize $\sum_{i=1}^k f(V_i)$. In this work, we focus on SUB-MP when the input function is monotone (termed MONO-SUB-MP). MONO-SUB-MP formulates partitioning problems over several interesting structures -- e.g., matrices, matroids, graphs, and hypergraphs. MONO-SUB-MP is NP-hard since the graph multiway cut problem can be cast as a special case. We investigate the approximability of MONO-SUB-MP: we show that it admits a $4/3$-approximation and does not admit a $(10/9-\epsilon)$-approximation for every constant $\epsilon>0$. Next, we study a special case of MONO-SUB-MP where the monotone submodular function of interest is the coverage function of an input graph, termed GRAPH-COVERAGE-MP. GRAPH-COVERAGE-MP is equivalent to the classic multiway cut problem for the purposes of exact optimization. We show that GRAPH-COVERAGE-MP admits a $1.125$-approximation and does not admit a $(1.00074-\epsilon)$-approximation for every constant $\epsilon>0$ assuming the Unique Games Conjecture. These results separate GRAPH-COVERAGE-MP from graph multiway cut in terms of approximability.

Average-Distortion Sketching

from arXiv: Data Structures and Algorithms

Authors: Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, Tian Zhang

We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwise distances. The novelty is studying average-distortion: for any fixed (yet, arbitrary) distribution $\mu$ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from $\mu$. The notion generalizes average-distortion embeddings into $\ell_1$ [Rabinovich '03, Kush-Nikolov-Tang '21] as well as data-dependent locality-sensitive hashing [Andoni-Razenshteyn '15, Andoni-Naor-Nikolov-et-al. '18], which have been recently studied in the context of nearest neighbor search. $\bullet$ For all $p \in [1, \infty)$ and any $c$ larger than a fixed constant, we give an average-distortion sketch for $([\Delta]^d, \ell_p)$ with approximation $c$ and bit-complexity $\text{poly}(cp \cdot 2^{p/c} \cdot \log(d\Delta))$, which is provably impossible in (worst-case) sketching. $\bullet$ As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over $\ell_p$ (for large $p > 2$). The prior best approximation was $O(p)$ [Andoni-Naor-Nikolov-et.al '18, Kush-Nikolov-Tang '21], and we show it can be any $c$ larger than a fixed constant (irrespective of $p$) by using $n^{\text{poly}(cp \cdot 2^{p/c})}$ space. We give some evidence that $2^{\Omega(p/c)}$ space may be necessary by giving a lower bound on average-distortion sketches which produce a certain probabilistic certificate of farness (which our sketches crucially rely on).

Authors: Yiqiao Bao, Anubhav Baweja, Nicolas Menand, Erik Waingarten, Nathan White, Tian Zhang

We introduce average-distortion sketching for metric spaces. As in (worst-case) sketching, these algorithms compress points in a metric space while approximately recovering pairwise distances. The novelty is studying average-distortion: for any fixed (yet, arbitrary) distribution $\mu$ over the metric, the sketch should not over-estimate distances, and it should (approximately) preserve the average distance with respect to draws from $\mu$. The notion generalizes average-distortion embeddings into $\ell_1$ [Rabinovich '03, Kush-Nikolov-Tang '21] as well as data-dependent locality-sensitive hashing [Andoni-Razenshteyn '15, Andoni-Naor-Nikolov-et-al. '18], which have been recently studied in the context of nearest neighbor search. $\bullet$ For all $p \in [1, \infty)$ and any $c$ larger than a fixed constant, we give an average-distortion sketch for $([\Delta]^d, \ell_p)$ with approximation $c$ and bit-complexity $\text{poly}(cp \cdot 2^{p/c} \cdot \log(d\Delta))$, which is provably impossible in (worst-case) sketching. $\bullet$ As an application, we improve on the approximation of sublinear-time data structures for nearest neighbor search over $\ell_p$ (for large $p > 2$). The prior best approximation was $O(p)$ [Andoni-Naor-Nikolov-et.al '18, Kush-Nikolov-Tang '21], and we show it can be any $c$ larger than a fixed constant (irrespective of $p$) by using $n^{\text{poly}(cp \cdot 2^{p/c})}$ space. We give some evidence that $2^{\Omega(p/c)}$ space may be necessary by giving a lower bound on average-distortion sketches which produce a certain probabilistic certificate of farness (which our sketches crucially rely on).

On the cohesion and separability of average-link for hierarchical agglomerative clustering

from arXiv: Data Structures and Algorithms

Authors: Eduardo Sany Laber, Miguel Bastista

Average-link is widely recognized as one of the most popular and effective methods for building hierarchical agglomerative clustering. The available theoretical analyses show that this method has a much better approximation than other popular heuristics, as single-linkage and complete-linkage, regarding variants of Dasgupta's cost function [STOC 2016]. However, these analyses do not separate average-link from a random hierarchy and they are not appealing for metric spaces since every hierarchical clustering has a 1/2 approximation with regard to the variant of Dasgupta's function that is employed for dissimilarity measures [Moseley and Yang 2020]. In this paper, we present a comprehensive study of the performance of average-link in metric spaces, regarding several natural criteria that capture separability and cohesion and are more interpretable than Dasgupta's cost function and its variants. We also present experimental results with real datasets that, together with our theoretical analyses, suggest that average-link is a better choice than other related methods when both cohesion and separability are important goals.

Authors: Eduardo Sany Laber, Miguel Bastista

Average-link is widely recognized as one of the most popular and effective methods for building hierarchical agglomerative clustering. The available theoretical analyses show that this method has a much better approximation than other popular heuristics, as single-linkage and complete-linkage, regarding variants of Dasgupta's cost function [STOC 2016]. However, these analyses do not separate average-link from a random hierarchy and they are not appealing for metric spaces since every hierarchical clustering has a 1/2 approximation with regard to the variant of Dasgupta's function that is employed for dissimilarity measures [Moseley and Yang 2020]. In this paper, we present a comprehensive study of the performance of average-link in metric spaces, regarding several natural criteria that capture separability and cohesion and are more interpretable than Dasgupta's cost function and its variants. We also present experimental results with real datasets that, together with our theoretical analyses, suggest that average-link is a better choice than other related methods when both cohesion and separability are important goals.

Sunday, November 10

Our 2024 Postdoc Program is up

from TOC for Fairness

The Simons collaboration on the theory of algorithmic fairness is excited to announce our new postdoc program. We are seeking strong candidates from a diverse set of academic backgrounds and ...

The Simons collaboration on the theory of algorithmic fairness is excited to announce our new postdoc program. We are seeking strong candidates from a diverse set of academic backgrounds and personal experiences who want to work with one or more of the PIs on algorithmic fairness and responsible computing more broadly. We expect to be extending multiple offers.

By Omer Reingold

Faculty at University of Montreal (apply by January 10, 2025)

from CCI: jobs

The University of Montreal’s Department of Computer Science and Operations Research invites applications for a tenure-track faculty position at the rank of Assistant Professor in the area of theoretical computer science. Website: rh-carriere-dmz-eng.synchro.umontreal.ca/psc/rhprpr9_car_eng/EMPLOYEE/HRMS/c/HRS_HRAM_FL.HRS_CG_SEARCH_FL.GBL?Page=HRS_APP_JBPST_FL&Action=U&FOCUS=Applicant&SiteId=3&JobOpeningId=527501&PostingSeq=1& Email: directeur-TCS@iro.umontreal.ca

The University of Montreal’s Department of Computer Science and Operations Research invites applications for a tenure-track faculty position at the rank of Assistant Professor in the area of theoretical computer science.

Website: https://rh-carriere-dmz-eng.synchro.umontreal.ca/psc/rhprpr9_car_eng/EMPLOYEE/HRMS/c/HRS_HRAM_FL.HRS_CG_SEARCH_FL.GBL?Page=HRS_APP_JBPST_FL&Action=U&FOCUS=Applicant&SiteId=3&JobOpeningId=527501&PostingSeq=1&
Email: directeur-TCS@iro.umontreal.ca

By shacharlovett

Saturday, November 09

News for October 2024

from Property Testing Review

Four* papers on property testing last month! Lower bounds, upper bounds, distribution testing, quantum, and a new testing model! * at least four. If we missed any, please let us know in the comments! Lower Bounds for Convexity Testing, by Xi Chen, Anindya De, Shivam Nadimpalli, Rocco Servedio, and Erik Waingarten (arXiv). You’re given a […]

Four* papers on property testing last month! Lower bounds, upper bounds, distribution testing, quantum, and a new testing model!

* at least four. If we missed any, please let us know in the comments!

Lower Bounds for Convexity Testing, by Xi Chen, Anindya De, Shivam Nadimpalli, Rocco Servedio, and Erik Waingarten (arXiv). You’re given a membership oracle to a set \(S\) in \(\mathbb{R}^n\) (that is, query access to its indicator function \(f_S\colon \mathbb{R}^n\to \{0,1\}\)), and asked to decide if this set is convex, or “far from it”. This is a very natural and seemingly basic question— of course, we need to define what “far” means here, and the natural (normal, one may say) choice of underlying measure in \(\mathbb{R}^n\) is the standard Gaussian measure: \(d(S,T) = \Pr_{\mathcal{N}(0,I_n)}[ x \in S\Delta T]\).
Previous algorithms for this convexity testing question (and its tolerant testing analogue) are non-adaptive, and have \(2^{\tilde{O}(\sqrt{n})}\) query complexity. This paper shows that this is not just unfortunate, but also necessary: every non-adaptive tolerant tester for this question must make \(2^{\Omega(\sqrt[4]{n}}\) queries, and every (possibly adaptive) one-sided tester must have polynomial query complexity.

Replicable Uniformity Testing, by Sihan Liu and Christopher Ye (arXiv). In property testing, the algorithm must say YES with high probability on inputs which have the property, and NO with high probability on those which are far. On anything else, the algorithm is off the hook and can output either. This is typically considered to be fine, and, in any case, necessary to be able to obtain ultra-efficient algorithms. But what if, in this third case, we wanted to put the algorithm partially back on that hook, and required it to be consistent? The algorithm can answer either YES or NO, sure, but if I run it again on that same input, it should give the same answer with high probability. This is in line with a recent line of works on replicable algorithms, and is non-trivial to achieve in (the standard model of) distribution testing, where a distribution testing algorithm only gets to see random samples from the distribution, and thus needs to have a replicable behavior over that randomness. This paper introduces the question of replicable distribution testing, and provides both upper and lower bounds (essentially matching, with an asterisk) for the flagship task of uniformity testing.

Quantum property testing in sparse directed graphs, by Simon Apers, Frédéric Magniez, Sayantan Sen, and Dániel Szabó (arXiv). Graph property testing has a long and rich history in the classical setting, spanning more than two decades. There are several testing models, depending on whether the graph is dense, sparse, and directed or not: and even in the sparse, directed case, it is important to sometimes only allow outgoing edge queries. All these variants capture different meaningful scenarios, and relations and separations between them are known. This paper opens the direction of quantum testing for sparse graphs, either directed or not. The authors investigate what advantage quantum computers can bring for graph testing in this setting, and show one natural property for which a quadratic speedup exists: \(o(\sqrt{n})\) quantum queries in the outgoing-edge-query-only (unidrectional) sparse model, while classically \(\Omega(n)\) are necessary. They also show that this is not always the case: quantum testing of 3-colorability, as in the classical case, does not admit a \(o(n)\)-query tester.

Relative-error monotonicity testing, by Xi Chen, Anindya De, Yizhi Huang, Yuhao Li, Shivam Nadimpalli, Rocco Servedio, and Tianqi Yang (arXiv). Property testing of Boolean functions is defined “absolutely“: the distance between two functions is the fraction of the domain on which they differ, i.e., \(\displaystyle\frac{|f^{-1}(\{1\})\Delta g^{-1}(\{1\})|}{2^n}\)
This makes sense when the functions have a reasonable number of satisfying assignments: but may be much less meaningful for sparse functions, which only are non-zero on a \(o(1)\) fraction of the inputs—for instance, functions where “all the action” is concentrated in a tiny subcube of the hypercube. All these functions are vanishingly close to each other! To address this, the authors introduce a new distance notion, relative-error, where the distance from \(g\) to \(f\) is scaled by the sparsity of \(f\):
\(\displaystyle\frac{|f^{-1}(\{1\})\Delta g^{-1}(\{1\})|}{|f^{-1}(\{1\})|}\)
This requires a slightly different access model to avoid trivial impossibility results, so the tester is augmented with sampling access to satisfying assignments of \(f\), on top of query access to \(f\) (as otherwise it may just never even find one satisfying assignment). After introducing and motivating this testing model, the paper initiates its study in the specific case of testing monotonicity of Boolean functions.

By Clement Canonne

Friday, November 08

Postdoc at University of California, Berkeley (apply by December 15, 2024)

from CCI: jobs

The Simons Institute for the Theory of Computing invites applications for Simons-Berkeley Research Fellowships for the Fall 2025 semester. The Institute will host programs on “Complexity and Linear Algebra,” and “Algorithmic Foundations for Emerging Computing Technologies” in fall 2025. The application deadline is December 15, 2024. Website: simons.berkeley.edu/simons-berkeley-research-fellowship-call-applications Email: simonsassociatedirector@berkeley.edu

The Simons Institute for the Theory of Computing invites applications for Simons-Berkeley Research Fellowships for the Fall 2025 semester. The Institute will host programs on “Complexity and Linear Algebra,” and “Algorithmic Foundations for Emerging Computing Technologies” in fall 2025. The application deadline is December 15, 2024.

Website: https://simons.berkeley.edu/simons-berkeley-research-fellowship-call-applications
Email: simonsassociatedirector@berkeley.edu

By shacharlovett

Quantum Threshold is Powerful

from arXiv: Computational Complexity

Authors: Daniel Grier, Jackson Morris

In 2005, H{\o}yer and \v{S}palek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean functions as well as the quantum Fourier transform. They also asked what other multi-qubit gates could rival Fanout in terms of computational power, and suggested that the quantum Threshold gate might be one such candidate. Threshold is the gate that indicates if the Hamming weight of a classical basis state input is greater than some target value. We prove that Threshold is indeed powerful--there are polynomial-size constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity. Our proof is a generalization of a proof by Rosenthal that exponential-size constant-depth circuits with generalized Toffoli gates can compute Fanout. Our construction reveals that other quantum gates able to "weakly approximate" Parity can also be used as substitutes for Fanout.

Authors: Daniel Grier, Jackson Morris

In 2005, H{\o}yer and \v{S}palek showed that constant-depth quantum circuits augmented with multi-qubit Fanout gates are quite powerful, able to compute a wide variety of Boolean functions as well as the quantum Fourier transform. They also asked what other multi-qubit gates could rival Fanout in terms of computational power, and suggested that the quantum Threshold gate might be one such candidate. Threshold is the gate that indicates if the Hamming weight of a classical basis state input is greater than some target value. We prove that Threshold is indeed powerful--there are polynomial-size constant-depth quantum circuits with Threshold gates that compute Fanout to high fidelity. Our proof is a generalization of a proof by Rosenthal that exponential-size constant-depth circuits with generalized Toffoli gates can compute Fanout. Our construction reveals that other quantum gates able to "weakly approximate" Parity can also be used as substitutes for Fanout.

Convergence efficiency of quantum gates and circuits

from arXiv: Computational Complexity

Authors: Linghang Kong, Zimu Li, Zi-Wen Liu

We consider quantum circuit models where the gates are drawn from arbitrary gate ensembles given by probabilistic distributions over certain gate sets and circuit architectures, which we call stochastic quantum circuits. Of main interest in this work is the speed of convergence of stochastic circuits with different gate ensembles and circuit architectures to unitary t-designs. A key motivation for this theory is the varying preference for different gates and circuit architectures in different practical scenarios. In particular, it provides a versatile framework for devising efficient circuits for implementing $t$-designs and relevant applications including random circuit and scrambling experiments, as well as benchmarking the performance of gates and circuit architectures. We examine various important settings in depth. A key aspect of our study is an "ironed gadget" model, which allows us to systematically evaluate and compare the convergence efficiency of entangling gates and circuit architectures. Particularly notable results include i) gadgets of two-qubit gates with KAK coefficients $\left(\frac{\pi}{4}-\frac{1}{8}\arccos(\frac{1}{5}),\frac{\pi}{8},\frac{1}{8}\arccos(\frac{1}{5})\right)$ (which we call $\chi$ gates) directly form exact 2- and 3-designs; ii) the iSWAP gate family achieves the best efficiency for convergence to 2-designs under mild conjectures with numerical evidence, even outperforming the Haar-random gate, for generic many-body circuits; iii) iSWAP + complete graph achieve the best efficiency for convergence to 2-designs among all graph circuits. A variety of numerical results are provided to complement our analysis. We also derive robustness guarantees for our analysis against gate perturbations. Additionally, we provide cursory analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.

Authors: Linghang Kong, Zimu Li, Zi-Wen Liu

We consider quantum circuit models where the gates are drawn from arbitrary gate ensembles given by probabilistic distributions over certain gate sets and circuit architectures, which we call stochastic quantum circuits. Of main interest in this work is the speed of convergence of stochastic circuits with different gate ensembles and circuit architectures to unitary t-designs. A key motivation for this theory is the varying preference for different gates and circuit architectures in different practical scenarios. In particular, it provides a versatile framework for devising efficient circuits for implementing $t$-designs and relevant applications including random circuit and scrambling experiments, as well as benchmarking the performance of gates and circuit architectures. We examine various important settings in depth. A key aspect of our study is an "ironed gadget" model, which allows us to systematically evaluate and compare the convergence efficiency of entangling gates and circuit architectures. Particularly notable results include i) gadgets of two-qubit gates with KAK coefficients $\left(\frac{\pi}{4}-\frac{1}{8}\arccos(\frac{1}{5}),\frac{\pi}{8},\frac{1}{8}\arccos(\frac{1}{5})\right)$ (which we call $\chi$ gates) directly form exact 2- and 3-designs; ii) the iSWAP gate family achieves the best efficiency for convergence to 2-designs under mild conjectures with numerical evidence, even outperforming the Haar-random gate, for generic many-body circuits; iii) iSWAP + complete graph achieve the best efficiency for convergence to 2-designs among all graph circuits. A variety of numerical results are provided to complement our analysis. We also derive robustness guarantees for our analysis against gate perturbations. Additionally, we provide cursory analysis on gates with higher locality and found that the Margolus gate outperforms various other well-known gates.

Hardness of approximation for ground state problems

from arXiv: Computational Complexity

Authors: Sevag Gharibian, Carsten Hecht

After nearly two decades of research, the question of a quantum PCP theorem for quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a result, proving QMA-hardness of approximation for ground state energy estimation has remained elusive. Recently, it was shown [Bittel, Gharibian, Kliesch, CCC 2023] that a natural problem involving variational quantum circuits is QCMA-hard to approximate within ratio N^(1-eps) for any eps > 0 and N the input size. Unfortunately, this problem was not related to quantum CSPs, leaving the question of hardness of approximation for quantum CSPs open. In this work, we show that if instead of focusing on ground state energies, one considers computing properties of the ground space, QCMA-hardness of computing ground space properties can be shown. In particular, we show that it is (1) QCMA-complete within ratio N^(1-eps) to approximate the Ground State Connectivity problem (GSCON), and (2) QCMA-hard within the same ratio to estimate the amount of entanglement of a local Hamiltonian's ground state, denoted Ground State Entanglement (GSE). As a bonus, a simplification of our construction yields NP-completeness of approximation for a natural k-SAT reconfiguration problem, to be contrasted with the recent PCP-based PSPACE hardness of approximation results for a different definition of k-SAT reconfiguration [Karthik C.S. and Manurangsi, 2023, and Hirahara, Ohsaka, STOC 2024].

Authors: Sevag Gharibian, Carsten Hecht

After nearly two decades of research, the question of a quantum PCP theorem for quantum Constraint Satisfaction Problems (CSPs) remains wide open. As a result, proving QMA-hardness of approximation for ground state energy estimation has remained elusive. Recently, it was shown [Bittel, Gharibian, Kliesch, CCC 2023] that a natural problem involving variational quantum circuits is QCMA-hard to approximate within ratio N^(1-eps) for any eps > 0 and N the input size. Unfortunately, this problem was not related to quantum CSPs, leaving the question of hardness of approximation for quantum CSPs open. In this work, we show that if instead of focusing on ground state energies, one considers computing properties of the ground space, QCMA-hardness of computing ground space properties can be shown. In particular, we show that it is (1) QCMA-complete within ratio N^(1-eps) to approximate the Ground State Connectivity problem (GSCON), and (2) QCMA-hard within the same ratio to estimate the amount of entanglement of a local Hamiltonian's ground state, denoted Ground State Entanglement (GSE). As a bonus, a simplification of our construction yields NP-completeness of approximation for a natural k-SAT reconfiguration problem, to be contrasted with the recent PCP-based PSPACE hardness of approximation results for a different definition of k-SAT reconfiguration [Karthik C.S. and Manurangsi, 2023, and Hirahara, Ohsaka, STOC 2024].

Complexity theory of orbit closure intersection for tensors: reductions, completeness, and graph isomorphism hardness

from arXiv: Computational Complexity

Authors: Vladimir Lysikov, Michael Walter

Many natural computational problems in computer science, mathematics, physics, and other sciences amount to deciding if two objects are equivalent. Often this equivalence is defined in terms of group actions. A natural question is to ask when two objects can be distinguished by polynomial functions that are invariant under the group action. For finite groups, this is the usual notion of equivalence, but for continuous groups like the general linear groups it gives rise to a new notion, called orbit closure intersection. It captures, among others, the graph isomorphism problem, noncommutative PIT, null cone problems in invariant theory, equivalence problems for tensor networks, and the classification of multiparty quantum states. Despite recent algorithmic progress in celebrated special cases, the computational complexity of general orbit closure intersection problems is currently quite unclear. In particular, tensors seem to give rise to the most difficult problems. In this work we start a systematic study of orbit closure intersection from the complexity-theoretic viewpoint. To this end, we define a complexity class TOCI that captures the power of orbit closure intersection problems for general tensor actions, give an appropriate notion of algebraic reductions that imply polynomial-time reductions in the usual sense, but are amenable to invariant-theoretic techniques, identify natural tensor problems that are complete for TOCI, including the equivalence of 2D tensor networks with constant physical dimension, and show that the graph isomorphism problem can be reduced to these complete problems, hence GI$\subseteq$TOCI. As such, our work establishes the first lower bound on the computational complexity of orbit closure intersection problems, and it explains the difficulty of finding unconditional polynomial-time algorithms beyond special cases, as has been observed in the literature.

Authors: Vladimir Lysikov, Michael Walter

Many natural computational problems in computer science, mathematics, physics, and other sciences amount to deciding if two objects are equivalent. Often this equivalence is defined in terms of group actions. A natural question is to ask when two objects can be distinguished by polynomial functions that are invariant under the group action. For finite groups, this is the usual notion of equivalence, but for continuous groups like the general linear groups it gives rise to a new notion, called orbit closure intersection. It captures, among others, the graph isomorphism problem, noncommutative PIT, null cone problems in invariant theory, equivalence problems for tensor networks, and the classification of multiparty quantum states. Despite recent algorithmic progress in celebrated special cases, the computational complexity of general orbit closure intersection problems is currently quite unclear. In particular, tensors seem to give rise to the most difficult problems. In this work we start a systematic study of orbit closure intersection from the complexity-theoretic viewpoint. To this end, we define a complexity class TOCI that captures the power of orbit closure intersection problems for general tensor actions, give an appropriate notion of algebraic reductions that imply polynomial-time reductions in the usual sense, but are amenable to invariant-theoretic techniques, identify natural tensor problems that are complete for TOCI, including the equivalence of 2D tensor networks with constant physical dimension, and show that the graph isomorphism problem can be reduced to these complete problems, hence GI$\subseteq$TOCI. As such, our work establishes the first lower bound on the computational complexity of orbit closure intersection problems, and it explains the difficulty of finding unconditional polynomial-time algorithms beyond special cases, as has been observed in the literature.

On the average-case hardness of BosonSampling

from arXiv: Computational Complexity

Authors: Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez

BosonSampling is a popular candidate for near-term quantum advantage, which has now been experimentally implemented several times. The original proposal of Aaronson and Arkhipov from 2011 showed that classical hardness of BosonSampling is implied by a proof of the "Gaussian Permanent Estimation" conjecture. This conjecture states that $e^{-n\log{n}-n-O(\log n)}$ additive error estimates to the output probability of most random BosonSampling experiments are $\#P$-hard. Proving this conjecture has since become the central question in the theory of quantum advantage. In this work we make progress by proving that $e^{-n\log n -n - O(n^\delta)}$ additive error estimates to output probabilities of most random BosonSampling experiments are $\#P$-hard, for any $\delta>0$. In the process, we circumvent all known barrier results for proving the hardness of BosonSampling experiments. This is nearly the robustness needed to prove hardness of BosonSampling -- the remaining hurdle is now "merely" to show that the $n^\delta$ in the exponent can be improved to $O(\log n).$ We also obtain an analogous result for Random Circuit Sampling. Our result allows us to show, for the first time, a hardness of classical sampling result for random BosonSampling experiments, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-e^{-O(n)}$, unless the Polynomial Hierarchy collapses.

Authors: Adam Bouland, Ishaun Datta, Bill Fefferman, Felipe Hernandez

BosonSampling is a popular candidate for near-term quantum advantage, which has now been experimentally implemented several times. The original proposal of Aaronson and Arkhipov from 2011 showed that classical hardness of BosonSampling is implied by a proof of the "Gaussian Permanent Estimation" conjecture. This conjecture states that $e^{-n\log{n}-n-O(\log n)}$ additive error estimates to the output probability of most random BosonSampling experiments are $\#P$-hard. Proving this conjecture has since become the central question in the theory of quantum advantage. In this work we make progress by proving that $e^{-n\log n -n - O(n^\delta)}$ additive error estimates to output probabilities of most random BosonSampling experiments are $\#P$-hard, for any $\delta>0$. In the process, we circumvent all known barrier results for proving the hardness of BosonSampling experiments. This is nearly the robustness needed to prove hardness of BosonSampling -- the remaining hurdle is now "merely" to show that the $n^\delta$ in the exponent can be improved to $O(\log n).$ We also obtain an analogous result for Random Circuit Sampling. Our result allows us to show, for the first time, a hardness of classical sampling result for random BosonSampling experiments, under an anticoncentration conjecture. Specifically, we prove the impossibility of multiplicative-error sampling from random BosonSampling experiments with probability $1-e^{-O(n)}$, unless the Polynomial Hierarchy collapses.

The Computational Complexity of Variational Inequalities and Applications in Game Theory

from arXiv: Computational Complexity

Authors: Bruce M. Kapron, Koosha Samieefar

We present a computational formulation for the approximate version of several variational inequality problems, investigating their computational complexity and establishing PPAD-completeness. Examining applications in computational game theory, we specifically focus on two key concepts: resilient Nash equilibrium, and multi-leader-follower games -- domains traditionally known for the absence of general solutions. In the presence of standard assumptions and relaxation techniques, we formulate problem versions for such games that are expressible in terms of variational inequalities, ultimately leading to proofs of PPAD-completeness.

Authors: Bruce M. Kapron, Koosha Samieefar

We present a computational formulation for the approximate version of several variational inequality problems, investigating their computational complexity and establishing PPAD-completeness. Examining applications in computational game theory, we specifically focus on two key concepts: resilient Nash equilibrium, and multi-leader-follower games -- domains traditionally known for the absence of general solutions. In the presence of standard assumptions and relaxation techniques, we formulate problem versions for such games that are expressible in terms of variational inequalities, ultimately leading to proofs of PPAD-completeness.

On the hardness of learning ground state entanglement of geometrically local Hamiltonians

from arXiv: Computational Complexity

Authors: Adam Bouland, Chenyi Zhang, Zixin Zhou

Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In this work we study the computational complexity of this problem, given the Hamiltonian as input. Our main result is that to show it is cryptographically hard to determine if the ground state of a geometrically local, polynomially gapped Hamiltonian on qudits ($d=O(1)$) has near-area law vs near-volume law entanglement. This improves prior work of Bouland et al. (arXiv:2311.12017) showing this for non-geometrically local Hamiltonians. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our proof works by constructing a novel form of public-key pseudo-entanglement which is highly space-efficient, and combining this with a modification of Gottesman and Irani's quantum Turing machine to Hamiltonian construction. Our work suggests that the problem of learning so-called "gapless" quantum phases of matter might be intractable.

Authors: Adam Bouland, Chenyi Zhang, Zixin Zhou

Characterizing the entanglement structure of ground states of local Hamiltonians is a fundamental problem in quantum information. In this work we study the computational complexity of this problem, given the Hamiltonian as input. Our main result is that to show it is cryptographically hard to determine if the ground state of a geometrically local, polynomially gapped Hamiltonian on qudits ($d=O(1)$) has near-area law vs near-volume law entanglement. This improves prior work of Bouland et al. (arXiv:2311.12017) showing this for non-geometrically local Hamiltonians. In particular we show this problem is roughly factoring-hard in 1D, and LWE-hard in 2D. Our proof works by constructing a novel form of public-key pseudo-entanglement which is highly space-efficient, and combining this with a modification of Gottesman and Irani's quantum Turing machine to Hamiltonian construction. Our work suggests that the problem of learning so-called "gapless" quantum phases of matter might be intractable.

Uniformity testing when you have the source code

from arXiv: Data Structures and Algorithms

Authors: Clément L. Canonne, Robin Kothari, Ryan O'Donnell

We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the distribution. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on $[d]$ or $\epsilon$-far from uniform in total variation distance. More generally, we consider identity testing, which is the task of deciding if the output distribution equals a known hypothesis distribution, or is $\epsilon$-far from it. For both problems, the previous best known upper bound was $O(\min\{d^{1/3}/\epsilon^{2},d^{1/2}/\epsilon\})$. Here we improve the upper bound to $O(\min\{d^{1/3}/\epsilon^{4/3}, d^{1/2}/\epsilon\})$, which we conjecture is optimal.

Authors: Clément L. Canonne, Robin Kothari, Ryan O'Donnell

We study quantum algorithms for verifying properties of the output probability distribution of a classical or quantum circuit, given access to the source code that generates the distribution. We consider the basic task of uniformity testing, which is to decide if the output distribution is uniform on $[d]$ or $\epsilon$-far from uniform in total variation distance. More generally, we consider identity testing, which is the task of deciding if the output distribution equals a known hypothesis distribution, or is $\epsilon$-far from it. For both problems, the previous best known upper bound was $O(\min\{d^{1/3}/\epsilon^{2},d^{1/2}/\epsilon\})$. Here we improve the upper bound to $O(\min\{d^{1/3}/\epsilon^{4/3}, d^{1/2}/\epsilon\})$, which we conjecture is optimal.

On the Complexity of 2-club Cluster Editing with Vertex Splitting

from arXiv: Data Structures and Algorithms

Authors: Faisal N. Abu-Khzam, Tom Davot, Lucas Isenmann, Sergio Thoumi

Editing a graph to obtain a disjoint union of s-clubs is one of the models for correlation clustering, which seeks a partition of the vertex set of a graph so that elements of each resulting set are close enough according to some given criterion. For example, in the case of editing into s-clubs, the criterion is proximity since any pair of vertices (in an s-club) are within a distance of s from each other. In this work we consider the vertex splitting operation, which allows a vertex to belong to more than one cluster. This operation was studied as one of the parameters associated with the Cluster Editing problem. We study the complexity and parameterized complexity of the s-Club Cluster Edge Deletion with Vertex Splitting and s-Club Cluster Vertex Splitting problems. Both problems are shown to be NP-Complete and APX-hard. On the positive side, we show that both problems are Fixed-Parameter Tractable with respect to the number of allowed editing operations and that s-Club Cluster Vertex Splitting is solvable in polynomial-time on the class of forests.

Authors: Faisal N. Abu-Khzam, Tom Davot, Lucas Isenmann, Sergio Thoumi

Editing a graph to obtain a disjoint union of s-clubs is one of the models for correlation clustering, which seeks a partition of the vertex set of a graph so that elements of each resulting set are close enough according to some given criterion. For example, in the case of editing into s-clubs, the criterion is proximity since any pair of vertices (in an s-club) are within a distance of s from each other. In this work we consider the vertex splitting operation, which allows a vertex to belong to more than one cluster. This operation was studied as one of the parameters associated with the Cluster Editing problem. We study the complexity and parameterized complexity of the s-Club Cluster Edge Deletion with Vertex Splitting and s-Club Cluster Vertex Splitting problems. Both problems are shown to be NP-Complete and APX-hard. On the positive side, we show that both problems are Fixed-Parameter Tractable with respect to the number of allowed editing operations and that s-Club Cluster Vertex Splitting is solvable in polynomial-time on the class of forests.

Quantum speedups in solving near-symmetric optimization problems by low-depth QAOA

from arXiv: Data Structures and Algorithms

Authors: Ashley Montanaro, Leo Zhou

We present new advances in achieving exponential quantum speedups for solving optimization problems by low-depth quantum algorithms. Specifically, we focus on families of combinatorial optimization problems that exhibit symmetry and contain planted solutions. We rigorously prove that the 1-step Quantum Approximate Optimization Algorithm (QAOA) can achieve a success probability of $\Omega(1/\sqrt{n})$, and sometimes $\Omega(1)$, for finding the exact solution in many cases. Furthermore, we construct near-symmetric optimization problems by randomly sampling the individual clauses of symmetric problems, and prove that the QAOA maintains a strong success probability in this setting even when the symmetry is broken. Finally, we construct various families of near-symmetric Max-SAT problems and benchmark state-of-the-art classical solvers, discovering instances where all known classical algorithms require exponential time. Therefore, our results indicate that low-depth QAOA could achieve an exponential quantum speedup for optimization problems.

Authors: Ashley Montanaro, Leo Zhou

We present new advances in achieving exponential quantum speedups for solving optimization problems by low-depth quantum algorithms. Specifically, we focus on families of combinatorial optimization problems that exhibit symmetry and contain planted solutions. We rigorously prove that the 1-step Quantum Approximate Optimization Algorithm (QAOA) can achieve a success probability of $\Omega(1/\sqrt{n})$, and sometimes $\Omega(1)$, for finding the exact solution in many cases. Furthermore, we construct near-symmetric optimization problems by randomly sampling the individual clauses of symmetric problems, and prove that the QAOA maintains a strong success probability in this setting even when the symmetry is broken. Finally, we construct various families of near-symmetric Max-SAT problems and benchmark state-of-the-art classical solvers, discovering instances where all known classical algorithms require exponential time. Therefore, our results indicate that low-depth QAOA could achieve an exponential quantum speedup for optimization problems.

Faster feasibility for dynamic flows and transshipments on temporal networks

from arXiv: Data Structures and Algorithms

Authors: Kristin Sheridan, Shuchi Chawla

In this paper we study flow problems on temporal networks, where edge capacities and travel times change over time. We consider a network with $n$ nodes and $m$ edges where the capacity and length of each edge is a piecewise constant function, and use $\mu=\Omega(m)$ to denote the total number of pieces in all of the $2m$ functions. Our goal is to design exact algorithms for various flow problems that run in time polynomial in the parameter $\mu$. Importantly, the algorithms we design are strongly polynomial, i.e. have no dependence on the capacities, flow value, or the time horizon of the flow process, all of which can be exponentially large relative to the other parameters; and return an integral flow when all input parameters are integral. Our main result is an algorithm for checking feasibility of a dynamic transshipment problem on temporal networks -- given multiple sources and sinks with supply and demand values, is it possible to satisfy the desired supplies and demands within a given time horizon? We develop a fast ($O(\mu^3)$ time) algorithm for this feasibility problem when the input network has a certain canonical form, by exploiting the cut structure of the associated time expanded network. We then adapt an approach of \cite{hoppe2000} to show how other flow problems on temporal networks can be reduced to the canonical format. For computing dynamic transshipments on temporal networks, this results in a $O(\mu^7)$ time algorithm, whereas the previous best integral exact algorithm runs in time $\tilde O(\mu^{19})$. We achieve similar improvements for other flow problems on temporal networks.

Authors: Kristin Sheridan, Shuchi Chawla

In this paper we study flow problems on temporal networks, where edge capacities and travel times change over time. We consider a network with $n$ nodes and $m$ edges where the capacity and length of each edge is a piecewise constant function, and use $\mu=\Omega(m)$ to denote the total number of pieces in all of the $2m$ functions. Our goal is to design exact algorithms for various flow problems that run in time polynomial in the parameter $\mu$. Importantly, the algorithms we design are strongly polynomial, i.e. have no dependence on the capacities, flow value, or the time horizon of the flow process, all of which can be exponentially large relative to the other parameters; and return an integral flow when all input parameters are integral. Our main result is an algorithm for checking feasibility of a dynamic transshipment problem on temporal networks -- given multiple sources and sinks with supply and demand values, is it possible to satisfy the desired supplies and demands within a given time horizon? We develop a fast ($O(\mu^3)$ time) algorithm for this feasibility problem when the input network has a certain canonical form, by exploiting the cut structure of the associated time expanded network. We then adapt an approach of \cite{hoppe2000} to show how other flow problems on temporal networks can be reduced to the canonical format. For computing dynamic transshipments on temporal networks, this results in a $O(\mu^7)$ time algorithm, whereas the previous best integral exact algorithm runs in time $\tilde O(\mu^{19})$. We achieve similar improvements for other flow problems on temporal networks.

Unbounded Error Correcting Codes

from arXiv: Data Structures and Algorithms

Authors: Klim Efremenko, Or Zamir

We introduce a variant of Error Correcting Codes with no predetermined length. An Unbounded ECC with rate $R$ and distance $\varepsilon$ is an encoding of a possibly infinite message into a possibly infinite codeword, such that for every large enough $k$ we may recover the first $Rk$ symbols of the message from the first $k$ symbols of the codeword -- even when up to $\frac{1}{2}\varepsilon k$ of these codeword symbols are adversarially corrupted. We study unbounded codes over a binary alphabet in the regime of small distance $\varepsilon$, and obtain nearly-tight upper and lower bounds in several natural settings. We show that the optimal rate of such a code is between $R<1-\Omega(\sqrt{\varepsilon})$ and $R>1-O\left(\sqrt{\varepsilon\log\log\left(1/\varepsilon\right)}\right)$. Surprisingly, our construction is non-linear, and we show that the optimal rate of a linear unbounded code is the asymptotically worse $R=1-\Theta\left(\sqrt{\varepsilon\log\left(1/\varepsilon\right)}\right)$. In the setting of random noise, the optimal rate of unbounded codes improves and matches the rate of standard codes at $R=1-\Theta({\varepsilon\log{\left(1/\varepsilon\right)}})$.

Authors: Klim Efremenko, Or Zamir

We introduce a variant of Error Correcting Codes with no predetermined length. An Unbounded ECC with rate $R$ and distance $\varepsilon$ is an encoding of a possibly infinite message into a possibly infinite codeword, such that for every large enough $k$ we may recover the first $Rk$ symbols of the message from the first $k$ symbols of the codeword -- even when up to $\frac{1}{2}\varepsilon k$ of these codeword symbols are adversarially corrupted. We study unbounded codes over a binary alphabet in the regime of small distance $\varepsilon$, and obtain nearly-tight upper and lower bounds in several natural settings. We show that the optimal rate of such a code is between $R<1-\Omega(\sqrt{\varepsilon})$ and $R>1-O\left(\sqrt{\varepsilon\log\log\left(1/\varepsilon\right)}\right)$. Surprisingly, our construction is non-linear, and we show that the optimal rate of a linear unbounded code is the asymptotically worse $R=1-\Theta\left(\sqrt{\varepsilon\log\left(1/\varepsilon\right)}\right)$. In the setting of random noise, the optimal rate of unbounded codes improves and matches the rate of standard codes at $R=1-\Theta({\varepsilon\log{\left(1/\varepsilon\right)}})$.

Approximate counting of permutation patterns

from arXiv: Data Structures and Algorithms

Authors: Omri Ben-Eliezer, Slobodan Mitrović, Pranjal Srivastava

We consider the problem of counting the copies of a length-$k$ pattern $\sigma$ in a sequence $f \colon [n] \to \mathbb{R}$, where a copy is a subset of indices $i_1 < \ldots < i_k \in [n]$ such that $f(i_j) < f(i_\ell)$ if and only if $\sigma(j) < \sigma(\ell)$. This problem is motivated by a range of connections and applications in ranking, nonparametric statistics, combinatorics, and fine-grained complexity, especially when $k$ is a small fixed constant. Recent advances have significantly improved our understanding of counting and detecting patterns. Guillemot and Marx [2014] demonstrated that the detection variant is solvable in $O(n)$ time for any fixed $k$. Their proof has laid the foundations for the discovery of the twin-width, a concept that has notably advanced parameterized complexity in recent years. Counting, in contrast, is harder: it has a conditional lower bound of $n^{\Omega(k / \log k)}$ [Berendsohn, Kozma, and Marx 2019] and is expected to be polynomially harder than detection as early as $k = 4$, given its equivalence to counting $4$-cycles in graphs [Dudek and Gawrychowski, 2020]. In this work, we design a deterministic near-linear time $(1+\varepsilon)$-approximation algorithm for counting $\sigma$-copies in $f$ for all $k \leq 5$. Combined with the conditional lower bound for $k=4$, this establishes the first known separation between approximate and exact algorithms for pattern counting. Interestingly, our algorithm leverages the Birg\'e decomposition -- a sublinear tool for monotone distributions widely used in distribution testing -- which, to our knowledge, has not been applied in a pattern counting context before.

Authors: Omri Ben-Eliezer, Slobodan Mitrović, Pranjal Srivastava

We consider the problem of counting the copies of a length-$k$ pattern $\sigma$ in a sequence $f \colon [n] \to \mathbb{R}$, where a copy is a subset of indices $i_1 < \ldots < i_k \in [n]$ such that $f(i_j) < f(i_\ell)$ if and only if $\sigma(j) < \sigma(\ell)$. This problem is motivated by a range of connections and applications in ranking, nonparametric statistics, combinatorics, and fine-grained complexity, especially when $k$ is a small fixed constant. Recent advances have significantly improved our understanding of counting and detecting patterns. Guillemot and Marx [2014] demonstrated that the detection variant is solvable in $O(n)$ time for any fixed $k$. Their proof has laid the foundations for the discovery of the twin-width, a concept that has notably advanced parameterized complexity in recent years. Counting, in contrast, is harder: it has a conditional lower bound of $n^{\Omega(k / \log k)}$ [Berendsohn, Kozma, and Marx 2019] and is expected to be polynomially harder than detection as early as $k = 4$, given its equivalence to counting $4$-cycles in graphs [Dudek and Gawrychowski, 2020]. In this work, we design a deterministic near-linear time $(1+\varepsilon)$-approximation algorithm for counting $\sigma$-copies in $f$ for all $k \leq 5$. Combined with the conditional lower bound for $k=4$, this establishes the first known separation between approximate and exact algorithms for pattern counting. Interestingly, our algorithm leverages the Birg\'e decomposition -- a sublinear tool for monotone distributions widely used in distribution testing -- which, to our knowledge, has not been applied in a pattern counting context before.

A Generalisation of Voter Model: Influential Nodes and Convergence Properties

from arXiv: Data Structures and Algorithms

Authors: Abhiram Manohara, Ahad N. Zehmakan

Consider an undirected graph G, representing a social network, where each node is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of individuals connections, individuals with neutral opinion on a topic, and individuals who are reluctant to update their opinion. To address these issues, we introduce and study a generalisation of the voter model. Motivating by campaigning strategies, we study the problem of selecting a set of seeds blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP- hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms. We also investigate the convergence properties of the model. We prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the period (the number of states in convergence) divides the length of all cycles in the graph.

Authors: Abhiram Manohara, Ahad N. Zehmakan

Consider an undirected graph G, representing a social network, where each node is blue or red, corresponding to positive or negative opinion on a topic. In the voter model, in discrete time rounds, each node picks a neighbour uniformly at random and adopts its colour. Despite its significant popularity, this model does not capture some fundamental real-world characteristics such as the difference in the strengths of individuals connections, individuals with neutral opinion on a topic, and individuals who are reluctant to update their opinion. To address these issues, we introduce and study a generalisation of the voter model. Motivating by campaigning strategies, we study the problem of selecting a set of seeds blue nodes to maximise the expected number of blue nodes after some rounds. We prove that the problem is NP- hard and provide a polynomial time approximation algorithm with the best possible approximation guarantee. Our experiments on real-world and synthetic graph data demonstrate that the proposed algorithm outperforms other algorithms. We also investigate the convergence properties of the model. We prove that the process could take an exponential number of rounds to converge. However, if we limit ourselves to strongly connected graphs, the convergence time is polynomial and the period (the number of states in convergence) divides the length of all cycles in the graph.

Mixing time of quantum Gibbs sampling for random sparse Hamiltonians

from arXiv: Data Structures and Algorithms

Authors: Akshar Ramkumar, Mehdi Soleimanifar

Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm by Chen, Kastoryano, and Gily\'en provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The running time of this algorithm depends on the mixing time of the corresponding quantum Markov chain, which has not been rigorously bounded except in the high-temperature regime. In this work, we establish a polylog(n) upper bound on its mixing time for various families of random n by n sparse Hamiltonians at any constant temperature. We further analyze how the choice of the jump operators for the algorithm and the spectral properties of these sparse Hamiltonians influence the mixing time. Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.

Authors: Akshar Ramkumar, Mehdi Soleimanifar

Providing evidence that quantum computers can efficiently prepare low-energy or thermal states of physically relevant interacting quantum systems is a major challenge in quantum information science. A newly developed quantum Gibbs sampling algorithm by Chen, Kastoryano, and Gily\'en provides an efficient simulation of the detailed-balanced dissipative dynamics of non-commutative quantum systems. The running time of this algorithm depends on the mixing time of the corresponding quantum Markov chain, which has not been rigorously bounded except in the high-temperature regime. In this work, we establish a polylog(n) upper bound on its mixing time for various families of random n by n sparse Hamiltonians at any constant temperature. We further analyze how the choice of the jump operators for the algorithm and the spectral properties of these sparse Hamiltonians influence the mixing time. Our result places this method for Gibbs sampling on par with other efficient algorithms for preparing low-energy states of quantumly easy Hamiltonians.

Fully Dynamic (Δ+1) Coloring Against Adaptive Adversaries

from arXiv: Data Structures and Algorithms

Authors: Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim

Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include $(\Delta+1)$ vertex coloring, maximal independent set, and maximal matching. For all three problems, there are randomized algorithms that maintain a valid solution after each edge insertion or deletion to the $n$-vertex graph by spending $\polylog n$ time, provided that the adversary is oblivious. However, none of these algorithms work against adaptive adversaries whose updates may depend on the output of the algorithm. In fact, even breaking the trivial bound of $O(n)$ against adaptive adversaries remains open for all three problems. For instance, in the case of $(\Delta+1)$ vertex coloring, the main challenge is that an adaptive adversary can keep inserting edges between vertices of the same color, necessitating a recoloring of one of the endpoints. The trivial algorithm would simply scan all neighbors of one endpoint to find a new available color (which always exists) in $O(n)$ time. In this paper, we break this linear barrier for the $(\Delta+1)$ vertex coloring problem. Our algorithm is randomized, and maintains a valid $(\Delta+1)$ vertex coloring after each edge update by spending $\widetilde{O}(n^{8/9})$ time with high probability.

Authors: Soheil Behnezhad, Rajmohan Rajaraman, Omer Wasim

Over the years, there has been extensive work on fully dynamic algorithms for classic graph problems that admit greedy solutions. Examples include $(\Delta+1)$ vertex coloring, maximal independent set, and maximal matching. For all three problems, there are randomized algorithms that maintain a valid solution after each edge insertion or deletion to the $n$-vertex graph by spending $\polylog n$ time, provided that the adversary is oblivious. However, none of these algorithms work against adaptive adversaries whose updates may depend on the output of the algorithm. In fact, even breaking the trivial bound of $O(n)$ against adaptive adversaries remains open for all three problems. For instance, in the case of $(\Delta+1)$ vertex coloring, the main challenge is that an adaptive adversary can keep inserting edges between vertices of the same color, necessitating a recoloring of one of the endpoints. The trivial algorithm would simply scan all neighbors of one endpoint to find a new available color (which always exists) in $O(n)$ time. In this paper, we break this linear barrier for the $(\Delta+1)$ vertex coloring problem. Our algorithm is randomized, and maintains a valid $(\Delta+1)$ vertex coloring after each edge update by spending $\widetilde{O}(n^{8/9})$ time with high probability.

Statistical-Computational Trade-offs for Greedy Recursive Partitioning Estimators

from arXiv: Data Structures and Algorithms

Authors: Yan Shuo Tan, Jason M. Klusowski, Krishnakumar Balasubramanian

Models based on recursive partitioning such as decision trees and their ensembles are popular for high-dimensional regression as they can potentially avoid the curse of dimensionality. Because empirical risk minimization (ERM) is computationally infeasible, these models are typically trained using greedy algorithms. Although effective in many cases, these algorithms have been empirically observed to get stuck at local optima. We explore this phenomenon in the context of learning sparse regression functions over $d$ binary features, showing that when the true regression function $f^*$ does not satisfy the so-called Merged Staircase Property (MSP), greedy training requires $\exp(\Omega(d))$ to achieve low estimation error. Conversely, when $f^*$ does satisfy MSP, greedy training can attain small estimation error with only $O(\log d)$ samples. This performance mirrors that of two-layer neural networks trained with stochastic gradient descent (SGD) in the mean-field regime, thereby establishing a head-to-head comparison between SGD-trained neural networks and greedy recursive partitioning estimators. Furthermore, ERM-trained recursive partitioning estimators achieve low estimation error with $O(\log d)$ samples irrespective of whether $f^*$ satisfies MSP, thereby demonstrating a statistical-computational trade-off for greedy training. Our proofs are based on a novel interpretation of greedy recursive partitioning using stochastic process theory and a coupling technique that may be of independent interest.

Authors: Yan Shuo Tan, Jason M. Klusowski, Krishnakumar Balasubramanian

Models based on recursive partitioning such as decision trees and their ensembles are popular for high-dimensional regression as they can potentially avoid the curse of dimensionality. Because empirical risk minimization (ERM) is computationally infeasible, these models are typically trained using greedy algorithms. Although effective in many cases, these algorithms have been empirically observed to get stuck at local optima. We explore this phenomenon in the context of learning sparse regression functions over $d$ binary features, showing that when the true regression function $f^*$ does not satisfy the so-called Merged Staircase Property (MSP), greedy training requires $\exp(\Omega(d))$ to achieve low estimation error. Conversely, when $f^*$ does satisfy MSP, greedy training can attain small estimation error with only $O(\log d)$ samples. This performance mirrors that of two-layer neural networks trained with stochastic gradient descent (SGD) in the mean-field regime, thereby establishing a head-to-head comparison between SGD-trained neural networks and greedy recursive partitioning estimators. Furthermore, ERM-trained recursive partitioning estimators achieve low estimation error with $O(\log d)$ samples irrespective of whether $f^*$ satisfies MSP, thereby demonstrating a statistical-computational trade-off for greedy training. Our proofs are based on a novel interpretation of greedy recursive partitioning using stochastic process theory and a coupling technique that may be of independent interest.

Scalable DP-SGD: Shuffling vs. Poisson Subsampling

from arXiv: Data Structures and Algorithms

Authors: Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang

We provide new lower bounds on the privacy guarantee of the multi-epoch Adaptive Batch Linear Queries (ABLQ) mechanism with shuffled batch sampling, demonstrating substantial gaps when compared to Poisson subsampling; prior analysis was limited to a single epoch. Since the privacy analysis of Differentially Private Stochastic Gradient Descent (DP-SGD) is obtained by analyzing the ABLQ mechanism, this brings into serious question the common practice of implementing shuffling-based DP-SGD, but reporting privacy parameters as if Poisson subsampling was used. To understand the impact of this gap on the utility of trained machine learning models, we introduce a practical approach to implement Poisson subsampling at scale using massively parallel computation, and efficiently train models with the same. We compare the utility of models trained with Poisson-subsampling-based DP-SGD, and the optimistic estimates of utility when using shuffling, via our new lower bounds on the privacy guarantee of ABLQ with shuffling.

Authors: Lynn Chua, Badih Ghazi, Pritish Kamath, Ravi Kumar, Pasin Manurangsi, Amer Sinha, Chiyuan Zhang

We provide new lower bounds on the privacy guarantee of the multi-epoch Adaptive Batch Linear Queries (ABLQ) mechanism with shuffled batch sampling, demonstrating substantial gaps when compared to Poisson subsampling; prior analysis was limited to a single epoch. Since the privacy analysis of Differentially Private Stochastic Gradient Descent (DP-SGD) is obtained by analyzing the ABLQ mechanism, this brings into serious question the common practice of implementing shuffling-based DP-SGD, but reporting privacy parameters as if Poisson subsampling was used. To understand the impact of this gap on the utility of trained machine learning models, we introduce a practical approach to implement Poisson subsampling at scale using massively parallel computation, and efficiently train models with the same. We compare the utility of models trained with Poisson-subsampling-based DP-SGD, and the optimistic estimates of utility when using shuffling, via our new lower bounds on the privacy guarantee of ABLQ with shuffling.

Assistant Professor at University of California, San Diego (apply by January 1, 2025)

from CCI: jobs

The UC San Diego Department of Computer Science and Engineering (CSE) invites applications for multiple tenure-track faculty positions at the Assistant Professor rank. The department is looking for exceptional candidates in all areas of Computer Science and Engineering. Website: apol-recruit.ucsd.edu/JPF04123 Email: nherrera@ucsd.edu

The UC San Diego Department of Computer Science and Engineering (CSE) invites applications for multiple tenure-track faculty positions at the Assistant Professor rank. The department is looking for exceptional candidates in all areas of Computer Science and Engineering.

Website: https://apol-recruit.ucsd.edu/JPF04123
Email: nherrera@ucsd.edu

By shacharlovett

Thursday, November 07

(Open Rank) Professor in the Paul G. Allen School of Computer Science & Engineering at University of Washington (apply by November 15, 2024)

from CCI: jobs

The University of Washington’s Paul G. Allen School of Computer Science & Engineering invites applications for multiple tenure-track positions at all ranks across all areas in both Computer Science and Computer Engineering. Deadline is for priority consideration. Website: www.cs.washington.edu/faculty_candidates Email: frc@cs.washington.edu

The University of Washington’s Paul G. Allen School of Computer Science & Engineering invites applications for multiple tenure-track positions at all ranks across all areas in both Computer Science and Computer Engineering. Deadline is for priority consideration.

Website: https://www.cs.washington.edu/faculty_candidates
Email: frc@cs.washington.edu

By shacharlovett

TR24-173 | Lower Bounds in the Query-with-Sketch Model and a Barrier in Derandomizing BPL | Songhua He, Yuanzhi Li, Periklis Papakonstantinou, Xin Yang

from ECCC Papers

This work makes two distinct yet related contributions. The first contribution is a new information-theoretic model, the query-with-sketch model, and tools to show lower bounds within it. The second contribution is conceptual, technically builds on the first contribution, and is a barrier in the derandomization of randomized logarithmic space (BPL). (1) The query-with-sketch model generalizes the query complexity model for computing multi-bit functions $f:\{0,1\}^N\to\{0,1\}^M$. In this model, computation unfolds in two phases. Initially, the algorithm sends an agent to evaluate an arbitrary but length-restricted sketch of the input. Subsequently, the algorithm proceeds with queries. The main technical contribution is a lower bound in this model for the Approximate Matrix Powering (AMP) problem. To that end, we introduce a constrained form of conditional min-entropy that characterizes the number of queries in the model. We bound this entropy by developing tools that blend geometry, a generalization of tools from Lipschitz analysis for polynomials and low-distortion spaces, and probability theory. The main result is that AMP requires polynomial query complexity or super-polylogarithmic sketch size. We note that AMP and the query-with-sketch model are natural and interesting in their own right, in addition to the following conceptual contribution. (2) Derandomizing BPL is an open question in computational complexity. The most successful derandomization algorithms of BPL make recursive use of pseudorandom generators or similar pseudorandom objects. The best-known derandomization places BPL inside DSPACE$(\frac{\log^{3/2} n}{\sqrt{\log\log n}})$. We ask whether these algorithms can be substantially improved if we keep fixed the pseudorandom object and the main idea, which is to approximate $M^n$ of the computation matrix $M$ by relying on intermediate powers such as $M^{n/2}$. We answer this question in the negative in a recursive generalization of the query-with-sketch model. We show that in this recursive and space-bounded model AMP needs super-polynomially many queries (time) or super-polylogarithmic sketch size (space). Specifically, in our model an algorithm that uses approximations of elements of the matrix $M^{n/2}$ to approximate an element of $M^n$, it must first determine the values of these elements in $M^{n/2}$ and it can do this recursively. Other than this restriction, an algorithm is free to determine arbitrarily how to organize the recursion and how to use the bounded space. The conceptual takeaway is the "intermediate powers barrier", which indicates that fully derandomizing BPL cannot rely on a natural, recursive use of approximated intermediate powers.

This work makes two distinct yet related contributions. The first contribution is a new information-theoretic model, the query-with-sketch model, and tools to show lower bounds within it. The second contribution is conceptual, technically builds on the first contribution, and is a barrier in the derandomization of randomized logarithmic space (BPL). (1) The query-with-sketch model generalizes the query complexity model for computing multi-bit functions $f:\{0,1\}^N\to\{0,1\}^M$. In this model, computation unfolds in two phases. Initially, the algorithm sends an agent to evaluate an arbitrary but length-restricted sketch of the input. Subsequently, the algorithm proceeds with queries. The main technical contribution is a lower bound in this model for the Approximate Matrix Powering (AMP) problem. To that end, we introduce a constrained form of conditional min-entropy that characterizes the number of queries in the model. We bound this entropy by developing tools that blend geometry, a generalization of tools from Lipschitz analysis for polynomials and low-distortion spaces, and probability theory. The main result is that AMP requires polynomial query complexity or super-polylogarithmic sketch size. We note that AMP and the query-with-sketch model are natural and interesting in their own right, in addition to the following conceptual contribution. (2) Derandomizing BPL is an open question in computational complexity. The most successful derandomization algorithms of BPL make recursive use of pseudorandom generators or similar pseudorandom objects. The best-known derandomization places BPL inside DSPACE$(\frac{\log^{3/2} n}{\sqrt{\log\log n}})$. We ask whether these algorithms can be substantially improved if we keep fixed the pseudorandom object and the main idea, which is to approximate $M^n$ of the computation matrix $M$ by relying on intermediate powers such as $M^{n/2}$. We answer this question in the negative in a recursive generalization of the query-with-sketch model. We show that in this recursive and space-bounded model AMP needs super-polynomially many queries (time) or super-polylogarithmic sketch size (space). Specifically, in our model an algorithm that uses approximations of elements of the matrix $M^{n/2}$ to approximate an element of $M^n$, it must first determine the values of these elements in $M^{n/2}$ and it can do this recursively. Other than this restriction, an algorithm is free to determine arbitrarily how to organize the recursion and how to use the bounded space. The conceptual takeaway is the "intermediate powers barrier", which indicates that fully derandomizing BPL cannot rely on a natural, recursive use of approximated intermediate powers.

The Central Path

from Ben Recht

The brilliant simplicity of primal-dual interior point methods.

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

How do we jump from unconstrained optimization to constrained optimization? In unconstrained optimization, we are free to follow any direction downhill, so we can let simple local search run without worrying. In constrained optimization, we require a solution matching a specification. How do we ensure local search finds such a point?

There are many methods, and the next couple of weeks will explore several. We’re going to skip the convergence proofs in this class. Our goal is to understand the mechanics of how these algorithms work so that we can tune our models to match what these methods are best suited for.

I want to start with a class of algorithms that sounds the most intimidating but is in many ways the most simple: primal-dual interior point methods. Optimality conditions for convex problems are almost always a set of equations and inequality constraints. Primal-dual interior point methods solve the equations with a damped Newton method, where the step size is chosen so that the inequality constraints remain valid for all iterations.

Suppose we want to solve a nonlinear equation F(x)=0, where F is maps n-vectors to n-vectors. We additionally impose the restriction that our solution lies in a convex set C. For a simple motivating example, let’s say we want to solve the system

A valid solution is x=0, y=-1. Another is x=1, y=0. What if we want an algorithm guaranteed to find the solution where x and y are nonnegative? This is a typical constraint in interior point methods.

Interior point methods thus seed Newton’s method with a candidate point in the set C and then take damped Newton steps constrained to always lie in C. The meta-algorithm is 

start with x in the interior of C
while norm(F(x)) is large:
    compute the Netwon direction v at x
    find a large step size t such that x+tv is in the interior of C
    set x to x+tv

This algorithm is aptly dubbed an interior point method because it always maintains an iterate in the interior of C.

The primal-dual part of the algorithm comes in when we are solving the optimality conditions of a convex optimization problem. In this case, the equations we aim to solve are the equalities from the KKT conditions, and the convex set C is the set of tuples of primal feasible and dual feasible points. Let me now turn to a concrete optimization problem to make this explicit. 

We have been studying the general constrained optimization problem

Let’s fix that the primal variable is n-dimensional, and there are m inequality contractions and p equality constraints. The KKT conditions are

Here, s and 𝝀 are the dual variables, aka the Lagrange multipliers. The first three lines here are, as promised, equations. The total number of equations is n+p+m. There are n primal variables and p+m Lagrange multipliers. Aha, we have a square nonlinear system. The convex set C is 

We can use our meta-interior point method to solve this problem. We first find a candidate x that strictly satisfies the inequality constraints. We also initialize the variable s to a positive vector. Then we take damped Newton steps, ensuring the iterates stay inside C. 

The only hitch to making this work is guaranteeing that we can take large step sizes. This is the sticking point in all of the convergence analyses. The problem is that the KKT conditions demand that the optimal solution lie on the boundary of C. As you get close to that boundary, the algorithm will have a hard time making progress. 

The main brilliant fix, inspired by a decade of working on interior point methods, is to take Newton steps on a relaxed set of equations.

These are the same as the KKT conditions, except that we enforce the product of the f_i(x) and s_i to be equal to the positive scalar t. Namely, their product must equal -t. This can only happen if the solution is well inside the interior of C. For convex problems, every value of t defines a unique point in C. As t goes to 0, these points converge to the optimal solution of the optimization problem. The path of solutions to these modified KKT conditions is called the central path

Targeting the central path gives interior point methods more wiggle room to take larger steps. Keeping iterates close to the central path guarantees convergence of the primal-dual interior point method. This works astonishingly well in practice. There are simple rules for how to make t smaller as you progress so that the step sizes remain reasonable as you approach the boundary. Since Newton’s converges quadratically near optimality, you can adjust the path parameter to take advantage of this fast convergence and push your iterates to complementary slackness. 

The details of how to make these things precisely work in practice aren’t too hard. I highly recommend Steve Wright’s book Primal-Dual Interior-Point Methods for the gory details. Steve also gave a fantastic tutorial on these methods at the Simons Institute. Though it’s been more trendy as of late to always run first-order methods, hand coding up an implementation of the primal-dual interior point method isn’t hard. It’s even easier if you use automatic differentiation tools. For modestly sized problems where matrix inversion is feasible, these methods are hard to beat.

Subscribe now

By Ben Recht

TR24-172 | Quantum Communication Advantage in TFNP | Mika Göös, Tom Gur, Siddhartha Jain, Jiawei Li

from ECCC Papers

We exhibit a total search problem whose communication complexity in the quantum SMP (simultaneous message passing) model is exponentially smaller than in the classical two-way randomized model. Moreover, the quantum protocol is computationally efficient and its solutions are classically verifiable, that is, the problem lies in the communication analogue of the class TFNP. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry (JACM 2024). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication protocols.

We exhibit a total search problem whose communication complexity in the quantum SMP (simultaneous message passing) model is exponentially smaller than in the classical two-way randomized model. Moreover, the quantum protocol is computationally efficient and its solutions are classically verifiable, that is, the problem lies in the communication analogue of the class TFNP. Our problem is a bipartite version of a query complexity problem recently introduced by Yamakawa and Zhandry (JACM 2024). We prove the classical lower bound using the structure-vs-randomness paradigm for analyzing communication protocols.

Higher Education Under Trump

from Computational Complexity

It feels eerie as pretty much everyone seemingly avoided talking about the election. But Trump back in the White House will likely have a profound effect on US Colleges and Universities. Trump is no fan of universities and his vice-president once proclaimed "the professors are the enemy". 

While most US universities act outside of federal control, almost all of them take Federal funds in scholarships and grants and Trump could use that as a lever to push his policies.

Now Trump is always unpredictable and the courts could step in but here is what could happen.

International Students

I still remember Trump's ban on Iranians in the US and what it meant to our students and faculty at Georgia Tech. While that thankfully got blocked by the courts, who knows what will happen in this next administration.

International students at all levels in higher ed play a major role in increasing both the intellectual and financial strengths of universities. International Students, especially from some countries like China, may have a harder time coming to or staying in the US under a Trump administration or may have less desire to do so.

On the other hand last June Trump said "What I want to do and what I will do is, you graduate from a college, I think you should get automatically, as part of your diploma, a Green Card to be able to stay in this country." If that's true that will greatly increase interest among foreign students but I doubt he will carry it out.
Student Loan Forgiveness Not going to happen

Title IX University Title IX offices get whiplash with each change of administration. Expect Title IX (sex discrimination) protections to be watered down and eliminated for transgender individuals. 
Look at Republican States Trump may try to apply Republican policies at state universities to all universities as a whole: Dismantling DEI efforts, weakening tenure protection, allowing campus carry of guns on campus, and "free speech" policies while limiting what can be taught and cracking down on protests.
Accreditation Trump and republicans are no fan of accreditation, and Trump has threatened that he will replace accreditors to enforce certain points of view.

By Lance Fortnow

It feels eerie as pretty much everyone seemingly avoided talking about the election. But Trump back in the White House will likely have a profound effect on US Colleges and Universities. Trump is no fan of universities and his vice-president once proclaimed "the professors are the enemy". 

While most US universities act outside of federal control, almost all of them take Federal funds in scholarships and grants and Trump could use that as a lever to push his policies.

Now Trump is always unpredictable and the courts could step in but here is what could happen.

International Students

I still remember Trump's ban on Iranians in the US and what it meant to our students and faculty at Georgia Tech. While that thankfully got blocked by the courts, who knows what will happen in this next administration.

International students at all levels in higher ed play a major role in increasing both the intellectual and financial strengths of universities. International Students, especially from some countries like China, may have a harder time coming to or staying in the US under a Trump administration or may have less desire to do so.

On the other hand last June Trump said "What I want to do and what I will do is, you graduate from a college, I think you should get automatically, as part of your diploma, a Green Card to be able to stay in this country." If that's true that will greatly increase interest among foreign students but I doubt he will carry it out.

Student Loan Forgiveness
Not going to happen

Title IX
University Title IX offices get whiplash with each change of administration. Expect Title IX (sex discrimination) protections to be watered down and eliminated for transgender individuals. 

Look at Republican States
Trump may try to apply Republican policies at state universities to all universities as a whole: Dismantling DEI efforts, weakening tenure protection, allowing campus carry of guns on campus, and "free speech" policies while limiting what can be taught and cracking down on protests.

Accreditation
Trump and republicans are no fan of accreditation, and Trump has threatened that he will replace accreditors to enforce certain points of view.

By Lance Fortnow

Condensing Against Online Adversaries

from arXiv: Computational Complexity

Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model for which extraction is impossible [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks where at least $g$ of the blocks are good (independent and have some min-entropy) and the remaining bad blocks are controlled by an online adversary where each bad block can be arbitrarily correlated with any block that appears before it. The existence of condensers was studied in [CGR, FOCS'24]. They proved condensing impossibility results for various values of $g, \ell$ and showed the existence of condensers matching the impossibility results in the case when $n$ is extremely large compared to $\ell$. In this work, we make significant progress on proving the existence of condensers with strong parameters in almost all parameter regimes, even when $n$ is a large enough constant and $\ell$ is growing. This almost resolves the question of the existence of condensers for oNOSF sources, except when $n$ is a small constant. We construct the first explicit condensers for oNOSF sources, achieve parameters that match the existential results of [CGR, FOCS'24], and obtain an improved construction for transforming low-entropy oNOSF sources into uniform ones. We find applications of our results to collective coin flipping and sampling, well-studied problems in fault-tolerant distributed computing. We use our condensers to provide simple protocols for these problems. To understand the case of small $n$, we focus on $n=1$ which corresponds to online non-oblivious bit-fixing (oNOBF) sources. We initiate a study of a new, natural notion of influence of Boolean functions which we call online influence. We establish tight bounds on the total online influence of Boolean functions, implying extraction lower bounds.

Authors: Eshan Chattopadhyay, Mohit Gurumukhani, Noam Ringach

We investigate the task of deterministically condensing randomness from Online Non-Oblivious Symbol Fixing (oNOSF) sources, a natural model for which extraction is impossible [AORSV, EUROCRYPT'20]. A $(g,\ell)$-oNOSF source is a sequence of $\ell$ blocks where at least $g$ of the blocks are good (independent and have some min-entropy) and the remaining bad blocks are controlled by an online adversary where each bad block can be arbitrarily correlated with any block that appears before it. The existence of condensers was studied in [CGR, FOCS'24]. They proved condensing impossibility results for various values of $g, \ell$ and showed the existence of condensers matching the impossibility results in the case when $n$ is extremely large compared to $\ell$. In this work, we make significant progress on proving the existence of condensers with strong parameters in almost all parameter regimes, even when $n$ is a large enough constant and $\ell$ is growing. This almost resolves the question of the existence of condensers for oNOSF sources, except when $n$ is a small constant. We construct the first explicit condensers for oNOSF sources, achieve parameters that match the existential results of [CGR, FOCS'24], and obtain an improved construction for transforming low-entropy oNOSF sources into uniform ones. We find applications of our results to collective coin flipping and sampling, well-studied problems in fault-tolerant distributed computing. We use our condensers to provide simple protocols for these problems. To understand the case of small $n$, we focus on $n=1$ which corresponds to online non-oblivious bit-fixing (oNOBF) sources. We initiate a study of a new, natural notion of influence of Boolean functions which we call online influence. We establish tight bounds on the total online influence of Boolean functions, implying extraction lower bounds.

Revisiting BQP with Non-Collapsing Measurements

from arXiv: Computational Complexity

Authors: David Miloschewsky, Supartha Podder

The study of non-collapsing measurements was initiated by Aaronson, Bouland, Fitzsimons, and Lee, who showed that BQP, when equipped with the ability to perform non-collapsing measurements (denoted as PDQP), contains both BQP and SZK, yet still requires $\Omega (N^{1/4})$ queries to find an element in an unsorted list. By formulating an alternative equivalent model of PDQP, we prove the positive weighted adversary method, obtaining a variety of new lower bounds and establishing a trade-off between queries and non-collapsing measurements. The method allows us to examine the well-studied majority and element distinctness problems, while also tightening the bound for the search problem to $\Theta (N^{1/3})$. Additionally, we explore related settings, obtaining tight bounds in BQP with the ability to copy arbitrary states (called CBQP) and PDQP with non-adaptive queries.

Authors: David Miloschewsky, Supartha Podder

The study of non-collapsing measurements was initiated by Aaronson, Bouland, Fitzsimons, and Lee, who showed that BQP, when equipped with the ability to perform non-collapsing measurements (denoted as PDQP), contains both BQP and SZK, yet still requires $\Omega (N^{1/4})$ queries to find an element in an unsorted list. By formulating an alternative equivalent model of PDQP, we prove the positive weighted adversary method, obtaining a variety of new lower bounds and establishing a trade-off between queries and non-collapsing measurements. The method allows us to examine the well-studied majority and element distinctness problems, while also tightening the bound for the search problem to $\Theta (N^{1/3})$. Additionally, we explore related settings, obtaining tight bounds in BQP with the ability to copy arbitrary states (called CBQP) and PDQP with non-adaptive queries.

Rescheduling after vehicle failures in the multi-depot rural postman problem with rechargeable and reusable vehicles

from arXiv: Computational Complexity

Authors: Eashwar Sathyamurthy, Jeffrey W. Herrmann, Shapour Azarm

We present a centralized auction algorithm to solve the Multi-Depot Rural Postman Problem with Rechargeable and Reusable Vehicles (MD-RPP-RRV), focusing on rescheduling arc routing after vehicle failures. The problem involves finding heuristically obtained best feasible routes for multiple rechargeable and reusable vehicles with capacity constraints capable of performing multiple trips from multiple depots, with the possibility of vehicle failures. Our algorithm auctions the failed trips to active (non-failed) vehicles through local auctioning, modifying initial routes to handle dynamic vehicle failures efficiently. When a failure occurs, the algorithm searches for the best active vehicle to perform the failed trip and inserts the trip into that vehicle's route, which avoids a complete rescheduling and reduces the computational effort. We compare the algorithm's solutions against offline optimal solutions obtained from solving a Mixed Integer Linear Programming (MILP) formulation using the Gurobi solver; this formulation assumes that perfect information about the vehicle failures and failure times is given. The results demonstrate that the centralized auction algorithm produces solutions that are, in some cases, near optimal; moreover, the execution time for the proposed approach is much more consistent and is, for some instances, orders of magnitude less than the execution time of the Gurobi solver. The theoretical analysis provides an upper bound for the competitive ratio and computational complexity of our algorithm, offering a formal performance guarantee in dynamic failure scenarios.

Authors: Eashwar Sathyamurthy, Jeffrey W. Herrmann, Shapour Azarm

We present a centralized auction algorithm to solve the Multi-Depot Rural Postman Problem with Rechargeable and Reusable Vehicles (MD-RPP-RRV), focusing on rescheduling arc routing after vehicle failures. The problem involves finding heuristically obtained best feasible routes for multiple rechargeable and reusable vehicles with capacity constraints capable of performing multiple trips from multiple depots, with the possibility of vehicle failures. Our algorithm auctions the failed trips to active (non-failed) vehicles through local auctioning, modifying initial routes to handle dynamic vehicle failures efficiently. When a failure occurs, the algorithm searches for the best active vehicle to perform the failed trip and inserts the trip into that vehicle's route, which avoids a complete rescheduling and reduces the computational effort. We compare the algorithm's solutions against offline optimal solutions obtained from solving a Mixed Integer Linear Programming (MILP) formulation using the Gurobi solver; this formulation assumes that perfect information about the vehicle failures and failure times is given. The results demonstrate that the centralized auction algorithm produces solutions that are, in some cases, near optimal; moreover, the execution time for the proposed approach is much more consistent and is, for some instances, orders of magnitude less than the execution time of the Gurobi solver. The theoretical analysis provides an upper bound for the competitive ratio and computational complexity of our algorithm, offering a formal performance guarantee in dynamic failure scenarios.

On the satisfiability of random $3$-SAT formulas with $k$-wise independent clauses

from arXiv: Computational Complexity

Authors: Ioannis Caragiannis, Nick Gravin, Zhile Jiang

The problem of identifying the satisfiability threshold of random $3$-SAT formulas has received a lot of attention during the last decades and has inspired the study of other threshold phenomena in random combinatorial structures. The classical assumption in this line of research is that, for a given set of $n$ Boolean variables, each clause is drawn uniformly at random among all sets of three literals from these variables, independently from other clauses. Here, we keep the uniform distribution of each clause, but deviate significantly from the independence assumption and consider richer families of probability distributions. For integer parameters $n$, $m$, and $k$, we denote by $\DistFamily_k(n,m)$ the family of probability distributions that produce formulas with $m$ clauses, each selected uniformly at random from all sets of three literals from the $n$ variables, so that the clauses are $k$-wise independent. Our aim is to make general statements about the satisfiability or unsatisfiability of formulas produced by distributions in $\DistFamily_k(n,m)$ for different values of the parameters $n$, $m$, and $k$.

Authors: Ioannis Caragiannis, Nick Gravin, Zhile Jiang

The problem of identifying the satisfiability threshold of random $3$-SAT formulas has received a lot of attention during the last decades and has inspired the study of other threshold phenomena in random combinatorial structures. The classical assumption in this line of research is that, for a given set of $n$ Boolean variables, each clause is drawn uniformly at random among all sets of three literals from these variables, independently from other clauses. Here, we keep the uniform distribution of each clause, but deviate significantly from the independence assumption and consider richer families of probability distributions. For integer parameters $n$, $m$, and $k$, we denote by $\DistFamily_k(n,m)$ the family of probability distributions that produce formulas with $m$ clauses, each selected uniformly at random from all sets of three literals from the $n$ variables, so that the clauses are $k$-wise independent. Our aim is to make general statements about the satisfiability or unsatisfiability of formulas produced by distributions in $\DistFamily_k(n,m)$ for different values of the parameters $n$, $m$, and $k$.

Complexity Theory for Quantum Promise Problems

from arXiv: Computational Complexity

Authors: Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang, Jhih-Wei Shih

Quantum computing introduces many problems rooted in physics, asking to compute information from input quantum states. Determining the complexity of these problems has implications for both computer science and physics. However, as existing complexity theory primarily addresses problems with classical inputs and outputs, it lacks the framework to fully capture the complexity of quantum-input problems. This gap is relevant when studying the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework, as characterizing the security of quantum cryptographic primitives requires complexity classes for problems involving quantum inputs. To bridge this gap, we examine the complexity theory of quantum promise problems, which determine if input quantum states have certain properties. We focus on complexity classes p/mBQP, p/mQ(C)MA, $\mathrm{p/mQSZK_{hv}}$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states corresponding to any classical class C. We establish structural results, including complete problems, search-to-decision reductions, and relationships between classes. Notably, our findings reveal differences from classical counterparts, such as p/mQIP $\neq$ p/mPSPACE and $\mathrm{mcoQSZK_{hv}} \neq \mathrm{mQSZK_{hv}}$. As an application, we apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or $\mathrm{mQSZK_{hv}}$. We also show that the average-case hardness of $\mathrm{pQCZK_{hv}}$ implies the existence of EFI. These results provide new insights into Impagliazzo's worlds, establishing a connection between quantum cryptography and quantum promise complexity theory. We also extend our findings to quantum property testing and unitary synthesis, highlighting further applications of this new framework.

Authors: Nai-Hui Chia, Kai-Min Chung, Tzu-Hsiang Huang, Jhih-Wei Shih

Quantum computing introduces many problems rooted in physics, asking to compute information from input quantum states. Determining the complexity of these problems has implications for both computer science and physics. However, as existing complexity theory primarily addresses problems with classical inputs and outputs, it lacks the framework to fully capture the complexity of quantum-input problems. This gap is relevant when studying the relationship between quantum cryptography and complexity theory, especially within Impagliazzo's five worlds framework, as characterizing the security of quantum cryptographic primitives requires complexity classes for problems involving quantum inputs. To bridge this gap, we examine the complexity theory of quantum promise problems, which determine if input quantum states have certain properties. We focus on complexity classes p/mBQP, p/mQ(C)MA, $\mathrm{p/mQSZK_{hv}}$, p/mQIP, and p/mPSPACE, where "p/mC" denotes classes with pure (p) or mixed (m) states corresponding to any classical class C. We establish structural results, including complete problems, search-to-decision reductions, and relationships between classes. Notably, our findings reveal differences from classical counterparts, such as p/mQIP $\neq$ p/mPSPACE and $\mathrm{mcoQSZK_{hv}} \neq \mathrm{mQSZK_{hv}}$. As an application, we apply this framework to cryptography, showing that breaking one-way state generators, pseudorandom states, and EFI is bounded by mQCMA or $\mathrm{mQSZK_{hv}}$. We also show that the average-case hardness of $\mathrm{pQCZK_{hv}}$ implies the existence of EFI. These results provide new insights into Impagliazzo's worlds, establishing a connection between quantum cryptography and quantum promise complexity theory. We also extend our findings to quantum property testing and unitary synthesis, highlighting further applications of this new framework.

Algebraic metacomplexity and representation theory

from arXiv: Computational Complexity

Authors: Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Vladimir Lysikov

We prove that in the algebraic metacomplexity framework, the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. This means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, our result means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincar\'e--Birkhoff--Witt theorem for Lie algebras and on Gelfand--Tsetlin theory, for which we give the necessary comprehensive background.

Authors: Maxim van den Berg, Pranjal Dutta, Fulvio Gesmundo, Christian Ikenmeyer, Vladimir Lysikov

We prove that in the algebraic metacomplexity framework, the decomposition of metapolynomials into their isotypic components can be implemented efficiently, namely with only a quasipolynomial blowup in the circuit size. This means that many existing algebraic complexity lower bound proofs can be efficiently converted into isotypic lower bound proofs via highest weight metapolynomials, a notion studied in geometric complexity theory. In the context of algebraic natural proofs, our result means that without loss of generality algebraic natural proofs can be assumed to be isotypic. Our proof is built on the Poincar\'e--Birkhoff--Witt theorem for Lie algebras and on Gelfand--Tsetlin theory, for which we give the necessary comprehensive background.