Last Update

OPML feed of all feeds.

Subscribe to the Atom feed, RSS feed, or follow on Twitter, to stay up to date.

Source on GitHub.

Maintained by Nima Anari, Arnab Bhattacharyya, Gautam Kamath.

Powered by Pluto.

Theory of Computing Report

Monday, December 04

Where do Non-Primitive Recursive Functions come up NATURALLY?

from Computational Complexity

The following is a conversation between Clyde Kruskal and Bill Gasarch.

CLYDE:  Bill, a student, Ian Roberts,  asked me if there are any non-primitive recursive functions that people actually want to compute.

BILL: Off hand I would say no, but non-prim rec functions DO come up in natural ways.

CLYDE: That's not what he asked.

BILL: Even so, that's what I will blog about. OH, one more thing, why does he want to know?

CLYDE: Ask him directly. (BILL then emailed Ian)

BILL: Good question about NATURAL problems that are not prim-rec, but why do you want to know?

IAN:  Meyer and Richie proved (see here) that if you limit the control flow to IF statements, FOR loops with finite iterators then the class of functions you implement is  exactly the primitive recursive functions. So I was wondering if I could avoid ever using WHILE loops since they are harder to reason about. 

BILL: YES you COULD avoid ever using WHILE LOOPS; however, there are times when using them is the best way to go.

CLYDE: Bill, when is the last time you wrote a program? And LaTex does not count. 

BILL: Good point. Rather than take my word for it, let's ASK my readers. I'll add that to my list of RANDOM THOUGHTS ABOUT non-prim rec functions. 

SO, random thoughts on non-prim rec functions

0) Are there problems for which writing a WHILE loop is the way to go even though they are  not needed? 

1) HALT is not prim recursive and we want to compute it. Oh well. All future examples will be computable.

2) QUESTION: Are there simple programming languages so that HALT restricted to them is decidable but not primitive recursive? I suspect one could contrive such a language so I ask for both natural and contrived examples. 

3) The Paris-Harrington Numbers from Ramsey Theory are computable and  grow MUCH faster than prim rec. Indeed- they grow much faster than Ackermann's function. See Wikipedia Entry.

4) The Kanamori-McAloon Theorem from Ramsey theory is computable and grow MUCH faster than prim rec. Indeed- they grow much faster than Ackemann's function. See Wikipedia Entry. They are not as well known as the Paris-Harrington numbers. Hopefully this blog post will help that. 

5) Goodstein's Theorem yields numbers that are computable and grow MUCH faster than prim rec. Indeed, they grow much faster than Ackermann's function. See Wikipedia Entry and/or my blog post on them.

6) QUESTION: Of PH, KM, GOOD, which grows fastest? Second fastest? Third fastest? Perhaps some are tied.

6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. We know that there are some math games (e.g., the Hydra game) that are not prim recursive. Are there any FUN  games whose complexity is NOT prim recursive?

7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? It can be used to speed up Kruskal's MST algorithm, but that just takes the question back one step: Is MST a problem people really want to solve? I asked Lance and he asked chatty. For the results of that see here . The answer seems to be YES, though I wonder if the speedup that UNION-FIND gives is important. Union-Find is also used in the Hoshen-Kopelman Algorithm for (to quote Wikipedia) labeling clusters on a grid, where the grid is a regular network of  cells, with the cells being either occupied or unoccupied.  Other issues:  (a) is UNION-FIND hard to code up? Lance tells me that it is easy to code up.  (b) Is the constant reasonable?

8) Is the Ackerman Security Company called that since they claim that breaking their security is as hard as computing Ackerman's function? Unlikely- they spell it with only one n at the end. Even so, my class believed me when I told them that. 

9) The finite version of Kruskal's Tree Theorem YADA YADA YADA not prim rec. Wikipedia Entry

CLYDE: You can't YADA YADA YADA my Uncle Joe!

BILL: It's my party and you'll cry if you want to, cry if you want to, cry if you want to. (See here for Leslie Gore's song Its my party and I'll cry if I want to which is not about non primitive recursive functions. Also see her sequel Judy's turn to cry.  A much better song with a better message for teenagers is her You don't own me.)

CLYDE: Oh well. However, I'll make sure to tell that example to my class.


By gasarch

The following is a conversation between Clyde Kruskal and Bill Gasarch.

CLYDE:  Bill, a student, Ian Roberts,  asked me if there are any non-primitive recursive functions that people actually want to compute.

BILL: Off hand I would say no, but non-prim rec functions DO come up in natural ways.

CLYDE: That's not what he asked.

BILL: Even so, that's what I will blog about. OH, one more thing, why does he want to know?

CLYDE: Ask him directly. (BILL then emailed Ian)

BILL: Good question about NATURAL problems that are not prim-rec, but why do you want to know?

IAN:  Meyer and Richie proved (see here) that if you limit the control flow to IF statements, FOR loops with finite iterators then the class of functions you implement is  exactly the primitive recursive functions. So I was wondering if I could avoid ever using WHILE loops since they are harder to reason about. 

BILL: YES you COULD avoid ever using WHILE LOOPS; however, there are times when using them is the best way to go.

CLYDE: Bill, when is the last time you wrote a program? And LaTex does not count. 

BILL: Good point. Rather than take my word for it, let's ASK my readers. I'll add that to my list of RANDOM THOUGHTS ABOUT non-prim rec functions. 

SO, random thoughts on non-prim rec functions

0) Are there problems for which writing a WHILE loop is the way to go even though they are  not needed? 

1) HALT is not prim recursive and we want to compute it. Oh well. All future examples will be computable.

2) QUESTION: Are there simple programming languages so that HALT restricted to them is decidable but not primitive recursive? I suspect one could contrive such a language so I ask for both natural and contrived examples. 

3) The Paris-Harrington Numbers from Ramsey Theory are computable and  grow MUCH faster than prim rec. Indeed- they grow much faster than Ackermann's function. See Wikipedia Entry.

4) The Kanamori-McAloon Theorem from Ramsey theory is computable and grow MUCH faster than prim rec. Indeed- they grow much faster than Ackemann's function. See Wikipedia Entry. They are not as well known as the Paris-Harrington numbers. Hopefully this blog post will help that. 

5) Goodstein's Theorem yields numbers that are computable and grow MUCH faster than prim rec. Indeed, they grow much faster than Ackermann's function. See Wikipedia Entry and/or my blog post on them.

6) QUESTION: Of PH, KM, GOOD, which grows fastest? Second fastest? Third fastest? Perhaps some are tied.

6) QUESTION: We know that GO and CHESS have very high complexity, but are still prim recursive. We know that there are some math games (e.g., the Hydra game) that are not prim recursive. Are there any FUN  games whose complexity is NOT prim recursive?

7) Tarjan's UNION-FIND data structure has amortized complexity roughly O(n alpha(n)) where alpha(n) is the inverse of Ackermann's function. This is also a lower bound. See Wikipedia entry on disjoint-set data structure. QUESTION: Is Tarjan's UNION-FIND data structure actually used? It can be used to speed up Kruskal's MST algorithm, but that just takes the question back one step: Is MST a problem people really want to solve? I asked Lance and he asked chatty. For the results of that see here . The answer seems to be YES, though I wonder if the speedup that UNION-FIND gives is important. Union-Find is also used in the Hoshen-Kopelman Algorithm for (to quote Wikipedia) labeling clusters on a grid, where the grid is a regular network of  cells, with the cells being either occupied or unoccupied.  Other issues:  (a) is UNION-FIND hard to code up? Lance tells me that it is easy to code up.  (b) Is the constant reasonable?

8) Is the Ackerman Security Company called that since they claim that breaking their security is as hard as computing Ackerman's function? Unlikely- they spell it with only one n at the end. Even so, my class believed me when I told them that. 

9) The finite version of Kruskal's Tree Theorem YADA YADA YADA not prim rec. Wikipedia Entry

CLYDE: You can't YADA YADA YADA my Uncle Joe!

BILL: It's my party and you'll cry if you want to, cry if you want to, cry if you want to. (See here for Leslie Gore's song Its my party and I'll cry if I want to which is not about non primitive recursive functions. Also see her sequel Judy's turn to cry.  A much better song with a better message for teenagers is her You don't own me.)

CLYDE: Oh well. However, I'll make sure to tell that example to my class.


By gasarch

Complexity-theoretic foundations of BosonSampling with a linear number of modes

from arXiv: Computational Complexity

Authors: Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, Michal Oszmaniec

BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of photons to modes: all current hardness evidence assumes a "high-mode" regime in which the number of linear optical modes scales at least quadratically in the number of photons. By contrast, current experiments operate in a "low-mode" regime with a linear number of modes. In this paper we bridge this gap, bringing the hardness evidence for the low-mode experiments to the same level as had been previously established for the high-mode regime. This involves proving a new worst-to-average-case reduction for computing the Permanent that is robust to large numbers of row repetitions and also to distributions over matrices with correlated entries.

Authors: Adam Bouland, Daniel Brod, Ishaun Datta, Bill Fefferman, Daniel Grier, Felipe Hernandez, Michal Oszmaniec

BosonSampling is the leading candidate for demonstrating quantum computational advantage in photonic systems. While we have recently seen many impressive experimental demonstrations, there is still a formidable distance between the complexity-theoretic hardness arguments and current experiments. One of the largest gaps involves the ratio of photons to modes: all current hardness evidence assumes a "high-mode" regime in which the number of linear optical modes scales at least quadratically in the number of photons. By contrast, current experiments operate in a "low-mode" regime with a linear number of modes. In this paper we bridge this gap, bringing the hardness evidence for the low-mode experiments to the same level as had been previously established for the high-mode regime. This involves proving a new worst-to-average-case reduction for computing the Permanent that is robust to large numbers of row repetitions and also to distributions over matrices with correlated entries.

On the $\ell_0$ Isoperimetric Coefficient of Measurable Sets

from arXiv: Computational Geometry

Authors: Manuel Fernandez V

In this paper we prove that the $\ell_0$ isoperimetric coefficient for any axis-aligned cubes, $\psi_{\mathcal{C}}$, is $\Theta(n^{-1/2})$ and that the isoperimetric coefficient for any measurable body $K$, $\psi_K$, is of order $O(n^{-1/2})$. As a corollary we deduce that axis-aligned cubes essentially "maximize" the $\ell_0$ isoperimetric coefficient: There exists a positive constant $q > 0$ such that $\psi_K \leq q \cdot \psi_{\mathcal{C}}$, whenever $\mathcal{C}$ is an axis-aligned cube and $K$ is any measurable set. Lastly, we give immediate applications of our results to the mixing time of Coordinate-Hit-and-Run for sampling points uniformly from convex bodies.

Authors: Manuel Fernandez V

In this paper we prove that the $\ell_0$ isoperimetric coefficient for any axis-aligned cubes, $\psi_{\mathcal{C}}$, is $\Theta(n^{-1/2})$ and that the isoperimetric coefficient for any measurable body $K$, $\psi_K$, is of order $O(n^{-1/2})$. As a corollary we deduce that axis-aligned cubes essentially "maximize" the $\ell_0$ isoperimetric coefficient: There exists a positive constant $q > 0$ such that $\psi_K \leq q \cdot \psi_{\mathcal{C}}$, whenever $\mathcal{C}$ is an axis-aligned cube and $K$ is any measurable set. Lastly, we give immediate applications of our results to the mixing time of Coordinate-Hit-and-Run for sampling points uniformly from convex bodies.

A Threshold Greedy Algorithm for Noisy Submodular Maximization

from arXiv: Data Structures and Algorithms

Authors: Wenjing Chen, Shuo Xing, Victoria G. Crawford

We consider the optimization problem of cardinality constrained maximization of a monotone submodular set function $f:2^U\to\mathbb{R}_{\geq 0}$ (SM) with noisy evaluations of $f$. In particular, it is assumed that we do not have value oracle access to $f$, but instead for any $X\subseteq U$ and $u\in U$ we can take samples from a noisy distribution with expected value $f(X\cup\{u\})-f(X)$. Our goal is to develop algorithms in this setting that take as few samples as possible, and return a solution with an approximation guarantee relative to the optimal with high probability. We propose the algorithm Confident Threshold Greedy (CTG), which is based on the threshold greedy algorithm of Badanidiyuru and Vondrak [1] and samples adaptively in order to produce an approximate solution with high probability. We prove that CTG achieves an approximation ratio arbitrarily close to $1-1/e$, depending on input parameters. We provide an experimental evaluation on real instances of SM and demonstrate the sample efficiency of CTG.

Authors: Wenjing Chen, Shuo Xing, Victoria G. Crawford

We consider the optimization problem of cardinality constrained maximization of a monotone submodular set function $f:2^U\to\mathbb{R}_{\geq 0}$ (SM) with noisy evaluations of $f$. In particular, it is assumed that we do not have value oracle access to $f$, but instead for any $X\subseteq U$ and $u\in U$ we can take samples from a noisy distribution with expected value $f(X\cup\{u\})-f(X)$. Our goal is to develop algorithms in this setting that take as few samples as possible, and return a solution with an approximation guarantee relative to the optimal with high probability. We propose the algorithm Confident Threshold Greedy (CTG), which is based on the threshold greedy algorithm of Badanidiyuru and Vondrak [1] and samples adaptively in order to produce an approximate solution with high probability. We prove that CTG achieves an approximation ratio arbitrarily close to $1-1/e$, depending on input parameters. We provide an experimental evaluation on real instances of SM and demonstrate the sample efficiency of CTG.

Online Graph Coloring with Predictions

from arXiv: Data Structures and Algorithms

Authors: Antonios Antoniadis, Hajo Broersma, Yang Meng

We introduce learning augmented algorithms to the online graph coloring problem. Although the simple greedy algorithm FirstFit is known to perform poorly in the worst case, we are able to establish a relationship between the structure of any input graph $G$ that is revealed online and the number of colors that FirstFit uses for $G$. Based on this relationship, we propose an online coloring algorithm FirstFitPredictions that extends FirstFit while making use of machine learned predictions. We show that FirstFitPredictions is both \emph{consistent} and \emph{smooth}. Moreover, we develop a novel framework for combining online algorithms at runtime specifically for the online graph coloring problem. Finally, we show how this framework can be used to robustify by combining it with any classical online coloring algorithm (that disregards the predictions).

Authors: Antonios Antoniadis, Hajo Broersma, Yang Meng

We introduce learning augmented algorithms to the online graph coloring problem. Although the simple greedy algorithm FirstFit is known to perform poorly in the worst case, we are able to establish a relationship between the structure of any input graph $G$ that is revealed online and the number of colors that FirstFit uses for $G$. Based on this relationship, we propose an online coloring algorithm FirstFitPredictions that extends FirstFit while making use of machine learned predictions. We show that FirstFitPredictions is both \emph{consistent} and \emph{smooth}. Moreover, we develop a novel framework for combining online algorithms at runtime specifically for the online graph coloring problem. Finally, we show how this framework can be used to robustify by combining it with any classical online coloring algorithm (that disregards the predictions).

Sunday, December 03

TR23-193 | On the randomized complexity of range avoidance, with applications to cryptography and metacomplexity | Eldon Chung, Alexander Golovnev, Zeyong Li, Maciej Obremski, Sidhant Saraogi, Noah Stephens-Davidowitz

from ECCC Papers

We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in the question of whether there exist efficient randomized algorithms that output a valid solution to $\Avoid$ with probability significantly greater than $1/2$. (Notice that achieving probability $1/2$ is trivial by random guessing.) Our first main result shows that cryptographic one-way functions exist unless Avoid can be solved efficiently with probability $1-1/n^{C}$ (on efficiently sampleable input distributions). In other words, even a relatively weak notion of hardness of Avoid already implies the existence of all cryptographic primitives in Minicrypt. In fact, we show something a bit stronger than this. In particular, we introduce two new natural problems, which we call CollisionAvoid and AffineAvoid. Like Avoid, these are total search problems in the polynomial hierarchy. They are provably at least as hard as Avoid, and seem to be notably harder. We show that one-way functions exist if either of these problems is weakly hard on average. Our second main result shows that in certain settings Avoid can be solved with probability 1 in expected polynomial time, given access to either an oracle that approximates the Kolmogorov-Levin complexity of a bit string, or an oracle that approximates conditional time-bounded Kolmogorov complexity. This shows an interesting connection between Avoid and meta-complexity. Finally, we discuss the possibility of proving hardness of Avoid. We show barriers preventing simple reductions from hard problems in FNP to Avoid.
We study the Range Avoidance Problem (Avoid), in which the input is an expanding circuit $C : \{0,1\}^n \to \{0,1\}^{n+1}$, and the goal is to find a $y \in \{0,1\}^{n+1}$ that is not in the image of $C$. We are interested in the randomized complexity of this problem, i.e., in the question of whether there exist efficient randomized algorithms that output a valid solution to $\Avoid$ with probability significantly greater than $1/2$. (Notice that achieving probability $1/2$ is trivial by random guessing.) Our first main result shows that cryptographic one-way functions exist unless Avoid can be solved efficiently with probability $1-1/n^{C}$ (on efficiently sampleable input distributions). In other words, even a relatively weak notion of hardness of Avoid already implies the existence of all cryptographic primitives in Minicrypt. In fact, we show something a bit stronger than this. In particular, we introduce two new natural problems, which we call CollisionAvoid and AffineAvoid. Like Avoid, these are total search problems in the polynomial hierarchy. They are provably at least as hard as Avoid, and seem to be notably harder. We show that one-way functions exist if either of these problems is weakly hard on average. Our second main result shows that in certain settings Avoid can be solved with probability 1 in expected polynomial time, given access to either an oracle that approximates the Kolmogorov-Levin complexity of a bit string, or an oracle that approximates conditional time-bounded Kolmogorov complexity. This shows an interesting connection between Avoid and meta-complexity. Finally, we discuss the possibility of proving hardness of Avoid. We show barriers preventing simple reductions from hard problems in FNP to Avoid.

TR23-192 | A Note On the Universality of Black-box MKtP Solvers | Noam Mazor, Rafael Pass

from ECCC Papers

The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta-complexity problems relate to one another, and to the task of function inversion. In this note, we present resolutions to some of these questions with respect to the black-box analog of these problems. In more detail, let $MK^t_MP[s]$ denote the language consisting of strings $x$ with $K_{M}^t(x) < s(|x|)$, where $K_M^t(x)$ denotes the $t$-bounded Kolmogorov complexity of $x$ with $M$ as the underlying (Universal) Turing machine, and let $search-MK^t_MP[s]$ denote the search version of the same problem. We show that if there for every Universal Turing machine $U$ there exists a $2^{\alpha n}poly(n)$-size $U$-oracle aided circuit deciding $MK^t_UP [n-O(1)]$, then for every function $s$, and every---not necessarily universal---Turing machine $M$, there exists a $2^{\alpha s(n)}poly(n)$-size $M$-oracle aided circuit solving $search-MK^t_MP[s(n)]$; this in turn yields circuits of roughly the same size for both the Minimum Circuit Size Problem (MCSP), and the function inversion problem, as they can be thought of as instantiating $MK^t_MP$ with particular choices of (a non-universal) TMs $M$ (the circuit emulator for the case of MCSP, and the function evaluation in the case of function inversion). As a corollary of independent interest, we get that the complexity of black-box function inversion is (roughly) the same as the complexity of black-box deciding $MK^t_UP[n-O(1)]$ for any universal TM $U$; that is, also in the worst-case regime, function inversion is ``equivalent" to deciding $MK^t_UP$, in the black-box setting.
The relationships between various meta-complexity problems are not well understood in the worst-case regime, including whether the search version is harder than the decision version, whether the hardness scales with the ``threshold", and how the hardness of different meta-complexity problems relate to one another, and to the task of function inversion. In this note, we present resolutions to some of these questions with respect to the black-box analog of these problems. In more detail, let $MK^t_MP[s]$ denote the language consisting of strings $x$ with $K_{M}^t(x) < s(|x|)$, where $K_M^t(x)$ denotes the $t$-bounded Kolmogorov complexity of $x$ with $M$ as the underlying (Universal) Turing machine, and let $search-MK^t_MP[s]$ denote the search version of the same problem. We show that if there for every Universal Turing machine $U$ there exists a $2^{\alpha n}poly(n)$-size $U$-oracle aided circuit deciding $MK^t_UP [n-O(1)]$, then for every function $s$, and every---not necessarily universal---Turing machine $M$, there exists a $2^{\alpha s(n)}poly(n)$-size $M$-oracle aided circuit solving $search-MK^t_MP[s(n)]$; this in turn yields circuits of roughly the same size for both the Minimum Circuit Size Problem (MCSP), and the function inversion problem, as they can be thought of as instantiating $MK^t_MP$ with particular choices of (a non-universal) TMs $M$ (the circuit emulator for the case of MCSP, and the function evaluation in the case of function inversion). As a corollary of independent interest, we get that the complexity of black-box function inversion is (roughly) the same as the complexity of black-box deciding $MK^t_UP[n-O(1)]$ for any universal TM $U$; that is, also in the worst-case regime, function inversion is ``equivalent" to deciding $MK^t_UP$, in the black-box setting.

TR23-191 | On the Power of Homogeneous Algebraic Formulas | Nutan Limaye, Hervé Fournier, Srikanth Srinivasan, Sébastien Tavenas

from ECCC Papers

Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking this question: show that we can convert a general algebraic formula to a 'homogeneous' algebraic formula with moderate blow-up in size, and prove strong lower bounds against the latter model. Here, a homogeneous algebraic formula $F$ for a polynomial $P$ is a formula in which all subformulas compute homogeneous polynomials. In particular, if $P$ is homogeneous of degree $d$, $F$ does not contain subformulas that compute polynomials of degree greater than $d$. We investigate the feasibility of the above strategy and prove a number of positive and negative results in this direction. --- Lower bounds against weighted homogeneous formulas: We show the first lower bounds against homogeneous formulas 'of any depth' in the 'weighted' setting. Here, each variable has a given weight and the weight of a monomial is the sum of weights of the variables in it. This result builds on a lower bound of Hrubeš and Yehudayoff (Computational Complexity (2011)) against homogeneous multilinear formulas. This result is strong indication that lower bounds against homogeneous formulas is within reach. --- Improved (quasi-)homogenization for formulas: A simple folklore argument shows that any formula $F$ for a homogeneous polynomial of degree $d$ can be homogenized with a size blow-up of $d^{O(\log s)}.$ We show that this can be improved superpolynomially over fields of characteristic $0$ as long as $d = s^{o(1)}.$ Such a result was previously only known when $d = (\log s)^{1+o(1)}$ (Raz (J. ACM (2013))). Further, we show how to get rid of the condition on $d$ at the expense of getting a 'quasi-homogenization' result: this means that subformulas can compute polynomials of degree up to poly$(d).$ --- Lower bounds for non-commutative homogenization: A recent result of Dutta, Gesmundo, Ikenmeyer, Jindal and Lysikov (2022) implies that to homogenize algebraic formulas of any depth, it suffices to homogenize 'non-commutative' algebraic formulas of depth just $3$. We are able to show strong lower bounds against such homogenization, suggesting barriers for this approach. --- No Girard-Newton identities for positive characteristic: In characteristic $0$, it is known how to homogenize constant-depth algebraic formulas with a size blow-up of $\exp(O(\sqrt{d}))$ using the Girard-Newton identities. Finding analogues of these identities in positive characteristic would allow us, paradoxically, to show 'lower bounds' for constant-depth formulas over such fields. We rule out a strong generalization of Girard-Newton identities in the setting of positive characteristic, suggesting that a different approach is required.
Proving explicit lower bounds on the size of algebraic formulas is a long-standing open problem in the area of algebraic complexity theory. Recent results in the area (e.g. a lower bound against constant-depth algebraic formulas due to Limaye, Srinivasan, and Tavenas (FOCS 2021)) have indicated a way forward for attacking this question: show that we can convert a general algebraic formula to a 'homogeneous' algebraic formula with moderate blow-up in size, and prove strong lower bounds against the latter model. Here, a homogeneous algebraic formula $F$ for a polynomial $P$ is a formula in which all subformulas compute homogeneous polynomials. In particular, if $P$ is homogeneous of degree $d$, $F$ does not contain subformulas that compute polynomials of degree greater than $d$. We investigate the feasibility of the above strategy and prove a number of positive and negative results in this direction. --- Lower bounds against weighted homogeneous formulas: We show the first lower bounds against homogeneous formulas 'of any depth' in the 'weighted' setting. Here, each variable has a given weight and the weight of a monomial is the sum of weights of the variables in it. This result builds on a lower bound of Hrubeš and Yehudayoff (Computational Complexity (2011)) against homogeneous multilinear formulas. This result is strong indication that lower bounds against homogeneous formulas is within reach. --- Improved (quasi-)homogenization for formulas: A simple folklore argument shows that any formula $F$ for a homogeneous polynomial of degree $d$ can be homogenized with a size blow-up of $d^{O(\log s)}.$ We show that this can be improved superpolynomially over fields of characteristic $0$ as long as $d = s^{o(1)}.$ Such a result was previously only known when $d = (\log s)^{1+o(1)}$ (Raz (J. ACM (2013))). Further, we show how to get rid of the condition on $d$ at the expense of getting a 'quasi-homogenization' result: this means that subformulas can compute polynomials of degree up to poly$(d).$ --- Lower bounds for non-commutative homogenization: A recent result of Dutta, Gesmundo, Ikenmeyer, Jindal and Lysikov (2022) implies that to homogenize algebraic formulas of any depth, it suffices to homogenize 'non-commutative' algebraic formulas of depth just $3$. We are able to show strong lower bounds against such homogenization, suggesting barriers for this approach. --- No Girard-Newton identities for positive characteristic: In characteristic $0$, it is known how to homogenize constant-depth algebraic formulas with a size blow-up of $\exp(O(\sqrt{d}))$ using the Girard-Newton identities. Finding analogues of these identities in positive characteristic would allow us, paradoxically, to show 'lower bounds' for constant-depth formulas over such fields. We rule out a strong generalization of Girard-Newton identities in the setting of positive characteristic, suggesting that a different approach is required.

TR23-190 | From Trees to Polynomials and Back Again: New Capacity Bounds with Applications to TSP | Leonid Gurvits, Nathan Klein, Jonathan Leake

from ECCC Papers

We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of their approximation factor for metric TSP. Our results also allow for a more streamlined analysis of the algorithm. To achieve these new bounds, we build upon the work of Gurvits-Leake on the use of the productization technique for bounding the capacity of a real stable polynomial. This technique allows one to reduce certain inequalities for real stable polynomials to products of affine linear forms, which have an underlying matrix structure. In this paper, we push this technique further by characterizing the worst-case polynomials via bipartitioned forests. This rigid combinatorial structure yields a clean induction argument, which implies our stronger bounds. In general, we believe the results of this paper will lead to further improvement and simplification of the analysis of various combinatorial and probabilistic bounds and algorithms.
We give simply exponential lower bounds on the probabilities of a given strongly Rayleigh distribution, depending only on its expectation. This resolves a weak version of a problem left open by Karlin-Klein-Oveis Gharan in their recent breakthrough work on metric TSP, and this resolution leads to a minor improvement of their approximation factor for metric TSP. Our results also allow for a more streamlined analysis of the algorithm. To achieve these new bounds, we build upon the work of Gurvits-Leake on the use of the productization technique for bounding the capacity of a real stable polynomial. This technique allows one to reduce certain inequalities for real stable polynomials to products of affine linear forms, which have an underlying matrix structure. In this paper, we push this technique further by characterizing the worst-case polynomials via bipartitioned forests. This rigid combinatorial structure yields a clean induction argument, which implies our stronger bounds. In general, we believe the results of this paper will lead to further improvement and simplification of the analysis of various combinatorial and probabilistic bounds and algorithms.

Friday, December 01

Proofs of Equalities NP = coNP = PSPACE: Simplification

from arXiv: Computational Complexity

Authors: Lev Gordeev, Edward Hermann Haeusler

In this paper we present simplified proofs of our results NP = coNP = PSPACE.

Authors: Lev Gordeev, Edward Hermann Haeusler

In this paper we present simplified proofs of our results NP = coNP = PSPACE.

Lifting query complexity to time-space complexity for two-way finite automata

from arXiv: Computational Complexity

Authors: Shenggen Zheng, Yaqiao Li, Minghua Pan, Jozef Gruska, Lvzhou Li

Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique has been applied to study finite automata, it seems it has not been used to study time-space tradeoffs of finite automata. We design a new technique showing that separations of query complexity can be lifted, via communication complexity, to separations of time-space complexity of two-way finite automata. As an application, one of our main results exhibits the first example of a language $L$ such that the time-space complexity of two-way probabilistic finite automata with a bounded error (2PFA) is $\widetilde{\Omega}(n^2)$, while of exact two-way quantum finite automata with classical states (2QCFA) is $\widetilde{O}(n^{5/3})$, that is, we demonstrate for the first time that exact quantum computing has an advantage in time-space complexity comparing to classical computing.

Authors: Shenggen Zheng, Yaqiao Li, Minghua Pan, Jozef Gruska, Lvzhou Li

Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique has been applied to study finite automata, it seems it has not been used to study time-space tradeoffs of finite automata. We design a new technique showing that separations of query complexity can be lifted, via communication complexity, to separations of time-space complexity of two-way finite automata. As an application, one of our main results exhibits the first example of a language $L$ such that the time-space complexity of two-way probabilistic finite automata with a bounded error (2PFA) is $\widetilde{\Omega}(n^2)$, while of exact two-way quantum finite automata with classical states (2QCFA) is $\widetilde{O}(n^{5/3})$, that is, we demonstrate for the first time that exact quantum computing has an advantage in time-space complexity comparing to classical computing.

Matrix discrepancy and the log-rank conjecture

from arXiv: Computational Complexity

Authors: Benny Sudakov, István Tomon

Given an $m\times n$ binary matrix $M$ with $|M|=p\cdot mn$ (where $|M|$ denotes the number of 1 entries), define the discrepancy of $M$ as $\mbox{disc}(M)=\displaystyle\max_{X\subset [m], Y\subset [n]}\big||M[X\times Y]|-p|X|\cdot |Y|\big|$. Using semidefinite programming and spectral techniques, we prove that if $\mbox{rank}(M)\leq r$ and $p\leq 1/2$, then

$$\mbox{disc}(M)\geq \Omega(mn)\cdot \min\left\{p,\frac{p^{1/2}}{\sqrt{r}}\right\}.$$

We use this result to obtain a modest improvement of Lovett's best known upper bound on the log-rank conjecture. We prove that any $m\times n$ binary matrix $M$ of rank at most $r$ contains an $(m\cdot 2^{-O(\sqrt{r})})\times (n\cdot 2^{-O(\sqrt{r})})$ sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank $r$ is at most $O(\sqrt{r})$.

Authors: Benny Sudakov, István Tomon

Given an $m\times n$ binary matrix $M$ with $|M|=p\cdot mn$ (where $|M|$ denotes the number of 1 entries), define the discrepancy of $M$ as $\mbox{disc}(M)=\displaystyle\max_{X\subset [m], Y\subset [n]}\big||M[X\times Y]|-p|X|\cdot |Y|\big|$. Using semidefinite programming and spectral techniques, we prove that if $\mbox{rank}(M)\leq r$ and $p\leq 1/2$, then

$$\mbox{disc}(M)\geq \Omega(mn)\cdot \min\left\{p,\frac{p^{1/2}}{\sqrt{r}}\right\}.$$

We use this result to obtain a modest improvement of Lovett's best known upper bound on the log-rank conjecture. We prove that any $m\times n$ binary matrix $M$ of rank at most $r$ contains an $(m\cdot 2^{-O(\sqrt{r})})\times (n\cdot 2^{-O(\sqrt{r})})$ sized all-1 or all-0 submatrix, which implies that the deterministic communication complexity of any Boolean function of rank $r$ is at most $O(\sqrt{r})$.

Fully Dynamic Algorithms for Euclidean Steiner Tree

from arXiv: Computational Geometry

Authors: T-H. Hubert Chan, Gramoz Goranci, Shaofeng H.-C. Jiang, Bo Wang, Quan Xue

The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of \emph{terminal} points $X$ in $\mathbb{R}^d$, possibly using points not in $X$ which are called Steiner points. Even though near-linear time $(1 + \epsilon)$-approximation was obtained in the offline setting in seminal works of Arora and Mitchell, efficient dynamic algorithms for Steiner tree is still open. We give the first algorithm that (implicitly) maintains a $(1 + \epsilon)$-approximate solution which is accessed via a set of tree traversal queries, subject to point insertion and deletions, with amortized update and query time $O(\poly\log n)$ with high probability. Our approach is based on an Arora-style geometric dynamic programming, and our main technical contribution is to maintain the DP subproblems in the dynamic setting efficiently. We also need to augment the DP subproblems to support the tree traversal queries.

Authors: T-H. Hubert Chan, Gramoz Goranci, Shaofeng H.-C. Jiang, Bo Wang, Quan Xue

The Euclidean Steiner tree problem asks to find a min-cost metric graph that connects a given set of \emph{terminal} points $X$ in $\mathbb{R}^d$, possibly using points not in $X$ which are called Steiner points. Even though near-linear time $(1 + \epsilon)$-approximation was obtained in the offline setting in seminal works of Arora and Mitchell, efficient dynamic algorithms for Steiner tree is still open. We give the first algorithm that (implicitly) maintains a $(1 + \epsilon)$-approximate solution which is accessed via a set of tree traversal queries, subject to point insertion and deletions, with amortized update and query time $O(\poly\log n)$ with high probability. Our approach is based on an Arora-style geometric dynamic programming, and our main technical contribution is to maintain the DP subproblems in the dynamic setting efficiently. We also need to augment the DP subproblems to support the tree traversal queries.

Sparsifying generalized linear models

from arXiv: Data Structures and Algorithms

Authors: Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford

We consider the sparsification of sums $F : \mathbb{R}^n \to \mathbb{R}$ where $F(x) = f_1(\langle a_1,x\rangle) + \cdots + f_m(\langle a_m,x\rangle)$ for vectors $a_1,\ldots,a_m \in \mathbb{R}^n$ and functions $f_1,\ldots,f_m : \mathbb{R} \to \mathbb{R}_+$. We show that $(1+\varepsilon)$-approximate sparsifiers of $F$ with support size $\frac{n}{\varepsilon^2} (\log \frac{n}{\varepsilon})^{O(1)}$ exist whenever the functions $f_1,\ldots,f_m$ are symmetric, monotone, and satisfy natural growth bounds. Additionally, we give efficient algorithms to compute such a sparsifier assuming each $f_i$ can be evaluated efficiently.

Our results generalize the classic case of $\ell_p$ sparsification, where $f_i(z) = |z|^p$, for $p \in (0, 2]$, and give the first near-linear size sparsifiers in the well-studied setting of the Huber loss function and its generalizations, e.g., $f_i(z) = \min\{|z|^p, |z|^2\}$ for $0 < p \leq 2$. Our sparsification algorithm can be applied to give near-optimal reductions for optimizing a variety of generalized linear models including $\ell_p$ regression for $p \in (1, 2]$ to high accuracy, via solving $(\log n)^{O(1)}$ sparse regression instances with $m \le n(\log n)^{O(1)}$, plus runtime proportional to the number of nonzero entries in the vectors $a_1, \dots, a_m$.

Authors: Arun Jambulapati, James R. Lee, Yang P. Liu, Aaron Sidford

We consider the sparsification of sums $F : \mathbb{R}^n \to \mathbb{R}$ where $F(x) = f_1(\langle a_1,x\rangle) + \cdots + f_m(\langle a_m,x\rangle)$ for vectors $a_1,\ldots,a_m \in \mathbb{R}^n$ and functions $f_1,\ldots,f_m : \mathbb{R} \to \mathbb{R}_+$. We show that $(1+\varepsilon)$-approximate sparsifiers of $F$ with support size $\frac{n}{\varepsilon^2} (\log \frac{n}{\varepsilon})^{O(1)}$ exist whenever the functions $f_1,\ldots,f_m$ are symmetric, monotone, and satisfy natural growth bounds. Additionally, we give efficient algorithms to compute such a sparsifier assuming each $f_i$ can be evaluated efficiently.

Our results generalize the classic case of $\ell_p$ sparsification, where $f_i(z) = |z|^p$, for $p \in (0, 2]$, and give the first near-linear size sparsifiers in the well-studied setting of the Huber loss function and its generalizations, e.g., $f_i(z) = \min\{|z|^p, |z|^2\}$ for $0 < p \leq 2$. Our sparsification algorithm can be applied to give near-optimal reductions for optimizing a variety of generalized linear models including $\ell_p$ regression for $p \in (1, 2]$ to high accuracy, via solving $(\log n)^{O(1)}$ sparse regression instances with $m \le n(\log n)^{O(1)}$, plus runtime proportional to the number of nonzero entries in the vectors $a_1, \dots, a_m$.

Almost-Linear Time Algorithms for Incremental Graphs: Cycle Detection, SCCs, $s$-$t$ Shortest Path, and Minimum-Cost Flow

from arXiv: Data Structures and Algorithms

Authors: Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, $s$-$t$ shortest path, maximum flow, and minimum-cost flow. To solve these problems, we give a deterministic data structure that returns a $m^{o(1)}$-approximate minimum-ratio cycle in fully dynamic graphs in amortized $m^{o(1)}$ time per update. Combining this with the interior point method framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time algorithm for deciding the first update in an incremental graph after which the cost of the minimum-cost flow attains value at most some given threshold $F$. By rather direct reductions to minimum-cost flow, we are then able to solve the problems in incremental graphs mentioned above.

At a high level, our algorithm dynamizes the $\ell_1$ oblivious routing of Rozho\v{n}-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method to extract an approximate minimum ratio cycle from the structure of the oblivious routing. To maintain the oblivious routing, we use tools from concurrent work of Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers for shortest paths, in order to maintain a sparse neighborhood cover in fully dynamic graphs.

To find a cycle, we first show that an approximate minimum ratio cycle can be represented as a fundamental cycle on a small set of trees resulting from the oblivious routing. Then, we find a cycle whose quality is comparable to the best tree cycle. This final cycle query step involves vertex and edge sparsification procedures reminiscent of previous works, but crucially requires a more powerful dynamic spanner which can handle far more edge insertions. We build such a spanner via a construction that hearkens back to the classic greedy spanner algorithm.

Authors: Li Chen, Rasmus Kyng, Yang P. Liu, Simon Meierhans, Maximilian Probst Gutenberg

We give the first almost-linear time algorithms for several problems in incremental graphs including cycle detection, strongly connected component maintenance, $s$-$t$ shortest path, maximum flow, and minimum-cost flow. To solve these problems, we give a deterministic data structure that returns a $m^{o(1)}$-approximate minimum-ratio cycle in fully dynamic graphs in amortized $m^{o(1)}$ time per update. Combining this with the interior point method framework of Brand-Liu-Sidford (STOC 2023) gives the first almost-linear time algorithm for deciding the first update in an incremental graph after which the cost of the minimum-cost flow attains value at most some given threshold $F$. By rather direct reductions to minimum-cost flow, we are then able to solve the problems in incremental graphs mentioned above.

At a high level, our algorithm dynamizes the $\ell_1$ oblivious routing of Rozho\v{n}-Grunau-Haeupler-Zuzic-Li (STOC 2022), and develops a method to extract an approximate minimum ratio cycle from the structure of the oblivious routing. To maintain the oblivious routing, we use tools from concurrent work of Kyng-Meierhans-Probst Gutenberg which designed vertex sparsifiers for shortest paths, in order to maintain a sparse neighborhood cover in fully dynamic graphs.

To find a cycle, we first show that an approximate minimum ratio cycle can be represented as a fundamental cycle on a small set of trees resulting from the oblivious routing. Then, we find a cycle whose quality is comparable to the best tree cycle. This final cycle query step involves vertex and edge sparsification procedures reminiscent of previous works, but crucially requires a more powerful dynamic spanner which can handle far more edge insertions. We build such a spanner via a construction that hearkens back to the classic greedy spanner algorithm.

Thursday, November 30

Linkage

from David Eppstein

Lance Fortnow notices fewer faculty job ads in this year’s November CRA News and asks: “is there a real drop in hiring, or something else?”

By David Eppstein

Visiting Lecturer/Senior Lecturer/Assistant Professor for “Interactive Narrative” course at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Responsibilities: Design the syllabus and teach to develop storylines and characters, character profiles, bios, and sketches, scripts of in-game dialogues, storyboards; Design grading metrics. Qualifications: Technical or humanitarian background; Excellent command of Game Design and Gamification processes; Experience of teaching young adults. Website: career.innopolis.university/en/job/ Email: faculty@innopolis.ru

Responsibilities:

Design the syllabus and teach to develop storylines and characters, character profiles, bios, and sketches, scripts of in-game dialogues, storyboards; Design grading metrics.

Qualifications:

Technical or humanitarian background;
Excellent command of Game Design and Gamification processes;
Experience of teaching young adults.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Visiting Lecturer / Assistant Professor for “Game Design and Gamification” course at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Responsibilities: Design the syllabus and teach Game Design Methodologies, Gamification Processes, and Player Experiences; Teach such as project-based learning, active discussions, role play, cases, etc.; Design grading metrics. Qualifications: Technical or humanitarian background; Excellent command of Game Design and Gamification processes; Experience of teaching young adults. Website: career.innopolis.university/en/job/ Email: faculty@innopolis.ru

Responsibilities:

Design the syllabus and teach Game Design Methodologies, Gamification Processes, and Player Experiences;
Teach such as project-based learning, active discussions, role play, cases, etc.; Design grading metrics.

Qualifications:

Technical or humanitarian background;
Excellent command of Game Design and Gamification processes;
Experience of teaching young adults.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Lecturer/Assistant Professor in Computer Science/ Games Specialty at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Qualifications: Ph.D. degree and published research in Computer Science . Focus on AI, GameDev and Data Science. Responsibilities: Frontal teaching the courses: Game History, Unity Game Development, Interactive Narrative, and Business of Games, etc. during the academic year; lead research activities, advise and mentor students. Website: career.innopolis.university/en/job/ Email: faculty@innopolis.ru

Qualifications:

Ph.D. degree and published research in Computer Science .
Focus on AI, GameDev and Data Science.

Responsibilities:

Frontal teaching the courses: Game History, Unity Game Development, Interactive Narrative, and Business of Games, etc. during the academic year; lead research activities, advise and mentor students.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Full Professor in Robotics & Computer Vision at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Qualifications: PhD degree practical experience in Sensor Fusion, SLAM, Perception, ML, RL, DL strong record of published papers in CV for robotic application experience as PI in projects Responsibilities: Up to 120 hours of frontal teaching in 4 courses per year, leading research, advising and mentoring students, other activities for developing the intellectual environment. Website: […]

Qualifications:

PhD degree
practical experience in Sensor Fusion, SLAM, Perception, ML, RL, DL strong record of published papers in CV for robotic application experience as PI in projects

Responsibilities:

Up to 120 hours of frontal teaching in 4 courses per year, leading research, advising and mentoring students, other activities for developing the intellectual environment.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Associate Professor in Data Science & AI at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Qualifications: PhD degree 2+ years of Assistant Professorship record of published papers in A* conferences Responsibilities: Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University. Website: career.innopolis.university/en/job/ Email: […]

Qualifications:
PhD degree
2+ years of Assistant Professorship
record of published papers in A* conferences

Responsibilities:
Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Associate/Full Professor in Software Engineering at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Qualifications: PhD degree and published research in software quality, software architecture experience of leading software development teams industry experience Responsibilities: Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities for developing and maintaining the intellectual environment. Website: career.innopolis.university/en/job/ Email: faculty@innopolis.ru

Qualifications:
PhD degree and published research in software quality, software architecture experience of leading software development teams
industry experience

Responsibilities:
Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities for developing and maintaining the intellectual environment.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Assistant Professor in Software Development and Engineering at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Qualifications: PhD degree and published research in programming languages, compilers, databases, OS industry experience Responsibilities: Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University. Website: career.innopolis.university/en/job/ Email: faculty@innopolis.ru

Qualifications:

PhD degree and published research in programming languages, compilers, databases, OS

industry experience

Responsibilities:
Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Assistant Professor in Robotics & Computer Vision at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Qualifications: PhD degree TAship experience experience in Machine Learning strong record of published papers Responsibilities: Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University. Website: career.innopolis.university/en/job/ Email: faculty@innopolis.ru

Qualifications:

PhD degree

TAship experience

experience in Machine Learning

strong record of published papers

Responsibilities:

Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Assistant Professor in Data Science & AI at Innopolis University (apply by January 30, 2024)

from CCI: jobs

Qualifications: PhD degree depth of expertise experience of being a TA strong record of published papers Responsibilities: Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University. Website: career.innopolis.university/en/job/ […]

Qualifications:

PhD degree

depth of expertise

experience of being a TA

strong record of published papers

Responsibilities:

Up to 120 academic hours of frontal teaching in 4 courses per year, leading high quality research, advising and mentoring students, other activities related to developing and maintaining the intellectual and cultural environment of the University.

Website: https://career.innopolis.university/en/job/
Email: faculty@innopolis.ru

By shacharlovett

Faculty positions in quantum computing and quantum algorithms at EPFL (apply by December 15, 2023)

from CCI: jobs

EPFL invite applications for a faculty position in all areas of quantum computing and quantum algorithms. Screening starts at December 15 but later applicants will also be considered. Reach out to Ola Svensson with any questions about the search, position, and school! Website: go.epfl.ch/qc-jobs Email: ola.svensson@epfl.ch

EPFL invite applications for a faculty position in all areas of quantum computing and quantum algorithms.

Screening starts at December 15 but later applicants will also be considered. Reach out to Ola Svensson with any questions about the search, position, and school!

Website: http://go.epfl.ch/qc-jobs
Email: ola.svensson@epfl.ch

By shacharlovett

On the Complexity of the Median and Closest Permutation Problems

from arXiv: Computational Complexity

Authors: Luís Cunha, Ignasi Sau, Uéverton Souza

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. Finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations, some distance metrics have been extensively studied. We investigate median and closest problems on permutations over the metrics: breakpoint, swap, block-interchange, short-block-move, and transposition. In biological matters some values are usually small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation for some metrics, even for k = 3; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics parameterized by the target distance d.

Authors: Luís Cunha, Ignasi Sau, Uéverton Souza

Genome rearrangements are events where large blocks of DNA exchange places during evolution. The analysis of these events is a promising tool for understanding evolutionary genomics, providing data for phylogenetic reconstruction based on genome rearrangement measures. Many pairwise rearrangement distances have been proposed, based on finding the minimum number of rearrangement events to transform one genome into the other, using some predefined operation. When more than two genomes are considered, we have the more challenging problem of rearrangement-based phylogeny reconstruction. Given a set of genomes and a distance notion, there are at least two natural ways to define the "target" genome. On the one hand, finding a genome that minimizes the sum of the distances from this to any other, called the median genome. Finding a genome that minimizes the maximum distance to any other, called the closest genome. Considering genomes as permutations, some distance metrics have been extensively studied. We investigate median and closest problems on permutations over the metrics: breakpoint, swap, block-interchange, short-block-move, and transposition. In biological matters some values are usually small, such as the solution value d or the number k of input permutations. For each of these metrics and parameters d or k, we analyze the closest and the median problems from the viewpoint of parameterized complexity. We obtain the following results: NP-hardness for finding the median/closest permutation for some metrics, even for k = 3; Polynomial kernels for the problems of finding the median permutation of all studied metrics, considering the target distance d as parameter; NP-hardness result for finding the closest permutation by short-block-moves; FPT algorithms and infeasibility of polynomial kernels for finding the closest permutation for some metrics parameterized by the target distance d.

A Local Approach to Studying the Time and Space Complexity of Deterministic and Nondeterministic Decision Trees

from arXiv: Computational Complexity

Authors: Kerven Durdymyradov, Mikhail Moshkov

In this paper, we study arbitrary infinite binary information systems each of which consists of an infinite set called universe and an infinite set of two-valued functions (attributes) defined on the universe. We consider the notion of a problem over information system, which is described by a finite number of attributes and a mapping associating a decision to each tuple of attribute values. As algorithms for problem solving, we investigate deterministic and nondeterministic decision trees that use only attributes from the problem description. Nondeterministic decision trees are representations of decision rule systems that sometimes have less space complexity than the original rule systems. As time and space complexity, we study the depth and the number of nodes in the decision trees. In the worst case, with the growth of the number of attributes in the problem description, (i) the minimum depth of deterministic decision trees grows either as a logarithm or linearly, (ii) the minimum depth of nondeterministic decision trees either is bounded from above by a constant or grows linearly, (iii) the minimum number of nodes in deterministic decision trees has either polynomial or exponential growth, and (iv) the minimum number of nodes in nondeterministic decision trees has either polynomial or exponential growth. Based on these results, we divide the set of all infinite binary information systems into three complexity classes. This allows us to identify nontrivial relationships between deterministic decision trees and decision rules systems represented by nondeterministic decision trees. For each class, we study issues related to time-space trade-off for deterministic and nondeterministic decision trees.

Authors: Kerven Durdymyradov, Mikhail Moshkov

In this paper, we study arbitrary infinite binary information systems each of which consists of an infinite set called universe and an infinite set of two-valued functions (attributes) defined on the universe. We consider the notion of a problem over information system, which is described by a finite number of attributes and a mapping associating a decision to each tuple of attribute values. As algorithms for problem solving, we investigate deterministic and nondeterministic decision trees that use only attributes from the problem description. Nondeterministic decision trees are representations of decision rule systems that sometimes have less space complexity than the original rule systems. As time and space complexity, we study the depth and the number of nodes in the decision trees. In the worst case, with the growth of the number of attributes in the problem description, (i) the minimum depth of deterministic decision trees grows either as a logarithm or linearly, (ii) the minimum depth of nondeterministic decision trees either is bounded from above by a constant or grows linearly, (iii) the minimum number of nodes in deterministic decision trees has either polynomial or exponential growth, and (iv) the minimum number of nodes in nondeterministic decision trees has either polynomial or exponential growth. Based on these results, we divide the set of all infinite binary information systems into three complexity classes. This allows us to identify nontrivial relationships between deterministic decision trees and decision rules systems represented by nondeterministic decision trees. For each class, we study issues related to time-space trade-off for deterministic and nondeterministic decision trees.

Violating Constant Degree Hypothesis Requires Breaking Symmetry

from arXiv: Computational Complexity

Authors: Piotr Kawałek, Armin Weiß

The Constant Degree Hypothesis was introduced by Barrington et. al. (1990) to study some extensions of $q$-groups by nilpotent groups and the power of these groups in a certain computational model. In its simplest formulation, it establishes exponential lower bounds for $\mathrm{AND}_d \circ \mathrm{MOD}_m \circ \mathrm{MOD}_q$ circuits computing AND of unbounded arity $n$ (for constant integers $d,m$ and a prime $q$). While it has been proved in some special cases (including $d=1$), it remains wide open in its general form for over 30 years.

In this paper we prove that the hypothesis holds when we restrict our attention to symmetric circuits with $m$ being a prime. While we build upon techniques by Grolmusz and Tardos (2000), we have to prove a new symmetric version of their Degree Decreasing Lemma and apply it in a highly non-trivial way. Moreover, to establish the result we perform a careful analysis of automorphism groups of $\mathrm{AND} \circ \mathrm{MOD}_m$ subcircuits and study the periodic behaviour of the computed functions.

Finally, our methods also yield lower bounds when $d$ is treated as a function of $n$.

Authors: Piotr Kawałek, Armin Weiß

The Constant Degree Hypothesis was introduced by Barrington et. al. (1990) to study some extensions of $q$-groups by nilpotent groups and the power of these groups in a certain computational model. In its simplest formulation, it establishes exponential lower bounds for $\mathrm{AND}_d \circ \mathrm{MOD}_m \circ \mathrm{MOD}_q$ circuits computing AND of unbounded arity $n$ (for constant integers $d,m$ and a prime $q$). While it has been proved in some special cases (including $d=1$), it remains wide open in its general form for over 30 years.

In this paper we prove that the hypothesis holds when we restrict our attention to symmetric circuits with $m$ being a prime. While we build upon techniques by Grolmusz and Tardos (2000), we have to prove a new symmetric version of their Degree Decreasing Lemma and apply it in a highly non-trivial way. Moreover, to establish the result we perform a careful analysis of automorphism groups of $\mathrm{AND} \circ \mathrm{MOD}_m$ subcircuits and study the periodic behaviour of the computed functions.

Finally, our methods also yield lower bounds when $d$ is treated as a function of $n$.

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes

from arXiv: Computational Complexity

Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to our knowledge, the first known family of codes that can be decoded in nearly linear time, even as they approach the list decoding capacity. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list-decoding. It is known that for every $\epsilon >0$, and rate $R \in (0,1)$, there exist explicit families of these codes that have rate $R$ and can be list-decoded from a $(1-R-\epsilon)$ fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory, 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above tasks in nearly linear time. Our algorithms have two main components. The first builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a nearly linear time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design nearly-linear time algorithms for two natural algebraic problems. The first algorithm solves linear differential equations of the form $Q\left(x, f(x), \frac{df}{dx}, \dots,\frac{d^m f}{dx^m}\right) \equiv 0$ where $Q$ has the form $Q(x,y_0,\dots,y_m) = \tilde{Q}(x) + \sum_{i = 0}^m Q_i(x)\cdot y_i$. The second solves functional equations of the form $Q\left(x, f(x), f(\gamma x), \dots,f(\gamma^m x)\right) \equiv 0$ where $\gamma$ is a high-order field element. These algorithms can be viewed as generalizations of classical algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.

Authors: Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to our knowledge, the first known family of codes that can be decoded in nearly linear time, even as they approach the list decoding capacity. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list-decoding. It is known that for every $\epsilon >0$, and rate $R \in (0,1)$, there exist explicit families of these codes that have rate $R$ and can be list-decoded from a $(1-R-\epsilon)$ fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory, 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above tasks in nearly linear time. Our algorithms have two main components. The first builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a nearly linear time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design nearly-linear time algorithms for two natural algebraic problems. The first algorithm solves linear differential equations of the form $Q\left(x, f(x), \frac{df}{dx}, \dots,\frac{d^m f}{dx^m}\right) \equiv 0$ where $Q$ has the form $Q(x,y_0,\dots,y_m) = \tilde{Q}(x) + \sum_{i = 0}^m Q_i(x)\cdot y_i$. The second solves functional equations of the form $Q\left(x, f(x), f(\gamma x), \dots,f(\gamma^m x)\right) \equiv 0$ where $\gamma$ is a high-order field element. These algorithms can be viewed as generalizations of classical algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.

Exceptional Mechanical Performance by Spatial Printing with Continuous Fiber

from arXiv: Computational Geometry

Authors: Guoxin Fang, Tianyu Zhang, Yuming Huang, Zhizhou Zhang, Kunal Masania, Charlie C.L. Wang

This work explores a spatial printing method to fabricate continuous fiber-reinforced thermoplastic composites (CFRTPCs), which can achieve exceptional mechanical performance. For models giving complex 3D stress distribution under loads, typical planar-layer based fiber placement usually fails to provide sufficient reinforcement due to their orientations being constrained to planes. The effectiveness of fiber reinforcement could be maximized by using multi-axis additive manufacturing (MAAM) to better control the orientation of continuous fibers in 3D-printed composites. Here, we propose a computational approach to generate 3D toolpaths that satisfy two major reinforcement objectives: 1) following the maximal stress directions in critical regions and 2) connecting multiple load-bearing regions by continuous fibers. Principal stress lines are first extracted in an input solid model to identify critical regions. Curved layers aligned with maximal stresses in these critical regions are generated by computing an optimized scalar field and extracting its iso-surfaces. Then, topological analysis and operations are applied to each curved layer to generate a computational domain that preserves fiber continuity between load-bearing regions. Lastly, continuous fiber toolpaths aligned with maximal stresses are generated on each surface layer by computing an optimized scalar field and extracting its iso-curves. A hardware system with dual robotic arms is employed to conduct the physical MAAM tasks depositing polymer or fiber reinforced polymer composite materials by applying a force normal to the extrusion plane to aid consolidation. When comparing to planar-layer based printing results in tension, up to 644% breaking forces and 240% stiffness are observed on shapes fabricated by our spatial printing method.

Authors: Guoxin Fang, Tianyu Zhang, Yuming Huang, Zhizhou Zhang, Kunal Masania, Charlie C.L. Wang

This work explores a spatial printing method to fabricate continuous fiber-reinforced thermoplastic composites (CFRTPCs), which can achieve exceptional mechanical performance. For models giving complex 3D stress distribution under loads, typical planar-layer based fiber placement usually fails to provide sufficient reinforcement due to their orientations being constrained to planes. The effectiveness of fiber reinforcement could be maximized by using multi-axis additive manufacturing (MAAM) to better control the orientation of continuous fibers in 3D-printed composites. Here, we propose a computational approach to generate 3D toolpaths that satisfy two major reinforcement objectives: 1) following the maximal stress directions in critical regions and 2) connecting multiple load-bearing regions by continuous fibers. Principal stress lines are first extracted in an input solid model to identify critical regions. Curved layers aligned with maximal stresses in these critical regions are generated by computing an optimized scalar field and extracting its iso-surfaces. Then, topological analysis and operations are applied to each curved layer to generate a computational domain that preserves fiber continuity between load-bearing regions. Lastly, continuous fiber toolpaths aligned with maximal stresses are generated on each surface layer by computing an optimized scalar field and extracting its iso-curves. A hardware system with dual robotic arms is employed to conduct the physical MAAM tasks depositing polymer or fiber reinforced polymer composite materials by applying a force normal to the extrusion plane to aid consolidation. When comparing to planar-layer based printing results in tension, up to 644% breaking forces and 240% stiffness are observed on shapes fabricated by our spatial printing method.

Constructing Optimal $L_{\infty}$ Star Discrepancy Sets

from arXiv: Computational Geometry

Authors: François Clément, Carola Doerr, Kathrin Klamroth, Luís Paquete

The $L_{\infty}$ star discrepancy is a very well-studied measure used to quantify the uniformity of a point set distribution. Constructing optimal point sets for this measure is seen as a very hard problem in the discrepancy community. Indeed, optimal point sets are, up to now, known only for $n\leq 6$ in dimension 2 and $n \leq 2$ for higher dimensions. We introduce in this paper mathematical programming formulations to construct point sets with as low $L_{\infty}$ star discrepancy as possible. Firstly, we present two models to construct optimal sets and show that there always exist optimal sets with the property that no two points share a coordinate. Then, we provide possible extensions of our models to other measures, such as the extreme and periodic discrepancies. For the $L_{\infty}$ star discrepancy, we are able to compute optimal point sets for up to 21 points in dimension 2 and for up to 8 points in dimension 3. For $d=2$ and $n\ge 7$ points, these point sets have around a 50% lower discrepancy than the current best point sets, and show a very different structure.

Authors: François Clément, Carola Doerr, Kathrin Klamroth, Luís Paquete

The $L_{\infty}$ star discrepancy is a very well-studied measure used to quantify the uniformity of a point set distribution. Constructing optimal point sets for this measure is seen as a very hard problem in the discrepancy community. Indeed, optimal point sets are, up to now, known only for $n\leq 6$ in dimension 2 and $n \leq 2$ for higher dimensions. We introduce in this paper mathematical programming formulations to construct point sets with as low $L_{\infty}$ star discrepancy as possible. Firstly, we present two models to construct optimal sets and show that there always exist optimal sets with the property that no two points share a coordinate. Then, we provide possible extensions of our models to other measures, such as the extreme and periodic discrepancies. For the $L_{\infty}$ star discrepancy, we are able to compute optimal point sets for up to 21 points in dimension 2 and for up to 8 points in dimension 3. For $d=2$ and $n\ge 7$ points, these point sets have around a 50% lower discrepancy than the current best point sets, and show a very different structure.

Improving embedding of graphs with missing data by soft manifolds

from arXiv: Computational Geometry

Authors: Andrea Marinoni, Pietro Lio', Alessandro Barp, Christian Jutten, Mark Girolami

Embedding graphs in continous spaces is a key factor in designing and developing algorithms for automatic information extraction to be applied in diverse tasks (e.g., learning, inferring, predicting). The reliability of graph embeddings directly depends on how much the geometry of the continuous space matches the graph structure. Manifolds are mathematical structure that can enable to incorporate in their topological spaces the graph characteristics, and in particular nodes distances. State-of-the-art of manifold-based graph embedding algorithms take advantage of the assumption that the projection on a tangential space of each point in the manifold (corresponding to a node in the graph) would locally resemble a Euclidean space. Although this condition helps in achieving efficient analytical solutions to the embedding problem, it does not represent an adequate set-up to work with modern real life graphs, that are characterized by weighted connections across nodes often computed over sparse datasets with missing records. In this work, we introduce a new class of manifold, named soft manifold, that can solve this situation. In particular, soft manifolds are mathematical structures with spherical symmetry where the tangent spaces to each point are hypocycloids whose shape is defined according to the velocity of information propagation across the data points. Using soft manifolds for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets. Experimental results on reconstruction tasks on synthetic and real datasets show how the proposed approach enable more accurate and reliable characterization of graphs in continuous spaces with respect to the state-of-the-art.

Authors: Andrea Marinoni, Pietro Lio', Alessandro Barp, Christian Jutten, Mark Girolami

Embedding graphs in continous spaces is a key factor in designing and developing algorithms for automatic information extraction to be applied in diverse tasks (e.g., learning, inferring, predicting). The reliability of graph embeddings directly depends on how much the geometry of the continuous space matches the graph structure. Manifolds are mathematical structure that can enable to incorporate in their topological spaces the graph characteristics, and in particular nodes distances. State-of-the-art of manifold-based graph embedding algorithms take advantage of the assumption that the projection on a tangential space of each point in the manifold (corresponding to a node in the graph) would locally resemble a Euclidean space. Although this condition helps in achieving efficient analytical solutions to the embedding problem, it does not represent an adequate set-up to work with modern real life graphs, that are characterized by weighted connections across nodes often computed over sparse datasets with missing records. In this work, we introduce a new class of manifold, named soft manifold, that can solve this situation. In particular, soft manifolds are mathematical structures with spherical symmetry where the tangent spaces to each point are hypocycloids whose shape is defined according to the velocity of information propagation across the data points. Using soft manifolds for graph embedding, we can provide continuous spaces to pursue any task in data analysis over complex datasets. Experimental results on reconstruction tasks on synthetic and real datasets show how the proposed approach enable more accurate and reliable characterization of graphs in continuous spaces with respect to the state-of-the-art.

An Efficient Algorithm for Unbalanced 1D Transportation

from arXiv: Data Structures and Algorithms

Authors: Gabriel Gouvine

Optimal transport (OT) and unbalanced optimal transport (UOT) are central in many machine learning, statistics and engineering applications. 1D OT is easily solved, with complexity O(n log n), but no efficient algorithm was known for 1D UOT. We present a new approach that leverages the successive shortest path algorithm for the corresponding network flow problem. By employing a suitable representation, we bundle together multiple steps that do not change the cost of the shortest path. We prove that our algorithm solves 1D UOT in O(n log n), closing the gap.

Authors: Gabriel Gouvine

Optimal transport (OT) and unbalanced optimal transport (UOT) are central in many machine learning, statistics and engineering applications. 1D OT is easily solved, with complexity O(n log n), but no efficient algorithm was known for 1D UOT. We present a new approach that leverages the successive shortest path algorithm for the corresponding network flow problem. By employing a suitable representation, we bundle together multiple steps that do not change the cost of the shortest path. We prove that our algorithm solves 1D UOT in O(n log n), closing the gap.

Lower Bounds on Adaptive Sensing for Matrix Recovery

from arXiv: Data Structures and Algorithms

Authors: Praneeth Kacham, David P Woodruff

We study lower bounds on adaptive sensing algorithms for recovering low rank matrices using linear measurements. Given an $n \times n$ matrix $A$, a general linear measurement $S(A)$, for an $n \times n$ matrix $S$, is just the inner product of $S$ and $A$, each treated as $n^2$-dimensional vectors. By performing as few linear measurements as possible on a rank-$r$ matrix $A$, we hope to construct a matrix $\hat{A}$ that satisfies $\|A - \hat{A}\|_F^2 \le c\|A\|_F^2$, for a small constant $c$. It is commonly assumed that when measuring $A$ with $S$, the response is corrupted with an independent Gaussian random variable of mean $0$ and variance $\sigma^2$. Cand\'es and Plan study non-adaptive algorithms for low rank matrix recovery using random linear measurements.

At a certain noise level, it is known that their non-adaptive algorithms need to perform $\Omega(n^2)$ measurements, which amounts to reading the entire matrix. An important question is whether adaptivity helps in decreasing the overall number of measurements. We show that any adaptive algorithm that uses $k$ linear measurements in each round and outputs an approximation to the underlying matrix with probability $\ge 9/10$ must run for $t = \Omega(\log(n^2/k)/\log\log n)$ rounds showing that any adaptive algorithm which uses $n^{2-\beta}$ linear measurements in each round must run for $\Omega(\log n/\log\log n)$ rounds to compute a reconstruction with probability $\ge 9/10$. Hence any adaptive algorithm that has $o(\log n/\log\log n)$ rounds must use an overall $\Omega(n^2)$ linear measurements. Our techniques also readily extend to obtain lower bounds on adaptive algorithms for tensor recovery and obtain measurement-vs-rounds trade-off for many sensing problems in numerical linear algebra, such as spectral norm low rank approximation, Frobenius norm low rank approximation, singular vector approximation, and more.

Authors: Praneeth Kacham, David P Woodruff

We study lower bounds on adaptive sensing algorithms for recovering low rank matrices using linear measurements. Given an $n \times n$ matrix $A$, a general linear measurement $S(A)$, for an $n \times n$ matrix $S$, is just the inner product of $S$ and $A$, each treated as $n^2$-dimensional vectors. By performing as few linear measurements as possible on a rank-$r$ matrix $A$, we hope to construct a matrix $\hat{A}$ that satisfies $\|A - \hat{A}\|_F^2 \le c\|A\|_F^2$, for a small constant $c$. It is commonly assumed that when measuring $A$ with $S$, the response is corrupted with an independent Gaussian random variable of mean $0$ and variance $\sigma^2$. Cand\'es and Plan study non-adaptive algorithms for low rank matrix recovery using random linear measurements.

At a certain noise level, it is known that their non-adaptive algorithms need to perform $\Omega(n^2)$ measurements, which amounts to reading the entire matrix. An important question is whether adaptivity helps in decreasing the overall number of measurements. We show that any adaptive algorithm that uses $k$ linear measurements in each round and outputs an approximation to the underlying matrix with probability $\ge 9/10$ must run for $t = \Omega(\log(n^2/k)/\log\log n)$ rounds showing that any adaptive algorithm which uses $n^{2-\beta}$ linear measurements in each round must run for $\Omega(\log n/\log\log n)$ rounds to compute a reconstruction with probability $\ge 9/10$. Hence any adaptive algorithm that has $o(\log n/\log\log n)$ rounds must use an overall $\Omega(n^2)$ linear measurements. Our techniques also readily extend to obtain lower bounds on adaptive algorithms for tensor recovery and obtain measurement-vs-rounds trade-off for many sensing problems in numerical linear algebra, such as spectral norm low rank approximation, Frobenius norm low rank approximation, singular vector approximation, and more.

Asynchronous Merkle Trees

from arXiv: Data Structures and Algorithms

Authors: Anoushk Kharangate

Merkle trees have become a widely successful cryptographic data structure. Enabling a vast variety of applications from checking for inconsistencies in databases like Dynamo to essential tools like Git to large scale distributed systems like Bitcoin and other blockchains. There have also been various versions of Merkle trees like Jellyfish Merkle Trees and Sparse Merkle Trees designed for different applications. However, one key drawback of all these Merkle trees is that with a large data set the cost of computing the tree increases significantly, moreover insert operations on a single leaf require re-building the entire tree. For certain use cases building the tree this way is acceptable, however in environments where compute time needs to be as low as possible and where data is processed in parallel, we are presented with a need for asynchronous computation. This paper proposes a solution where given a batch of data that has to be processed concurrently, a Merkle Tree can be constructed from the batch asynchronously without needing to recalculate the tree for every insert.

Authors: Anoushk Kharangate

Merkle trees have become a widely successful cryptographic data structure. Enabling a vast variety of applications from checking for inconsistencies in databases like Dynamo to essential tools like Git to large scale distributed systems like Bitcoin and other blockchains. There have also been various versions of Merkle trees like Jellyfish Merkle Trees and Sparse Merkle Trees designed for different applications. However, one key drawback of all these Merkle trees is that with a large data set the cost of computing the tree increases significantly, moreover insert operations on a single leaf require re-building the entire tree. For certain use cases building the tree this way is acceptable, however in environments where compute time needs to be as low as possible and where data is processed in parallel, we are presented with a need for asynchronous computation. This paper proposes a solution where given a batch of data that has to be processed concurrently, a Merkle Tree can be constructed from the batch asynchronously without needing to recalculate the tree for every insert.

Dynamic Programming Algorithms for Discovery of Antibiotic Resistance in Microbial Genomes

from arXiv: Data Structures and Algorithms

Authors: Manal Helal, Vitali Sintchenko

The translation of comparative genomics into clinical decision support tools often depends on the quality of sequence alignments. However, currently used methods of multiple sequence alignments suffer from significant biases and problems with aligning diverged sequences. The objective of this study was to develop and test a new multiple sequence alignment (MSA) algorithm suitable for the high-throughput comparative analysis of different microbial genomes. This algorithm employs an innovative tensor indexing method for partitioning the dynamic programming hyper-cube space for parallel processing. We have used the clinically relevant task of identifying regions that determine resistance to antibiotics to test the new algorithm and to compare its performance with existing MSA methods. The new method "mmDst" performed better than existing MSA algorithms for more divergent sequences because it employs a simultaneous alignment scoring recurrence, which effectively approximated the score for edge missing cell scores that fall outside the scoring region.

Authors: Manal Helal, Vitali Sintchenko

The translation of comparative genomics into clinical decision support tools often depends on the quality of sequence alignments. However, currently used methods of multiple sequence alignments suffer from significant biases and problems with aligning diverged sequences. The objective of this study was to develop and test a new multiple sequence alignment (MSA) algorithm suitable for the high-throughput comparative analysis of different microbial genomes. This algorithm employs an innovative tensor indexing method for partitioning the dynamic programming hyper-cube space for parallel processing. We have used the clinically relevant task of identifying regions that determine resistance to antibiotics to test the new algorithm and to compare its performance with existing MSA methods. The new method "mmDst" performed better than existing MSA algorithms for more divergent sequences because it employs a simultaneous alignment scoring recurrence, which effectively approximated the score for edge missing cell scores that fall outside the scoring region.

The Symmetric alpha-Stable Privacy Mechanism

from arXiv: Data Structures and Algorithms

Authors: Christopher Zawacki, Eyad Abed

With the rapid growth of digital platforms, there is increasing apprehension about how personal data is being collected, stored, and used by various entities. These concerns range from data breaches and cyber-attacks to potential misuse of personal information for targeted advertising and surveillance. As a result, differential privacy (DP) has emerged as a prominent tool for quantifying a system's level of protection. The Gaussian mechanism is commonly used because the Gaussian density is closed under convolution, a common method utilized when aggregating datasets. However, the Gaussian mechanism only satisfies approximate differential privacy. In this work, we present novel analysis of the Symmetric alpha-Stable (SaS) mechanism. We prove that the mechanism is purely differentially private while remaining closed under convolution. From our analysis, we believe the SaS Mechanism is an appealing choice for privacy focused applications.

Authors: Christopher Zawacki, Eyad Abed

With the rapid growth of digital platforms, there is increasing apprehension about how personal data is being collected, stored, and used by various entities. These concerns range from data breaches and cyber-attacks to potential misuse of personal information for targeted advertising and surveillance. As a result, differential privacy (DP) has emerged as a prominent tool for quantifying a system's level of protection. The Gaussian mechanism is commonly used because the Gaussian density is closed under convolution, a common method utilized when aggregating datasets. However, the Gaussian mechanism only satisfies approximate differential privacy. In this work, we present novel analysis of the Symmetric alpha-Stable (SaS) mechanism. We prove that the mechanism is purely differentially private while remaining closed under convolution. From our analysis, we believe the SaS Mechanism is an appealing choice for privacy focused applications.

A quasi-polynomial time algorithm for Multi-Dimensional Scaling via LP hierarchies

from arXiv: Data Structures and Algorithms

Authors: Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi

Multi-dimensional Scaling (MDS) is a family of methods for embedding pair-wise dissimilarities between $n$ objects into low-dimensional space. MDS is widely used as a data visualization tool in the social and biological sciences, statistics, and machine learning. We study the Kamada-Kawai formulation of MDS: given a set of non-negative dissimilarities $\{d_{i,j}\}_{i , j \in [n]}$ over $n$ points, the goal is to find an embedding $\{x_1,\dots,x_n\} \subset \mathbb{R}^k$ that minimizes \[ \text{OPT} = \min_{x} \mathbb{E}_{i,j \in [n]} \left[ \left(1-\frac{\|x_i - x_j\|}{d_{i,j}}\right)^2 \right] \]

Despite its popularity, our theoretical understanding of MDS is extremely limited. Recently, Demaine, Hesterberg, Koehler, Lynch, and Urschel (arXiv:2109.11505) gave the first approximation algorithm with provable guarantees for Kamada-Kawai, which achieves an embedding with cost $\text{OPT} +\epsilon$ in $n^2 \cdot 2^{\tilde{\mathcal{O}}(k \Delta^4 / \epsilon^2)}$ time, where $\Delta$ is the aspect ratio of the input dissimilarities. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on $\Delta$: for target dimension $k$, we achieve a solution with cost $\mathcal{O}(\text{OPT}^{ \hspace{0.04in}1/k } \cdot \log(\Delta/\epsilon) )+ \epsilon$ in time $n^{ \mathcal{O}(1)} \cdot 2^{\tilde{\mathcal{O}}( k^2 (\log(\Delta)/\epsilon)^{k/2 + 1} ) }$.

Our approach is based on a novel analysis of a conditioning-based rounding scheme for the Sherali-Adams LP Hierarchy. Crucially, our analysis exploits the geometry of low-dimensional Euclidean space, allowing us to avoid an exponential dependence on the aspect ratio $\Delta$. We believe our geometry-aware treatment of the Sherali-Adams Hierarchy is an important step towards developing general-purpose techniques for efficient metric optimization algorithms.

Authors: Ainesh Bakshi, Vincent Cohen-Addad, Samuel B. Hopkins, Rajesh Jayaram, Silvio Lattanzi

Multi-dimensional Scaling (MDS) is a family of methods for embedding pair-wise dissimilarities between $n$ objects into low-dimensional space. MDS is widely used as a data visualization tool in the social and biological sciences, statistics, and machine learning. We study the Kamada-Kawai formulation of MDS: given a set of non-negative dissimilarities $\{d_{i,j}\}_{i , j \in [n]}$ over $n$ points, the goal is to find an embedding $\{x_1,\dots,x_n\} \subset \mathbb{R}^k$ that minimizes \[ \text{OPT} = \min_{x} \mathbb{E}_{i,j \in [n]} \left[ \left(1-\frac{\|x_i - x_j\|}{d_{i,j}}\right)^2 \right] \]

Despite its popularity, our theoretical understanding of MDS is extremely limited. Recently, Demaine, Hesterberg, Koehler, Lynch, and Urschel (arXiv:2109.11505) gave the first approximation algorithm with provable guarantees for Kamada-Kawai, which achieves an embedding with cost $\text{OPT} +\epsilon$ in $n^2 \cdot 2^{\tilde{\mathcal{O}}(k \Delta^4 / \epsilon^2)}$ time, where $\Delta$ is the aspect ratio of the input dissimilarities. In this work, we give the first approximation algorithm for MDS with quasi-polynomial dependency on $\Delta$: for target dimension $k$, we achieve a solution with cost $\mathcal{O}(\text{OPT}^{ \hspace{0.04in}1/k } \cdot \log(\Delta/\epsilon) )+ \epsilon$ in time $n^{ \mathcal{O}(1)} \cdot 2^{\tilde{\mathcal{O}}( k^2 (\log(\Delta)/\epsilon)^{k/2 + 1} ) }$.

Our approach is based on a novel analysis of a conditioning-based rounding scheme for the Sherali-Adams LP Hierarchy. Crucially, our analysis exploits the geometry of low-dimensional Euclidean space, allowing us to avoid an exponential dependence on the aspect ratio $\Delta$. We believe our geometry-aware treatment of the Sherali-Adams Hierarchy is an important step towards developing general-purpose techniques for efficient metric optimization algorithms.

Wednesday, November 29

The Engineer and The Computer Scientist

from Computational Complexity

What is the difference between engineering and computer science? CS is not an engineering field, though there is some overlap. It's not the digital versus physical. To capture the difference we can look two tech CEOs dominating the news recently, Elon Musk and Sam Altman.

Engineers are problem solvers creating or improving technologies to reach a goal. Tesla has led the way for cars to become electric, connected and autonomous. SpaceX has develops highly capable rocket technology at lower cost. Ultimately though Tesla makes cars that go from A to B and SpaceX sends stuff into space. When Musk bought Twitter he focused on the engineering, but Twitter's challenges were not in its engineering and this is why Twitter/X has been floundering.

Computer scientists make platforms. The Internet, cloud computing, programming languages, mobile computing, cryptography, databases, social networks even NP-completeness don't focus on individual problems, rather they create environments that users and developers can apply to a variety of new applications and challenges.

AI is no exception. OpenAI has no specific goal or purpose it is trying to solve. There's AGI but that's more of a vague benchmark that may (or may not) be passed as ChatGPT and its successors continue to improve.

AWS, Python, Apple and OpenAI all have developers conferences. Tesla and SpaceX do not. Elon Musk has actually made Twitter/X harder for developers to build on. I don't hold high hopes for Grok.

It's not a perfect division, many engineers create platforms and computer scientists tackle specific problems. Nevertheless it's a good way to see the distinction between the fields.

Don't think the CS way is always the better way. You have less control of platforms, they can act in unexpected ways and people can use them unintentionally or intentionally to cause harm. Mitigating those harms is a challenge we must continuously address.

By Lance Fortnow

What is the difference between engineering and computer science? CS is not an engineering field, though there is some overlap. It's not the digital versus physical. To capture the difference we can look two tech CEOs dominating the news recently, Elon Musk and Sam Altman.

Engineers are problem solvers creating or improving technologies to reach a goal. Tesla has led the way for cars to become electric, connected and autonomous. SpaceX has develops highly capable rocket technology at lower cost. Ultimately though Tesla makes cars that go from A to B and SpaceX sends stuff into space. When Musk bought Twitter he focused on the engineering, but Twitter's challenges were not in its engineering and this is why Twitter/X has been floundering.

Computer scientists make platforms. The Internet, cloud computing, programming languages, mobile computing, cryptography, databases, social networks even NP-completeness don't focus on individual problems, rather they create environments that users and developers can apply to a variety of new applications and challenges.

AI is no exception. OpenAI has no specific goal or purpose it is trying to solve. There's AGI but that's more of a vague benchmark that may (or may not) be passed as ChatGPT and its successors continue to improve.

AWS, Python, Apple and OpenAI all have developers conferences. Tesla and SpaceX do not. Elon Musk has actually made Twitter/X harder for developers to build on. I don't hold high hopes for Grok.

It's not a perfect division, many engineers create platforms and computer scientists tackle specific problems. Nevertheless it's a good way to see the distinction between the fields.

Don't think the CS way is always the better way. You have less control of platforms, they can act in unexpected ways and people can use them unintentionally or intentionally to cause harm. Mitigating those harms is a challenge we must continuously address.

By Lance Fortnow

PhD position in Quantum Learning Theory at University of Warwick (apply by January 1, 2024)

from CCI: jobs

One funded PhD position is available in the group of Dr Matthias C. Caro, who will join the University of Warwick, UK, in Fall 2024. This is an excellent opportunity to join one of the most active CS theory groups in the UK and to become part of the interdisciplinary research initiative Warwick Quantum. Candidates […]

One funded PhD position is available in the group of Dr Matthias C. Caro, who will join the University of Warwick, UK, in Fall 2024. This is an excellent opportunity to join one of the most active CS theory groups in the UK and to become part of the interdisciplinary research initiative Warwick Quantum. Candidates interested in quantum computing and learning theory are encouraged to apply.

Website: https://warwick.ac.uk/fac/sci/dcs/news/?newsItem=8a1785d88bf6b075018c15b1e42170fb
Email: matthias.caro@fu-berlin.de

By shacharlovett

Parameterized Inapproximability Hypothesis under ETH

from arXiv: Computational Complexity

Authors: Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an $\varepsilon$ fraction of constraints for some absolute constant $\varepsilon > 0$. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap.

In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a "parallel PCP of proximity" based on the Walsh-Hadamard code.

Authors: Venkatesan Guruswami, Bingkai Lin, Xuandi Ren, Yican Sun, Kewen Wu

The Parameterized Inapproximability Hypothesis (PIH) asserts that no fixed parameter tractable (FPT) algorithm can distinguish a satisfiable CSP instance, parameterized by the number of variables, from one where every assignment fails to satisfy an $\varepsilon$ fraction of constraints for some absolute constant $\varepsilon > 0$. PIH plays the role of the PCP theorem in parameterized complexity. However, PIH has only been established under Gap-ETH, a very strong assumption with an inherent gap.

In this work, we prove PIH under the Exponential Time Hypothesis (ETH). This is the first proof of PIH from a gap-free assumption. Our proof is self-contained and elementary. We identify an ETH-hard CSP whose variables take vector values, and constraints are either linear or of a special parallel structure. Both kinds of constraints can be checked with constant soundness via a "parallel PCP of proximity" based on the Walsh-Hadamard code.

Fair Interventions in Weighted Congestion Games

from arXiv: Computational Complexity

Authors: Miriam Fischer, Martin Gairing, Dario Paccagnan

In this work we study the power and limitations of fair interventions in weighted congestion games. Specifically, we focus on interventions that aim at improving the equilibrium quality (price of anarchy) and are fair in the sense that identical players receive identical treatment. Within this setting, we provide three key contributions: First, we show that no fair intervention can reduce the price of anarchy below a given factor depending solely on the class of latencies considered. Interestingly, this lower bound is unconditional, i.e., it applies regardless of how much computation interventions are allowed to use. Second, we propose a taxation mechanism that is fair and show that the resulting price of anarchy matches this lower bound, while the mechanism can be efficiently computed in polynomial time. Third, we complement these results by showing that no intervention (fair or not) can achieve a better approximation if polynomial computability is required. We do so by proving that the minimum social cost is NP-hard to approximate below a factor identical to the one previously introduced. In doing so, we also show that the randomized algorithm proposed by Makarychev and Sviridenko (Journal of the ACM, 2018) for the class of optimization problems with a "diseconomy of scale" is optimal, and provide a novel way to derandomize its solution via equilibrium computation.

Authors: Miriam Fischer, Martin Gairing, Dario Paccagnan

In this work we study the power and limitations of fair interventions in weighted congestion games. Specifically, we focus on interventions that aim at improving the equilibrium quality (price of anarchy) and are fair in the sense that identical players receive identical treatment. Within this setting, we provide three key contributions: First, we show that no fair intervention can reduce the price of anarchy below a given factor depending solely on the class of latencies considered. Interestingly, this lower bound is unconditional, i.e., it applies regardless of how much computation interventions are allowed to use. Second, we propose a taxation mechanism that is fair and show that the resulting price of anarchy matches this lower bound, while the mechanism can be efficiently computed in polynomial time. Third, we complement these results by showing that no intervention (fair or not) can achieve a better approximation if polynomial computability is required. We do so by proving that the minimum social cost is NP-hard to approximate below a factor identical to the one previously introduced. In doing so, we also show that the randomized algorithm proposed by Makarychev and Sviridenko (Journal of the ACM, 2018) for the class of optimization problems with a "diseconomy of scale" is optimal, and provide a novel way to derandomize its solution via equilibrium computation.

Matrix Multiplication in Quadratic Time and Energy? Towards a Fine-Grained Energy-Centric Church-Turing Thesis

from arXiv: Data Structures and Algorithms

Authors: Gregory Valiant

We describe two algorithms for multiplying n x n matrices using time and energy n^2 polylog(n) under basic models of classical physics. The first algorithm is for multiplying integer-valued matrices, and the second, quite different algorithm, is for Boolean matrix multiplication. We hope this work inspires a deeper consideration of physically plausible/realizable models of computing that might allow for algorithms which improve upon the runtimes and energy usages suggested by the parallel RAM model in which each operation requires one unit of time and one unit of energy.

Authors: Gregory Valiant

We describe two algorithms for multiplying n x n matrices using time and energy n^2 polylog(n) under basic models of classical physics. The first algorithm is for multiplying integer-valued matrices, and the second, quite different algorithm, is for Boolean matrix multiplication. We hope this work inspires a deeper consideration of physically plausible/realizable models of computing that might allow for algorithms which improve upon the runtimes and energy usages suggested by the parallel RAM model in which each operation requires one unit of time and one unit of energy.

Property Testing with Online Adversaries

from arXiv: Data Structures and Algorithms

Authors: Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova

The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Specifically, after each query made by the tester is answered, the adversary can intervene and either erase or corrupt $t$ data points. In this work, we investigate a more nuanced version of the online model in order to overcome old and new impossibility results for the original model. We start by presenting an optimal tester for linearity and a lower bound for low-degree testing of Boolean functions in the original model. We overcome the lower bound by allowing batch queries, where the tester gets a group of queries answered between manipulations of the data. Our batch size is small enough so that function values for a single batch on their own give no information about whether the function is of low degree. Finally, to overcome the impossibility results of Kalemaj et al. for sortedness and the Lipschitz property of sequences, we extend the model to include $t<1$, i.e., adversaries that make less than one erasure per query. For sortedness, we characterize the rate of erasures for which online testing can be performed, exhibiting a sharp transition from optimal query complexity to impossibility of testability (with any number of queries). Our online tester works for a general class of local properties of sequences. One feature of our results is that we get new (and in some cases, simpler) optimal algorithms for several properties in the standard property testing model.

Authors: Omri Ben-Eliezer, Esty Kelman, Uri Meir, Sofya Raskhodnikova

The online manipulation-resilient testing model, proposed by Kalemaj, Raskhodnikova and Varma (ITCS 2022 and Theory of Computing 2023), studies property testing in situations where access to the input degrades continuously and adversarially. Specifically, after each query made by the tester is answered, the adversary can intervene and either erase or corrupt $t$ data points. In this work, we investigate a more nuanced version of the online model in order to overcome old and new impossibility results for the original model. We start by presenting an optimal tester for linearity and a lower bound for low-degree testing of Boolean functions in the original model. We overcome the lower bound by allowing batch queries, where the tester gets a group of queries answered between manipulations of the data. Our batch size is small enough so that function values for a single batch on their own give no information about whether the function is of low degree. Finally, to overcome the impossibility results of Kalemaj et al. for sortedness and the Lipschitz property of sequences, we extend the model to include $t<1$, i.e., adversaries that make less than one erasure per query. For sortedness, we characterize the rate of erasures for which online testing can be performed, exhibiting a sharp transition from optimal query complexity to impossibility of testability (with any number of queries). Our online tester works for a general class of local properties of sequences. One feature of our results is that we get new (and in some cases, simpler) optimal algorithms for several properties in the standard property testing model.

An Exploration of Left-Corner Transformations

from arXiv: Data Structures and Algorithms

Authors: Andreas Opedal, Eleftheria Tsipidi, Tiago Pimentel, Ryan Cotterell, Tim Vieira

The left-corner transformation (Rosenkrantz and Lewis, 1970) is used to remove left recursion from context-free grammars, which is an important step towards making the grammar parsable top-down with simple techniques. This paper generalizes prior left-corner transformations to support semiring-weighted production rules and to provide finer-grained control over which left corners may be moved. Our generalized left-corner transformation (GLCT) arose from unifying the left-corner transformation and speculation transformation (Eisner and Blatz, 2007), originally for logic programming. Our new transformation and speculation define equivalent weighted languages. Yet, their derivation trees are structurally different in an important way: GLCT replaces left recursion with right recursion, and speculation does not. We also provide several technical results regarding the formal relationships between the outputs of GLCT, speculation, and the original grammar. Lastly, we empirically investigate the efficiency of GLCT for left-recursion elimination from grammars of nine languages.

Authors: Andreas Opedal, Eleftheria Tsipidi, Tiago Pimentel, Ryan Cotterell, Tim Vieira

The left-corner transformation (Rosenkrantz and Lewis, 1970) is used to remove left recursion from context-free grammars, which is an important step towards making the grammar parsable top-down with simple techniques. This paper generalizes prior left-corner transformations to support semiring-weighted production rules and to provide finer-grained control over which left corners may be moved. Our generalized left-corner transformation (GLCT) arose from unifying the left-corner transformation and speculation transformation (Eisner and Blatz, 2007), originally for logic programming. Our new transformation and speculation define equivalent weighted languages. Yet, their derivation trees are structurally different in an important way: GLCT replaces left recursion with right recursion, and speculation does not. We also provide several technical results regarding the formal relationships between the outputs of GLCT, speculation, and the original grammar. Lastly, we empirically investigate the efficiency of GLCT for left-recursion elimination from grammars of nine languages.

On the quantum time complexity of divide and conquer

from arXiv: Data Structures and Algorithms

Authors: Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha

We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup and apply these theorems to an array of problems involving strings, integers, and geometric objects. They include LONGEST DISTINCT SUBSTRING, KLEE'S COVERAGE, several optimization problems on stock transactions, and k-INCREASING SUBSEQUENCE. For most of these results, our quantum time upper bound matches the quantum query lower bound for the problem, up to polylogarithmic factors.

Authors: Jonathan Allcock, Jinge Bao, Aleksandrs Belovs, Troy Lee, Miklos Santha

We initiate a systematic study of the time complexity of quantum divide and conquer algorithms for classical problems. We establish generic conditions under which search and minimization problems with classical divide and conquer algorithms are amenable to quantum speedup and apply these theorems to an array of problems involving strings, integers, and geometric objects. They include LONGEST DISTINCT SUBSTRING, KLEE'S COVERAGE, several optimization problems on stock transactions, and k-INCREASING SUBSEQUENCE. For most of these results, our quantum time upper bound matches the quantum query lower bound for the problem, up to polylogarithmic factors.

A Combinatorial Approach to Robust PCA

from arXiv: Data Structures and Algorithms

Authors: Weihao Kong, Mingda Qiao, Rajat Sen

We study the problem of recovering Gaussian data under adversarial corruptions when the noises are low-rank and the corruptions are on the coordinate level. Concretely, we assume that the Gaussian noises lie in an unknown $k$-dimensional subspace $U \subseteq \mathbb{R}^d$, and $s$ randomly chosen coordinates of each data point fall into the control of an adversary. This setting models the scenario of learning from high-dimensional yet structured data that are transmitted through a highly-noisy channel, so that the data points are unlikely to be entirely clean.

Our main result is an efficient algorithm that, when $ks^2 = O(d)$, recovers every single data point up to a nearly-optimal $\ell_1$ error of $\tilde O(ks/d)$ in expectation. At the core of our proof is a new analysis of the well-known Basis Pursuit (BP) method for recovering a sparse signal, which is known to succeed under additional assumptions (e.g., incoherence or the restricted isometry property) on the underlying subspace $U$. In contrast, we present a novel approach via studying a natural combinatorial problem and show that, over the randomness in the support of the sparse signal, a high-probability error bound is possible even if the subspace $U$ is arbitrary.

Authors: Weihao Kong, Mingda Qiao, Rajat Sen

We study the problem of recovering Gaussian data under adversarial corruptions when the noises are low-rank and the corruptions are on the coordinate level. Concretely, we assume that the Gaussian noises lie in an unknown $k$-dimensional subspace $U \subseteq \mathbb{R}^d$, and $s$ randomly chosen coordinates of each data point fall into the control of an adversary. This setting models the scenario of learning from high-dimensional yet structured data that are transmitted through a highly-noisy channel, so that the data points are unlikely to be entirely clean.

Our main result is an efficient algorithm that, when $ks^2 = O(d)$, recovers every single data point up to a nearly-optimal $\ell_1$ error of $\tilde O(ks/d)$ in expectation. At the core of our proof is a new analysis of the well-known Basis Pursuit (BP) method for recovering a sparse signal, which is known to succeed under additional assumptions (e.g., incoherence or the restricted isometry property) on the underlying subspace $U$. In contrast, we present a novel approach via studying a natural combinatorial problem and show that, over the randomness in the support of the sparse signal, a high-probability error bound is possible even if the subspace $U$ is arbitrary.

l2Match: Optimization Techniques on Subgraph Matching Algorithm using Label Pair, Neighboring Label Index, and Jump-Redo method

from arXiv: Data Structures and Algorithms

Authors: C. Q. Cheng, K. S. Wong, L. K. Soon

Graph database is designed to store bidirectional relationships between objects and facilitate the traversal process to extract a subgraph. However, the subgraph matching process is an NP-Complete problem. Existing solutions to this problem usually employ a filter-and-verification framework and a divide-and-conquer method. The filter-and-verification framework minimizes the number of inputs to the verification stage by filtering and pruning invalid candidates as much as possible. Meanwhile, subgraph matching is performed on the substructure decomposed from the larger graph to yield partial embedding. Subsequently, the recursive traversal or set intersection technique combines the partial embedding into a complete subgraph. In this paper, we first present a comprehensive literature review of the state-of-the-art solutions. l2Match, a subgraph isomorphism algorithm for small queries utilizing a Label-Pair Index and filtering method, is then proposed and presented as a proof of concept. Empirical experimentation shows that l2Match outperforms related state-of-the-art solutions, and the proposed methods optimize the existing algorithms.

Authors: C. Q. Cheng, K. S. Wong, L. K. Soon

Graph database is designed to store bidirectional relationships between objects and facilitate the traversal process to extract a subgraph. However, the subgraph matching process is an NP-Complete problem. Existing solutions to this problem usually employ a filter-and-verification framework and a divide-and-conquer method. The filter-and-verification framework minimizes the number of inputs to the verification stage by filtering and pruning invalid candidates as much as possible. Meanwhile, subgraph matching is performed on the substructure decomposed from the larger graph to yield partial embedding. Subsequently, the recursive traversal or set intersection technique combines the partial embedding into a complete subgraph. In this paper, we first present a comprehensive literature review of the state-of-the-art solutions. l2Match, a subgraph isomorphism algorithm for small queries utilizing a Label-Pair Index and filtering method, is then proposed and presented as a proof of concept. Empirical experimentation shows that l2Match outperforms related state-of-the-art solutions, and the proposed methods optimize the existing algorithms.

$k$-times bin packing and its application to fair electricity distribution

from arXiv: Data Structures and Algorithms

Authors: Dinesh Kumar Baghel, Erel Segal-Halevi

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a new variant called $k$-times bin packing ($k$BP), where the goal is to pack the items such that each item appears exactly $k$ times, in $k$ different bins. We generalize some existing approximation algorithms for bin-packing to solve $k$BP, and analyze their performance ratio.

The study of $k$BP is motivated by the problem of fair electricity distribution. In many developing countries, the total electricity demand is higher than the supply capacity. We show that $k$-times bin packing can be used to distribute the electricity in a fair and efficient way. Particularly, we implement generalizations of the First-Fit and First-Fit-Decreasing bin-packing algorithms to solve $k$BP, and apply the generalizations to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem.

Authors: Dinesh Kumar Baghel, Erel Segal-Halevi

Given items of different sizes and a fixed bin capacity, the bin-packing problem is to pack these items into a minimum number of bins such that the sum of item sizes in a bin does not exceed the capacity. We define a new variant called $k$-times bin packing ($k$BP), where the goal is to pack the items such that each item appears exactly $k$ times, in $k$ different bins. We generalize some existing approximation algorithms for bin-packing to solve $k$BP, and analyze their performance ratio.

The study of $k$BP is motivated by the problem of fair electricity distribution. In many developing countries, the total electricity demand is higher than the supply capacity. We show that $k$-times bin packing can be used to distribute the electricity in a fair and efficient way. Particularly, we implement generalizations of the First-Fit and First-Fit-Decreasing bin-packing algorithms to solve $k$BP, and apply the generalizations to real electricity demand data. We show that our generalizations outperform existing heuristic solutions to the same problem.