Thank you to arXiv for use of its open access interoperability.
Note: the date of arXiv entries announced right after publication holidays might incorrectly show up as the date of the publication holiday itself. This is due to our ad hoc method of inferring announcement dates, which are not returned by the arXiv API.
The Department of Computing Science at the University of Alberta invites applications for one tenure-track Assistant Professor position, starting as early as July 1st, 2025 in either the area of Theoretical Computing Science (e.g., Data Structures & Algorithm; Streaming, Sketching, and Big Data Algorithms; Computational Complexity; Discrete Optimization; etc.) or Computer Systems. Website: apps.ualberta.ca/careers/posting/1658 Email: […]
The Department of Computing Science at the University of Alberta invites applications for one tenure-track Assistant Professor position, starting as early as July 1st, 2025 in either the area of Theoretical Computing Science (e.g., Data Structures & Algorithm; Streaming, Sketching, and Big Data Algorithms; Computational Complexity; Discrete Optimization; etc.) or Computer Systems.
The hidden technology under the hood of numerical optimization
This is the live blog of Lecture 16 of my graduate class “Convex Optimization.” A Table of Contents is here.
Even though this class focuses on modeling, it’s helpful to understand a little bit about how to solve convex optimization problems. Many people can avoid ever looking across the abstraction boundaries. It’s likely possible to get a feel for the optimal use of tools like cvxpy without digging too much into how they work. Whether using Stata to solve regressions or pytorch to fit neural networks, you can learn heuristics for speedups without knowing what’s under the hood.
Unfortunately, the sad part of computational mathematics is computers are never fast enough. We need to pose problems that are solvable on the compute to which we have access. If you don’t have billions of dollars of Azure credits, then you have to understand a bit about what your solver does to get a solution in a reasonable amount of time. Solver knowledge can save you a lot of trial and error and reliance on folklore. A little bit can take you a long way.
In this class, I’ll focus on the solvers that try to solve optimality conditions. Gradient-based solvers are the best-known example. For unconstrained convex problems, the gradient vanishes at the optimal solution. So to minimize a function f, our goal is to find a point where
This is solving a nonlinear equation.
For constrained optimization, the KKT conditions generalize the gradient condition. They are a set of equations that are necessary and sufficient for optimality, a combination of nonlinear equations (the gradient of the Lagrangian must equal zero, the equality constraints must be satisfied, and complementary slackness must hold) and constraints on the nonnegativity of variables. Convex solvers try to solve these nonlinear equations subject to holding variables being nonnegative.
Nonlinear equations don’t typically have nice closed form solutions. To be fair, we learn in high school that linear equations don’t have simple solutions either. We have to slog through Gaussian elimination to solve systems of three equations in three variables. Nonlinear equations are worse, however, as there are no natural analogs of Gaussian elimination.
Instead, we solve nonlinear equations by sequentially solving linear equations. The most famous example of solving nonlinear equations by linear equations is called Newton’s method. Let’s say you want to solve a nonlinear system of equations F(x) = 0, which has n variables and n equations. That is, F has an n-dimensional vector as input and an n-dimensional vector as output. Newton’s method iteratively solves a linear approximation to this equation. Suppose your current approximation is x0. You can make a Taylor approximation to F as
Since F maps n-vectors to n-vectors, the “gradient” here is an n by n matrix called the Jacobian of F. If we set the Taylor approximation equal to zero, we get the update
where v is the solution to the linear equation
Under reasonable conditions, iterating this procedure will find the optimal x.
I’ll talk more about Newton’s method in the coming lectures, but I wanted to at least introduce it today to show why we care so much about solving systems of linear equations. The backbone of optimization methods is the solution of linear equations.
Since the dawn of the computer, we’ve optimized our architectures to solve linear equations. Linear systems solvers are built upon optimized computational primitives that let the end user type “A\b” or “np.linalg.solve(A,b),” and then you don’t have to worry about what’s under the hood. If you can reduce your optimization problem to a few of these API calls, you should consider this a win. You can lean on some of the most optimized numerical software in existence.
Except, as I’ve been saying, it’s not quite that easy. Algorithms for linear equation solving run in “polynomial time,” but the associated scaling may still be prohibitive. Adding two n-vectors together requires approximately n arithmetic operations (or FLOPs, if you prefer). An algorithm that requires a constant multiple of n operations runs in linear time. Multiplying an n x n matrix times a vector requires approximately 2n2 arithmetic operations. Algorithms that require a constant multiple of n2 operations run in quadratic time. Solving Ax=b for general matrices requires on the order of n3 operations, called cubic time. For large systems, cubic time algorithms are prohibitively expensive.
It’s thus important for a modeler to understand how computers solve these systems. You want to build models that lean on the strengths of your solvers. If I tell you that arranging your model in a particular order can buy you a factor of 10 speedup, I’m sure you’ll take it. You might never implement a linear system solver, but you should know which models the solvers are best suited for.
Hence, our tour of convex optimization solvers starts with a tour of linear system solvers. Some problems can be solved in linear time. The simplest are diagonal systems. If A is a diagonal matrix, then you can solve for each coordinate independently. This requires only n arithmetic operations. Other more complicated matrix forms also admit linear time solutions. A notable example is the tridiagonal system, where the matrix A is only nonzero on entries just above and below the matrix diagonal.
A step up in complexity is quadratic time. If a matrix is orthogonal, so that A-1 = AT, then you can invert it by a matrix multiply in quadratic time. If a matrix is lower triangular or upper triangular, substitution algorithms solve the associated systems in quadratic time.
Linear systems solvers try to factor the matrix A into a product of matrices where equation solving is at worst quadratic time. With such a factorization, you can solve your system in quadratic time. Most of the cost in modern linear systems solving is thus in matrix factorization. Today’s lecture will take a tour of the most common factorization techniques.
Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the existence of area laws. Although they are a simplified model of quantum computation, the status of the commuting local Hamiltonian problem remains largely unknown. A number of works have shown that increasingly expressive families of commuting local Hamiltonians admit completely classical verifiers. Despite intense work, the largest class of commuting local Hamiltonians we can place in NP are those on a square lattice, where each lattice site is a qutrit. Even worse, many of the techniques used to analyze these problems rely heavily on the geometry of the square lattice and the properties of the numbers 2 and 3 as local dimensions. In this work, we present a new technique to analyze the complexity of various families of commuting local Hamiltonians: guided reductions. Intuitively, these are a generalization of typical reduction where the prover provides a guide so that the verifier can construct a simpler Hamiltonian. The core of our reduction is a new rounding technique based on a combination of Jordan's Lemma and the Structure Lemma. Our rounding technique is much more flexible than previous work, and allows us to show that a larger family of commuting local Hamiltonians is in NP, albiet with the restriction that all terms are rank-1. Specifically, we prove the following two results:
1. Commuting local Hamiltonians in 2D that are rank-1 are contained in NP, independent of the qudit dimension. Note that this family of commuting local Hamiltonians has no restriction on the local dimension or the locality.
2. We prove that rank-1, 3D commuting Hamiltonians with qudits on edges are in NP. To our knowledge this is the first time a family of 3D commuting local Hamiltonians has been contained in NP.
Commuting local Hamiltonians provide a testing ground for studying many of the most interesting open questions in quantum information theory, including the quantum PCP conjecture and the existence of area laws. Although they are a simplified model of quantum computation, the status of the commuting local Hamiltonian problem remains largely unknown. A number of works have shown that increasingly expressive families of commuting local Hamiltonians admit completely classical verifiers. Despite intense work, the largest class of commuting local Hamiltonians we can place in NP are those on a square lattice, where each lattice site is a qutrit. Even worse, many of the techniques used to analyze these problems rely heavily on the geometry of the square lattice and the properties of the numbers 2 and 3 as local dimensions. In this work, we present a new technique to analyze the complexity of various families of commuting local Hamiltonians: guided reductions. Intuitively, these are a generalization of typical reduction where the prover provides a guide so that the verifier can construct a simpler Hamiltonian. The core of our reduction is a new rounding technique based on a combination of Jordan's Lemma and the Structure Lemma. Our rounding technique is much more flexible than previous work, and allows us to show that a larger family of commuting local Hamiltonians is in NP, albiet with the restriction that all terms are rank-1. Specifically, we prove the following two results:
1. Commuting local Hamiltonians in 2D that are rank-1 are contained in NP, independent of the qudit dimension. Note that this family of commuting local Hamiltonians has no restriction on the local dimension or the locality.
2. We prove that rank-1, 3D commuting Hamiltonians with qudits on edges are in NP. To our knowledge this is the first time a family of 3D commuting local Hamiltonians has been contained in NP.
Topological data analysis (TDA) aims to extract noise-robust features from a
data set by examining the number and persistence of holes in its topology. We
show that a computational problem closely related to a core task in TDA --
determining whether a given hole persists across different length scales -- is
$\mathsf{BQP}_1$-hard and contained in $\mathsf{BQP}$. This result implies an
exponential quantum speedup for this problem under standard
complexity-theoretic assumptions. Our approach relies on encoding the
persistence of a hole in a variant of the guided sparse Hamiltonian problem,
where the guiding state is constructed from a harmonic representative of the
hole.
Topological data analysis (TDA) aims to extract noise-robust features from a
data set by examining the number and persistence of holes in its topology. We
show that a computational problem closely related to a core task in TDA --
determining whether a given hole persists across different length scales -- is
$\mathsf{BQP}_1$-hard and contained in $\mathsf{BQP}$. This result implies an
exponential quantum speedup for this problem under standard
complexity-theoretic assumptions. Our approach relies on encoding the
persistence of a hole in a variant of the guided sparse Hamiltonian problem,
where the guiding state is constructed from a harmonic representative of the
hole.
Authors: Simon C. Marshall, Scott Aaronson, Vedran Dunjko
This paper furthers existing evidence that quantum computers are capable of
computations beyond classical computers. Specifically, we strengthen the
collapse of the polynomial hierarchy to the second level if: (i) Quantum
computers with postselection are as powerful as classical computers with
postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum
sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$,
$\mathsf{DQC1}$) can be approximately performed by a classical computer
(contingent on existing assumptions). This last result implies that if any of
these experiment's hardness conjectures hold, then quantum computers can
implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$)
unless the polynomial hierarchy collapses to its 2nd level. These results are
an improvement over previous work which either achieved a collapse to the third
level or were concerned with exact sampling, a physically impractical case.
The workhorse of these results is a new technical complexity-theoretic result
which we believe could have value beyond quantum computation. In particular, we
prove that if there exists an equivalence between problems solvable with an
exact counting oracle and problems solvable with an approximate counting
oracle, then the polynomial hierarchy collapses to its second level, indeed to
$\mathsf{ZPP^{NP}}$.
This paper furthers existing evidence that quantum computers are capable of
computations beyond classical computers. Specifically, we strengthen the
collapse of the polynomial hierarchy to the second level if: (i) Quantum
computers with postselection are as powerful as classical computers with
postselection ($\mathsf{PostBQP=PostBPP}$), (ii) any one of several quantum
sampling experiments ($\mathsf{BosonSampling}$, $\mathsf{IQP}$,
$\mathsf{DQC1}$) can be approximately performed by a classical computer
(contingent on existing assumptions). This last result implies that if any of
these experiment's hardness conjectures hold, then quantum computers can
implement functions classical computers cannot ($\mathsf{FBQP\neq FBPP}$)
unless the polynomial hierarchy collapses to its 2nd level. These results are
an improvement over previous work which either achieved a collapse to the third
level or were concerned with exact sampling, a physically impractical case.
The workhorse of these results is a new technical complexity-theoretic result
which we believe could have value beyond quantum computation. In particular, we
prove that if there exists an equivalence between problems solvable with an
exact counting oracle and problems solvable with an approximate counting
oracle, then the polynomial hierarchy collapses to its second level, indeed to
$\mathsf{ZPP^{NP}}$.
It is shown that $S(G) = O\left(m/\log_2 m + d\right)$ pebbles are sufficient
to pebble any DAG $G=(V,E)$, with $m$ edges and maximum in-degree $d$. It was
previously known that $S(G) = O\left(d n/\log n\right)$. The result builds on
two novel ideas. The first is the notion of $B-budget\ decomposition$ of a DAG
$G$, an efficiently computable partition of $G$ into at most $2^{\lfloor
\frac{m}{B} \rfloor}$ sub-DAGs, whose cumulative space requirement is at most
$B$. The second is the challenging vertices technique, which constructs a
pebbling schedule for $G$ from a pebbling schedule for a simplified DAG $G'$,
obtained by removing from $G$ a selected set of vertices $W$ and their incident
edges. This technique also yields improved pebbling upper bounds for DAGs with
bounded genus and for DAGs with bounded topological depth.
It is shown that $S(G) = O\left(m/\log_2 m + d\right)$ pebbles are sufficient
to pebble any DAG $G=(V,E)$, with $m$ edges and maximum in-degree $d$. It was
previously known that $S(G) = O\left(d n/\log n\right)$. The result builds on
two novel ideas. The first is the notion of $B-budget\ decomposition$ of a DAG
$G$, an efficiently computable partition of $G$ into at most $2^{\lfloor
\frac{m}{B} \rfloor}$ sub-DAGs, whose cumulative space requirement is at most
$B$. The second is the challenging vertices technique, which constructs a
pebbling schedule for $G$ from a pebbling schedule for a simplified DAG $G'$,
obtained by removing from $G$ a selected set of vertices $W$ and their incident
edges. This technique also yields improved pebbling upper bounds for DAGs with
bounded genus and for DAGs with bounded topological depth.
Algebraic matrix multiplication algorithms are designed by bounding the rank
of matrix multiplication tensors, and then using a recursive method. However,
designing algorithms in this way quickly leads to large constant factors: if
one proves that the tensor for multiplying $n \times n$ matrices has rank $\leq
t$, then the resulting recurrence shows that $M \times M$ matrices can be
multiplied using $O(n^2 \cdot M^{\log_n t})$ operations, where the leading
constant scales proportionally to $n^2$. Even modest increases in $n$ can blow
up the leading constant too much to be worth the slight decrease in the
exponent of $M$. Meanwhile, the asymptotically best algorithms use very large
$n$, such that $n^2$ is larger than the number of atoms in the visible
universe!
In this paper, we give new ways to use tensor rank bounds to design matrix
multiplication algorithms, which lead to smaller leading constants than the
standard recursive method. Our main result shows that, if the tensor for
multiplying $n \times n$ matrices has rank $\leq t$, then $M \times M$ matrices
can be multiplied using only $n^{O(1/(\log n)^{0.33})} \cdot M^{\log_n t}$
operations. In other words, we improve the leading constant in general from
$O(n^2)$ to $n^{O(1/(\log n)^{0.33})} < n^{o(1)}$. We then apply this and
further improve the leading constant in a number of situations of interest. We
show that, in the popularly-conjectured case where $\omega=2$, a new, different
recursive approach can lead to an improvement. We also show that the leading
constant of the current asymptotically fastest matrix multiplication algorithm,
and any algorithm designed using the group-theoretic method, can be further
improved by taking advantage of additional structure of the underlying tensor
identities.
Algebraic matrix multiplication algorithms are designed by bounding the rank
of matrix multiplication tensors, and then using a recursive method. However,
designing algorithms in this way quickly leads to large constant factors: if
one proves that the tensor for multiplying $n \times n$ matrices has rank $\leq
t$, then the resulting recurrence shows that $M \times M$ matrices can be
multiplied using $O(n^2 \cdot M^{\log_n t})$ operations, where the leading
constant scales proportionally to $n^2$. Even modest increases in $n$ can blow
up the leading constant too much to be worth the slight decrease in the
exponent of $M$. Meanwhile, the asymptotically best algorithms use very large
$n$, such that $n^2$ is larger than the number of atoms in the visible
universe!
In this paper, we give new ways to use tensor rank bounds to design matrix
multiplication algorithms, which lead to smaller leading constants than the
standard recursive method. Our main result shows that, if the tensor for
multiplying $n \times n$ matrices has rank $\leq t$, then $M \times M$ matrices
can be multiplied using only $n^{O(1/(\log n)^{0.33})} \cdot M^{\log_n t}$
operations. In other words, we improve the leading constant in general from
$O(n^2)$ to $n^{O(1/(\log n)^{0.33})} < n^{o(1)}$. We then apply this and
further improve the leading constant in a number of situations of interest. We
show that, in the popularly-conjectured case where $\omega=2$, a new, different
recursive approach can lead to an improvement. We also show that the leading
constant of the current asymptotically fastest matrix multiplication algorithm,
and any algorithm designed using the group-theoretic method, can be further
improved by taking advantage of additional structure of the underlying tensor
identities.
Authors: Alexander A. Sherstov, Andrey A. Storozhenko
We fully determine the communication complexity of approximating matrix rank,
over any finite field $\mathbb{F}$. We study the most general version of this
problem, where $0\leq r0$. Our result is an
exponential improvement in $k$ over previous work.
We also settle the randomized and quantum communication complexity of several
other linear-algebraic problems, for all settings of parameters. This includes
the determinant problem (given matrices $A$ and $B$, distinguish between the
cases $\mathrm{det}(A+B)=a$ and $\mathrm{det}(A+B)=b$, for fixed field elements
$a\ne b)$ and the subspace sum and subspace intersection problem (given
subspaces $S$ and $T$ of known dimensions $m$ and $\ell$, respectively,
approximate the dimensions of $S+T$ and $S\cap T$).
We fully determine the communication complexity of approximating matrix rank,
over any finite field $\mathbb{F}$. We study the most general version of this
problem, where $0\leq r0$. Our result is an
exponential improvement in $k$ over previous work.
We also settle the randomized and quantum communication complexity of several
other linear-algebraic problems, for all settings of parameters. This includes
the determinant problem (given matrices $A$ and $B$, distinguish between the
cases $\mathrm{det}(A+B)=a$ and $\mathrm{det}(A+B)=b$, for fixed field elements
$a\ne b)$ and the subspace sum and subspace intersection problem (given
subspaces $S$ and $T$ of known dimensions $m$ and $\ell$, respectively,
approximate the dimensions of $S+T$ and $S\cap T$).
Authors: Herbert Edelsbrunner, Alexey Garber, Morteza Saghafian
We generalize a classical result by Boris Delaunay that introduced Delaunay
triangulations. In particular, we prove that for a locally finite and coarsely
dense generic point set $A$ in $\mathbb{R}^d$, every generic point of
$\mathbb{R}^d$ belongs to exactly $\binom{d+k}{d}$ simplices whose vertices
belong to $A$ and whose circumspheres enclose exactly $k$ points of $A$. We
extend this result to the cases in which the points are weighted, and when $A$
contains only finitely many points in $\mathbb{R}^d$ or in $\mathbb{S}^d$.
Furthermore, we use the result to give a new geometric proof for the fact that
volumes of hypersimplices are Eulerian numbers.
We generalize a classical result by Boris Delaunay that introduced Delaunay
triangulations. In particular, we prove that for a locally finite and coarsely
dense generic point set $A$ in $\mathbb{R}^d$, every generic point of
$\mathbb{R}^d$ belongs to exactly $\binom{d+k}{d}$ simplices whose vertices
belong to $A$ and whose circumspheres enclose exactly $k$ points of $A$. We
extend this result to the cases in which the points are weighted, and when $A$
contains only finitely many points in $\mathbb{R}^d$ or in $\mathbb{S}^d$.
Furthermore, we use the result to give a new geometric proof for the fact that
volumes of hypersimplices are Eulerian numbers.
Authors: Roua Rouatbi, Juan Esteban Suarez, Ivo F. Sbalzarini
We introduce the Push-Forward Signed Distance Morphometric (PF-SDM), a novel
method for shape quantification in biomedical imaging that is continuous,
interpretable, and invariant to shape-preserving transformations. PF-SDM
effectively captures the geometric properties of shapes, including their
topological skeletons and radial symmetries. This results in a robust and
interpretable shape descriptor that generalizes to capture temporal shape
dynamics. Importantly, PF-SDM avoids certain issues of previous geometric
morphometrics, like Elliptical Fourier Analysis and Generalized Procrustes
Analysis, such as coefficient correlations and landmark choices. We present the
PF-SDM theory, provide a practically computable algorithm, and benchmark it on
synthetic data.
We introduce the Push-Forward Signed Distance Morphometric (PF-SDM), a novel
method for shape quantification in biomedical imaging that is continuous,
interpretable, and invariant to shape-preserving transformations. PF-SDM
effectively captures the geometric properties of shapes, including their
topological skeletons and radial symmetries. This results in a robust and
interpretable shape descriptor that generalizes to capture temporal shape
dynamics. Importantly, PF-SDM avoids certain issues of previous geometric
morphometrics, like Elliptical Fourier Analysis and Generalized Procrustes
Analysis, such as coefficient correlations and landmark choices. We present the
PF-SDM theory, provide a practically computable algorithm, and benchmark it on
synthetic data.
Zigzag filtrations of simplicial complexes generalize the usual filtrations
by allowing simplex deletions in addition to simplex insertions. The barcodes
computed from zigzag filtrations encode the evolution of homological features.
Although one can locate a particular feature at any index in the filtration
using existing algorithms, the resulting representatives may not be compatible
with the zigzag: a representative cycle at one index may not map into a
representative cycle at its neighbor. For this, one needs to compute compatible
representative cycles along each bar in the barcode. Even though it is known
that the barcode for a zigzag filtration with $m$ insertions and deletions can
be computed in $O(m^\omega)$ time, it is not known how to compute the
compatible representatives so efficiently. For a non-zigzag filtration, the
classical matrix-based algorithm provides representatives in $O(m^3)$ time,
which can be improved to $O(m^\omega)$. However, no known algorithm for zigzag
filtrations computes the representatives with the $O(m^3)$ time bound. We
present an $O(m^2n)$ time algorithm for this problem, where $n\leq m$ is the
size of the largest complex in the filtration.
Zigzag filtrations of simplicial complexes generalize the usual filtrations
by allowing simplex deletions in addition to simplex insertions. The barcodes
computed from zigzag filtrations encode the evolution of homological features.
Although one can locate a particular feature at any index in the filtration
using existing algorithms, the resulting representatives may not be compatible
with the zigzag: a representative cycle at one index may not map into a
representative cycle at its neighbor. For this, one needs to compute compatible
representative cycles along each bar in the barcode. Even though it is known
that the barcode for a zigzag filtration with $m$ insertions and deletions can
be computed in $O(m^\omega)$ time, it is not known how to compute the
compatible representatives so efficiently. For a non-zigzag filtration, the
classical matrix-based algorithm provides representatives in $O(m^3)$ time,
which can be improved to $O(m^\omega)$. However, no known algorithm for zigzag
filtrations computes the representatives with the $O(m^3)$ time bound. We
present an $O(m^2n)$ time algorithm for this problem, where $n\leq m$ is the
size of the largest complex in the filtration.
Trace distance and infidelity (induced by square root fidelity), as basic
measures of the closeness of quantum states, are commonly used in quantum state
discrimination, certification, and tomography. However, the sample complexity
for their estimation still remains open. In this paper, we solve this problem
for pure states. We present a quantum algorithm that estimates the trace
distance and square root fidelity between pure states to within additive error
$\varepsilon$, given sample access to their identical copies. Our algorithm
achieves the optimal sample complexity $\Theta(1/\varepsilon^2)$, improving the
long-standing folklore $O(1/\varepsilon^4)$. Our algorithm is composed of a
samplized phase estimation of the product of two Householder reflections.
Notably, an improved (multi-)samplizer for pure states is used as an
algorithmic tool in our construction, through which any quantum query algorithm
using $Q$ queries to the reflection operator about a pure state $|\psi\rangle$
can be converted to a $\delta$-close (in the diamond norm) quantum sample
algorithm using $\Theta(Q^2/\delta)$ samples of $|\psi\rangle$. This samplizer
for pure states is shown to be optimal.
Trace distance and infidelity (induced by square root fidelity), as basic
measures of the closeness of quantum states, are commonly used in quantum state
discrimination, certification, and tomography. However, the sample complexity
for their estimation still remains open. In this paper, we solve this problem
for pure states. We present a quantum algorithm that estimates the trace
distance and square root fidelity between pure states to within additive error
$\varepsilon$, given sample access to their identical copies. Our algorithm
achieves the optimal sample complexity $\Theta(1/\varepsilon^2)$, improving the
long-standing folklore $O(1/\varepsilon^4)$. Our algorithm is composed of a
samplized phase estimation of the product of two Householder reflections.
Notably, an improved (multi-)samplizer for pure states is used as an
algorithmic tool in our construction, through which any quantum query algorithm
using $Q$ queries to the reflection operator about a pure state $|\psi\rangle$
can be converted to a $\delta$-close (in the diamond norm) quantum sample
algorithm using $\Theta(Q^2/\delta)$ samples of $|\psi\rangle$. This samplizer
for pure states is shown to be optimal.
We show that assuming the availability of the processor with variable
precision arithmetic, we can compute matrix-by-matrix multiplications in
$O(N^2log_2N)$ computational complexity. We replace the standard
matrix-by-matrix multiplications algorithm
$\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}=\begin{bmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\end{bmatrix}$
by
$\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}=\Bigl\lfloor\begin{bmatrix}
(A_{11}+\epsilon A_{12})(B_{11}+1/{\epsilon}B_{21})&(A_{11}+\epsilon
A_{12})(B_{12}+1/{\epsilon}B_{22})\\(A_{21}+\epsilon
A_{22})(B_{11}+1/{\epsilon}B_{21})&(A_{21}+\epsilon
A_{22})(B_{12}+1/{\epsilon}B_{22})\end{bmatrix}\Bigr\rfloor \mod
\frac{1}{\epsilon}$. The resulting computational complexity for $N\times N$
matrices can be estimated from recursive equation $T(N)=4(N/2)^2$
(multiplication of a matrix by number)+$4(N/2)^2$ (additions of
matrices)+$2N^2$ (floor and modulo)+$4T(N/2)$ (recursive calls) as
$O(N^2log_2N)$. The novelty of the method lies in the observation, somehow
ignored by other matrix-by-matrix multiplication algorithms, that we can
multiply matrix entries by non-integer numbers to improve computational
complexity. In other words, while having a processor that can compute
multiplications, additions, modulo and floor operations with variable precision
arithmetic in $O(1)$, we can obtain a matrix-by-matrix multiplication algorithm
with $O(N^2log_2N)$ computational complexity. We also present a MATLAB code
using VPA variable precision arithmetic emulator that can multiply matrices of
size $N\times N$ using $(4log_2N+1)N^2$ variable precision arithmetic
operations. This emulator uses $O(N)$ digits to run our algorithm.
We show that assuming the availability of the processor with variable
precision arithmetic, we can compute matrix-by-matrix multiplications in
$O(N^2log_2N)$ computational complexity. We replace the standard
matrix-by-matrix multiplications algorithm
$\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}=\begin{bmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\end{bmatrix}$
by
$\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}\begin{bmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{bmatrix}=\Bigl\lfloor\begin{bmatrix}
(A_{11}+\epsilon A_{12})(B_{11}+1/{\epsilon}B_{21})&(A_{11}+\epsilon
A_{12})(B_{12}+1/{\epsilon}B_{22})\\(A_{21}+\epsilon
A_{22})(B_{11}+1/{\epsilon}B_{21})&(A_{21}+\epsilon
A_{22})(B_{12}+1/{\epsilon}B_{22})\end{bmatrix}\Bigr\rfloor \mod
\frac{1}{\epsilon}$. The resulting computational complexity for $N\times N$
matrices can be estimated from recursive equation $T(N)=4(N/2)^2$
(multiplication of a matrix by number)+$4(N/2)^2$ (additions of
matrices)+$2N^2$ (floor and modulo)+$4T(N/2)$ (recursive calls) as
$O(N^2log_2N)$. The novelty of the method lies in the observation, somehow
ignored by other matrix-by-matrix multiplication algorithms, that we can
multiply matrix entries by non-integer numbers to improve computational
complexity. In other words, while having a processor that can compute
multiplications, additions, modulo and floor operations with variable precision
arithmetic in $O(1)$, we can obtain a matrix-by-matrix multiplication algorithm
with $O(N^2log_2N)$ computational complexity. We also present a MATLAB code
using VPA variable precision arithmetic emulator that can multiply matrices of
size $N\times N$ using $(4log_2N+1)N^2$ variable precision arithmetic
operations. This emulator uses $O(N)$ digits to run our algorithm.
Authors: Holger Dell, Anselm Haak, Melvin Kallmayer, Leo Wennmann
We present a randomized algorithm for solving low-degree polynomial equation
systems over finite fields faster than exhaustive search. In order to do so, we
follow a line of work by Lokshtanov, Paturi, Tamaki, Williams, and Yu (SODA
2017), Bj\"orklund, Kaski, and Williams (ICALP 2019), and Dinur (SODA 2021). In
particular, we generalize Dinur's algorithm for $\mathbb{F}_2$ to all finite
fields, in particular the "symbolic interpolation" of Bj\"orklund, Kaski, and
Williams, and we use an efficient trimmed multipoint evaluation and
interpolation procedure for multivariate polynomials over finite fields by Van
der Hoeven and Schost (AAECC 2013). The running time of our algorithm matches
that of Dinur's algorithm for $\mathbb{F}_2$ and is significantly faster than
the one of Lokshtanov et al. for $q>2$.
We complement our results with tight conditional lower bounds that,
surprisingly, we were not able to find in the literature. In particular, under
the strong exponential time hypothesis, we prove that it is impossible to solve
$n$-variate low-degree polynomial equation systems over $\mathbb{F}_q$ in time
$O((q-\varepsilon)^{n})$. As a bonus, we show that under the counting version
of the strong exponential time hypothesis, it is impossible to compute the
number of roots of a single $n$-variate low-degree polynomial over
$\mathbb{F}_q$ in time ${O((q-\varepsilon)^{n})}$; this generalizes a result of
Williams (SOSA 2018) from $\mathbb{F}_2$ to all finite fields.
We present a randomized algorithm for solving low-degree polynomial equation
systems over finite fields faster than exhaustive search. In order to do so, we
follow a line of work by Lokshtanov, Paturi, Tamaki, Williams, and Yu (SODA
2017), Bj\"orklund, Kaski, and Williams (ICALP 2019), and Dinur (SODA 2021). In
particular, we generalize Dinur's algorithm for $\mathbb{F}_2$ to all finite
fields, in particular the "symbolic interpolation" of Bj\"orklund, Kaski, and
Williams, and we use an efficient trimmed multipoint evaluation and
interpolation procedure for multivariate polynomials over finite fields by Van
der Hoeven and Schost (AAECC 2013). The running time of our algorithm matches
that of Dinur's algorithm for $\mathbb{F}_2$ and is significantly faster than
the one of Lokshtanov et al. for $q>2$.
We complement our results with tight conditional lower bounds that,
surprisingly, we were not able to find in the literature. In particular, under
the strong exponential time hypothesis, we prove that it is impossible to solve
$n$-variate low-degree polynomial equation systems over $\mathbb{F}_q$ in time
$O((q-\varepsilon)^{n})$. As a bonus, we show that under the counting version
of the strong exponential time hypothesis, it is impossible to compute the
number of roots of a single $n$-variate low-degree polynomial over
$\mathbb{F}_q$ in time ${O((q-\varepsilon)^{n})}$; this generalizes a result of
Williams (SOSA 2018) from $\mathbb{F}_2$ to all finite fields.
Online paging is a fundamental problem in the field of online algorithms, in
which one maintains a cache of $k$ slots as requests for fetching pages arrive
online. In the weighted variant of this problem, each page has its own fetching
cost; a substantial line of work on this problem culminated in an (optimal)
$O(\log k)$-competitive randomized algorithm, due to Bansal, Buchbinder and
Naor (FOCS'07).
Existing work for weighted paging assumes that page weights are known in
advance, which is not always the case in practice. For example, in multi-level
caching architectures, the expected cost of fetching a memory block is a
function of its probability of being in a mid-level cache rather than the main
memory. This complex property cannot be predicted in advance; over time,
however, one may glean information about page weights through sampling their
fetching cost multiple times.
We present the first algorithm for online weighted paging that does not know
page weights in advance, but rather learns from weight samples. In terms of
techniques, this requires providing (integral) samples to a fractional solver,
requiring a delicate interface between this solver and the randomized rounding
scheme; we believe that our work can inspire online algorithms to other
problems that involve cost sampling.
Online paging is a fundamental problem in the field of online algorithms, in
which one maintains a cache of $k$ slots as requests for fetching pages arrive
online. In the weighted variant of this problem, each page has its own fetching
cost; a substantial line of work on this problem culminated in an (optimal)
$O(\log k)$-competitive randomized algorithm, due to Bansal, Buchbinder and
Naor (FOCS'07).
Existing work for weighted paging assumes that page weights are known in
advance, which is not always the case in practice. For example, in multi-level
caching architectures, the expected cost of fetching a memory block is a
function of its probability of being in a mid-level cache rather than the main
memory. This complex property cannot be predicted in advance; over time,
however, one may glean information about page weights through sampling their
fetching cost multiple times.
We present the first algorithm for online weighted paging that does not know
page weights in advance, but rather learns from weight samples. In terms of
techniques, this requires providing (integral) samples to a fractional solver,
requiring a delicate interface between this solver and the randomized rounding
scheme; we believe that our work can inspire online algorithms to other
problems that involve cost sampling.
Authors: Owais Aijaz, Syed Muhammad Ali, Yousuf Uyghur
Seam carving, a content-aware image resizing technique, has garnered
significant attention for its ability to resize images while preserving
important content. In this paper, we conduct a comprehensive analysis of four
algorithmic design techniques for seam carving: brute-force, greedy, dynamic
programming, and GPU-based parallel algorithms. We begin by presenting a
theoretical overview of each technique, discussing their underlying principles
and computational complexities. Subsequently, we delve into empirical
evaluations, comparing the performance of these algorithms in terms of runtime
efficiency. Our experimental results provide insights into the theoretical
complexities of the design techniques.
Seam carving, a content-aware image resizing technique, has garnered
significant attention for its ability to resize images while preserving
important content. In this paper, we conduct a comprehensive analysis of four
algorithmic design techniques for seam carving: brute-force, greedy, dynamic
programming, and GPU-based parallel algorithms. We begin by presenting a
theoretical overview of each technique, discussing their underlying principles
and computational complexities. Subsequently, we delve into empirical
evaluations, comparing the performance of these algorithms in terms of runtime
efficiency. Our experimental results provide insights into the theoretical
complexities of the design techniques.
Authors: Ilias Diakonikolas, Samuel B. Hopkins, Ankit Pensia, Stefan Tiegel
We prove that there is a universal constant $C>0$ so that for every $d \in
\mathbb N$, every centered subgaussian distribution $\mathcal D$ on $\mathbb
R^d$, and every even $p \in \mathbb N$, the $d$-variate polynomial $(Cp)^{p/2}
\cdot \|v\|_{2}^p - \mathbb E_{X \sim \mathcal D} \langle v,X\rangle^p$ is a
sum of square polynomials. This establishes that every subgaussian distribution
is \emph{SoS-certifiably subgaussian} -- a condition that yields efficient
learning algorithms for a wide variety of high-dimensional statistical tasks.
As a direct corollary, we obtain computationally efficient algorithms with
near-optimal guarantees for the following tasks, when given samples from an
arbitrary subgaussian distribution: robust mean estimation, list-decodable mean
estimation, clustering mean-separated mixture models, robust covariance-aware
mean estimation, robust covariance estimation, and robust linear regression.
Our proof makes essential use of Talagrand's generic chaining/majorizing
measures theorem.
We prove that there is a universal constant $C>0$ so that for every $d \in
\mathbb N$, every centered subgaussian distribution $\mathcal D$ on $\mathbb
R^d$, and every even $p \in \mathbb N$, the $d$-variate polynomial $(Cp)^{p/2}
\cdot \|v\|_{2}^p - \mathbb E_{X \sim \mathcal D} \langle v,X\rangle^p$ is a
sum of square polynomials. This establishes that every subgaussian distribution
is \emph{SoS-certifiably subgaussian} -- a condition that yields efficient
learning algorithms for a wide variety of high-dimensional statistical tasks.
As a direct corollary, we obtain computationally efficient algorithms with
near-optimal guarantees for the following tasks, when given samples from an
arbitrary subgaussian distribution: robust mean estimation, list-decodable mean
estimation, clustering mean-separated mixture models, robust covariance-aware
mean estimation, robust covariance estimation, and robust linear regression.
Our proof makes essential use of Talagrand's generic chaining/majorizing
measures theorem.
Authors: Nick Fischer, Bernhard Haeupler, Rustam Latypov, Antti Roeyskoe, Aurelio L. Sulser
We give the first parallel algorithm with optimal $\tilde{O}(m)$ work for the
classical problem of computing Single-Source Shortest Paths in general graphs
with negative-weight edges.
In graphs without negative edges, Dijkstra's algorithm solves the
Single-Source Shortest Paths (SSSP) problem with optimal $\tilde O(m)$ work,
but is inherently sequential. A recent breakthrough by Bernstein, Nanongkai,
Wulff-Nilsen; FOCS '22 achieves the same for general graphs. Parallel shortest
path algorithms are more difficult and have been intensely studied for decades.
Only very recently, multiple lines of research culminated in parallel
algorithms with optimal work $\tilde O(m)$ for various restricted settings,
such as approximate or exact algorithms for directed or undirected graphs
without negative edges. For general graphs, the best known algorithm by
[shvinkumar, Bernstein, Cao, Grunau, Haeupler, Jiang, Nanongkai, Su; ESA '24
still requires $m^{1+o(1)}$ work.
This paper presents a randomized parallel algorithm for SSSP in general
graphs with near-linear work $\tilde O(m)$ and state-of-the-art span $n^{1/2 +
o(1)}$. We follow a novel bottom-up approach leading to a particularly clean
and simple algorithm. Our algorithm can be seen as a \emph{near-optimal
parallel black-box reduction} from SSSP in general graphs to graphs without
negative edges. In contrast to prior works, the reduction in this paper is both
parallel and essentially without overhead, only affecting work and span by
polylogarithmic factors.
We give the first parallel algorithm with optimal $\tilde{O}(m)$ work for the
classical problem of computing Single-Source Shortest Paths in general graphs
with negative-weight edges.
In graphs without negative edges, Dijkstra's algorithm solves the
Single-Source Shortest Paths (SSSP) problem with optimal $\tilde O(m)$ work,
but is inherently sequential. A recent breakthrough by Bernstein, Nanongkai,
Wulff-Nilsen; FOCS '22 achieves the same for general graphs. Parallel shortest
path algorithms are more difficult and have been intensely studied for decades.
Only very recently, multiple lines of research culminated in parallel
algorithms with optimal work $\tilde O(m)$ for various restricted settings,
such as approximate or exact algorithms for directed or undirected graphs
without negative edges. For general graphs, the best known algorithm by
[shvinkumar, Bernstein, Cao, Grunau, Haeupler, Jiang, Nanongkai, Su; ESA '24
still requires $m^{1+o(1)}$ work.
This paper presents a randomized parallel algorithm for SSSP in general
graphs with near-linear work $\tilde O(m)$ and state-of-the-art span $n^{1/2 +
o(1)}$. We follow a novel bottom-up approach leading to a particularly clean
and simple algorithm. Our algorithm can be seen as a \emph{near-optimal
parallel black-box reduction} from SSSP in general graphs to graphs without
negative edges. In contrast to prior works, the reduction in this paper is both
parallel and essentially without overhead, only affecting work and span by
polylogarithmic factors.
Authors: Njagi Mwaniki, Erik Garrison, Nadia Pisanti
In this paper, we introduce flubbles, a new definition of "bubbles"
corresponding to variants in a (pan)genome graph $G$. We then show a
characterization for flubbles in terms of equivalence classes regarding cycles
in an intermediate data structure we built from the spanning tree of the $G$,
which leads us to a linear time and space solution for finding all flubbles.
Furthermore, we show how a related characterization also allows us to
efficiently detect what we define as hairpin inversions: a cycle preceded and
followed by the same path in the graph; being the latter necessarily traversed
both ways, this structure corresponds to inversions. Finally, Inspired by the
concept of Program Structure Tree introduced fifty years ago to represent the
hierarchy of the control structure of a program, we define a tree representing
the structure of G in terms of flubbles, the flubble tree, which we also find
in linear time. The hierarchy of variants introduced by the flubble tree paves
the way for new investigations of (pan)genomic structures and their
decomposition for practical analyses. We have implemented our methods into a
prototype tool named povu which we tested on human and yeast data. We show that
povu can find flubbles and also output the flubble tree while being as fast (or
faster than) well established tools that find bubbles, such as vg and
BubbleGun. Moreover, we show how, within the same time, povu can find hairpin
inversions that, to the best of our knowledge, no other tool is able to find.
Our tool is freely available at github.com/urbanslug/povu/ under the
MIT License.
In this paper, we introduce flubbles, a new definition of "bubbles"
corresponding to variants in a (pan)genome graph $G$. We then show a
characterization for flubbles in terms of equivalence classes regarding cycles
in an intermediate data structure we built from the spanning tree of the $G$,
which leads us to a linear time and space solution for finding all flubbles.
Furthermore, we show how a related characterization also allows us to
efficiently detect what we define as hairpin inversions: a cycle preceded and
followed by the same path in the graph; being the latter necessarily traversed
both ways, this structure corresponds to inversions. Finally, Inspired by the
concept of Program Structure Tree introduced fifty years ago to represent the
hierarchy of the control structure of a program, we define a tree representing
the structure of G in terms of flubbles, the flubble tree, which we also find
in linear time. The hierarchy of variants introduced by the flubble tree paves
the way for new investigations of (pan)genomic structures and their
decomposition for practical analyses. We have implemented our methods into a
prototype tool named povu which we tested on human and yeast data. We show that
povu can find flubbles and also output the flubble tree while being as fast (or
faster than) well established tools that find bubbles, such as vg and
BubbleGun. Moreover, we show how, within the same time, povu can find hairpin
inversions that, to the best of our knowledge, no other tool is able to find.
Our tool is freely available at https://github.com/urbanslug/povu/ under the
MIT License.
Authors: Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh, Vaishali Surianarayanan, Jie Xue
The \textsc{Capacitated $d$-Hitting Set} problem involves a universe $U$ with
a capacity function $\mathsf{cap}: U \rightarrow \mathbb{N}$ and a collection
$\mathcal{A}$ of subsets of $U$, each of size at most $d$. The goal is to find
a minimum subset $S \subseteq U$ and an assignment $\phi : \mathcal{A}
\rightarrow S$ such that for every $A \in \mathcal{A}$, $\phi(A) \in A$, and
for each $x \in U$, $|\phi^{-1}(x)| \leq \mathsf{cap}(x)$. For $d=2$, this is
known as \textsc{Capacitated Vertex Cover}. In the weighted variant, each
element of $U$ has a positive integer weight, with the objective of finding a
minimum-weight capacitated hitting set.
Chuzhoy and Naor [SICOMP 2006] provided a factor-3 approximation for
\textsc{Capacitated Vertex Cover} and showed that the weighted case lacks an
$o(\log n)$-approximation unless $P=NP$. Kao and Wong [SODA 2017] later
independently achieved a $d$-approximation for \textsc{Capacitated $d$-Hitting
Set}, with no $d - \epsilon$ improvements possible under the Unique Games
Conjecture. Our main result is a parameterized approximation algorithm with
runtime $\left(\frac{k}{\epsilon}\right)^k
2^{k^{O(kd)}}(|U|+|\mathcal{A}|)^{O(1)}$ that either concludes no solution of
size $\leq k$ exists or finds $S$ of size $\leq 4/3 \cdot k$ and weight at most
$2+\epsilon$ times the minimum weight for solutions of size $\leq k$. We
further show that no FPT-approximation with factor $c > 1$ exists for
unweighted \textsc{Capacitated $d$-Hitting Set} with $d \geq 3$, nor with
factor $2 - \epsilon$ for the weighted version, assuming the Exponential Time
Hypothesis. These results extend to \textsc{Capacitated Vertex Cover} in
multigraphs. Additionally, a variant of multi-dimensional \textsc{Knapsack} is
shown hard to FPT-approximate within $2 - \epsilon$.
The \textsc{Capacitated $d$-Hitting Set} problem involves a universe $U$ with
a capacity function $\mathsf{cap}: U \rightarrow \mathbb{N}$ and a collection
$\mathcal{A}$ of subsets of $U$, each of size at most $d$. The goal is to find
a minimum subset $S \subseteq U$ and an assignment $\phi : \mathcal{A}
\rightarrow S$ such that for every $A \in \mathcal{A}$, $\phi(A) \in A$, and
for each $x \in U$, $|\phi^{-1}(x)| \leq \mathsf{cap}(x)$. For $d=2$, this is
known as \textsc{Capacitated Vertex Cover}. In the weighted variant, each
element of $U$ has a positive integer weight, with the objective of finding a
minimum-weight capacitated hitting set.
Chuzhoy and Naor [SICOMP 2006] provided a factor-3 approximation for
\textsc{Capacitated Vertex Cover} and showed that the weighted case lacks an
$o(\log n)$-approximation unless $P=NP$. Kao and Wong [SODA 2017] later
independently achieved a $d$-approximation for \textsc{Capacitated $d$-Hitting
Set}, with no $d - \epsilon$ improvements possible under the Unique Games
Conjecture. Our main result is a parameterized approximation algorithm with
runtime $\left(\frac{k}{\epsilon}\right)^k
2^{k^{O(kd)}}(|U|+|\mathcal{A}|)^{O(1)}$ that either concludes no solution of
size $\leq k$ exists or finds $S$ of size $\leq 4/3 \cdot k$ and weight at most
$2+\epsilon$ times the minimum weight for solutions of size $\leq k$. We
further show that no FPT-approximation with factor $c > 1$ exists for
unweighted \textsc{Capacitated $d$-Hitting Set} with $d \geq 3$, nor with
factor $2 - \epsilon$ for the weighted version, assuming the Exponential Time
Hypothesis. These results extend to \textsc{Capacitated Vertex Cover} in
multigraphs. Additionally, a variant of multi-dimensional \textsc{Knapsack} is
shown hard to FPT-approximate within $2 - \epsilon$.
Authors: John Augustine, Fabien Dufoulon, Gopal Pandurangan
Byzantine agreement is a fundamental problem in fault-tolerant distributed
networks that has been studied intensively for the last four decades. Most of
these works designed protocols for complete networks. A key goal in Byzantine
protocols is to tolerate as many Byzantine nodes as possible.
The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was
the first to address the Byzantine agreement problem in sparse, bounded degree
networks and presented a protocol that achieved almost-everywhere agreement
among honest nodes. In such networks, all known Byzantine agreement protocols
(e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King,
Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine
nodes had a major drawback that they were not fully-distributed -- in those
protocols, nodes are required to have initial knowledge of the entire network
topology. This drawback makes such protocols inapplicable to real-world
communication networks such as peer-to-peer (P2P) networks, which are typically
sparse and bounded degree and where nodes initially have only local knowledge
of themselves and their neighbors. Indeed, a fundamental open question raised
by the above works is whether one can design Byzantine protocols that tolerate
a large number of Byzantine nodes in sparse networks that work with only local
knowledge, i.e., fully-distributed protocols. The work of Augustine,
Pandurangan, and Robinson [PODC 2013] presented the first fully-distributed
Byzantine agreement protocol that works in sparse networks, but it tolerated
only up to $O(\sqrt{n}/ polylog(n))$ Byzantine nodes (where $n$ is the total
network size).
We answer the earlier open question by presenting fully-distributed Byzantine
agreement protocols for sparse, bounded degree networks that tolerate
significantly more Byzantine nodes -- up to $O(n/ polylog(n))$ of them.
Byzantine agreement is a fundamental problem in fault-tolerant distributed
networks that has been studied intensively for the last four decades. Most of
these works designed protocols for complete networks. A key goal in Byzantine
protocols is to tolerate as many Byzantine nodes as possible.
The work of Dwork, Peleg, Pippenger, and Upfal [STOC 1986, SICOMP 1988] was
the first to address the Byzantine agreement problem in sparse, bounded degree
networks and presented a protocol that achieved almost-everywhere agreement
among honest nodes. In such networks, all known Byzantine agreement protocols
(e.g., Dwork, Peleg, Pippenger, and Upfal, STOC 1986; Upfal, PODC 1992; King,
Saia, Sanwalani, and Vee, FOCS 2006) that tolerated a large number of Byzantine
nodes had a major drawback that they were not fully-distributed -- in those
protocols, nodes are required to have initial knowledge of the entire network
topology. This drawback makes such protocols inapplicable to real-world
communication networks such as peer-to-peer (P2P) networks, which are typically
sparse and bounded degree and where nodes initially have only local knowledge
of themselves and their neighbors. Indeed, a fundamental open question raised
by the above works is whether one can design Byzantine protocols that tolerate
a large number of Byzantine nodes in sparse networks that work with only local
knowledge, i.e., fully-distributed protocols. The work of Augustine,
Pandurangan, and Robinson [PODC 2013] presented the first fully-distributed
Byzantine agreement protocol that works in sparse networks, but it tolerated
only up to $O(\sqrt{n}/ polylog(n))$ Byzantine nodes (where $n$ is the total
network size).
We answer the earlier open question by presenting fully-distributed Byzantine
agreement protocols for sparse, bounded degree networks that tolerate
significantly more Byzantine nodes -- up to $O(n/ polylog(n))$ of them.
The 3SUM problem is one of the cornerstones of fine-grained complexity. Its
study has led to countless lower bounds, but as has been sporadically observed
before -- and as we will demonstrate again -- insights on 3SUM can also lead to
algorithmic applications.
The starting point of our work is that we spend a lot of technical effort to
develop new algorithms for 3SUM-type problems such as approximate
3SUM-counting, small-doubling 3SUM-counting, and a deterministic
subquadratic-time algorithm for the celebrated Balog-Szemer\'edi-Gowers theorem
from additive combinatorics. As consequences of these tools, we derive diverse
new results in fine-grained complexity and pattern matching algorithms,
answering open questions from many unrelated research areas. Specifically:
- A recent line of research on the "short cycle removal" technique culminated
in tight 3SUM-based lower bounds for various graph problems via randomized
fine-grained reductions [Abboud, Bringmann, Fischer; STOC '23] [Jin, Xu; STOC
'23]. In this paper we derandomize the reduction to the important 4-Cycle
Listing problem.
- We establish that \#3SUM and 3SUM are fine-grained equivalent under
deterministic reductions.
- We give a deterministic algorithm for the $(1+\epsilon)$-approximate
Text-to-Pattern Hamming Distances problem in time $n^{1+o(1)} \cdot
\epsilon^{-1}$.
- In the $k$-Mismatch Constellation problem the input consists of two integer
sets $A, B \subseteq [N]$, and the goal is to test whether there is a shift $c$
such that $|(c + B) \setminus A| \leq k$ (i.e., whether $B$ shifted by $c$
matches $A$ up to $k$ mismatches). For moderately small $k$ the previously best
running time was $\tilde O(|A| \cdot k)$ [Cardoze, Schulman; FOCS '98]
[Fischer; SODA '24]. We give a faster $|A| \cdot k^{2/3} \cdot N^{o(1)}$-time
algorithm in the regime where $|B| = \Theta(|A|)$.
The 3SUM problem is one of the cornerstones of fine-grained complexity. Its
study has led to countless lower bounds, but as has been sporadically observed
before -- and as we will demonstrate again -- insights on 3SUM can also lead to
algorithmic applications.
The starting point of our work is that we spend a lot of technical effort to
develop new algorithms for 3SUM-type problems such as approximate
3SUM-counting, small-doubling 3SUM-counting, and a deterministic
subquadratic-time algorithm for the celebrated Balog-Szemer\'edi-Gowers theorem
from additive combinatorics. As consequences of these tools, we derive diverse
new results in fine-grained complexity and pattern matching algorithms,
answering open questions from many unrelated research areas. Specifically:
- A recent line of research on the "short cycle removal" technique culminated
in tight 3SUM-based lower bounds for various graph problems via randomized
fine-grained reductions [Abboud, Bringmann, Fischer; STOC '23] [Jin, Xu; STOC
'23]. In this paper we derandomize the reduction to the important 4-Cycle
Listing problem.
- We establish that \#3SUM and 3SUM are fine-grained equivalent under
deterministic reductions.
- We give a deterministic algorithm for the $(1+\epsilon)$-approximate
Text-to-Pattern Hamming Distances problem in time $n^{1+o(1)} \cdot
\epsilon^{-1}$.
- In the $k$-Mismatch Constellation problem the input consists of two integer
sets $A, B \subseteq [N]$, and the goal is to test whether there is a shift $c$
such that $|(c + B) \setminus A| \leq k$ (i.e., whether $B$ shifted by $c$
matches $A$ up to $k$ mismatches). For moderately small $k$ the previously best
running time was $\tilde O(|A| \cdot k)$ [Cardoze, Schulman; FOCS '98]
[Fischer; SODA '24]. We give a faster $|A| \cdot k^{2/3} \cdot N^{o(1)}$-time
algorithm in the regime where $|B| = \Theta(|A|)$.
The classic greedy coloring (first-fit) algorithm considers the vertices of
an input graph $G$ in a given order and assigns the first available color to
each vertex $v$ in $G$. In the {\sc Grundy Coloring} problem, the task is to
find an ordering of the vertices that will force the greedy algorithm to use as
many colors as possible. In the {\sc Partial Grundy Coloring}, the task is also
to color the graph using as many colors as possible. This time, however, we may
select both the ordering in which the vertices are considered and which color
to assign the vertex. The only constraint is that the color assigned to a
vertex $v$ is a color previously used for another vertex if such a color is
available.
Whether {\sc Grundy Coloring} and {\sc Partial Grundy Coloring} admit
fixed-parameter tractable (FPT) algorithms, algorithms with running time
$f(k)n^{\OO(1)}$, where $k$ is the number of colors, was posed as an open
problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et
al. (STACS 2020 and Algorithmica 2022) resolved the question for \Grundycol\ in
the negative by showing that the problem is W[1]-hard. For {\sc Partial Grundy
Coloring}, they obtain an FPT algorithm on graphs that do not contain $K_{i,j}$
as a subgraph (a.k.a. $K_{i,j}$-free graphs). Aboulker et al.~re-iterate the
question of whether there exists an FPT algorithm for {\sc Partial Grundy
Coloring} on general graphs and also asks whether {\sc Grundy Coloring} admits
an FPT algorithm on $K_{i,j}$-free graphs. We give FPT algorithms for {\sc
Partial Grundy Coloring} on general graphs and for {\sc Grundy Coloring} on
$K_{i,j}$-free graphs, resolving both the questions in the affirmative. We
believe that our new structural theorems for partial Grundy coloring and
``representative-family'' like sets for $K_{i,j}$-free graphs that we use in
obtaining our results may have wider algorithmic applications.
The classic greedy coloring (first-fit) algorithm considers the vertices of
an input graph $G$ in a given order and assigns the first available color to
each vertex $v$ in $G$. In the {\sc Grundy Coloring} problem, the task is to
find an ordering of the vertices that will force the greedy algorithm to use as
many colors as possible. In the {\sc Partial Grundy Coloring}, the task is also
to color the graph using as many colors as possible. This time, however, we may
select both the ordering in which the vertices are considered and which color
to assign the vertex. The only constraint is that the color assigned to a
vertex $v$ is a color previously used for another vertex if such a color is
available.
Whether {\sc Grundy Coloring} and {\sc Partial Grundy Coloring} admit
fixed-parameter tractable (FPT) algorithms, algorithms with running time
$f(k)n^{\OO(1)}$, where $k$ is the number of colors, was posed as an open
problem by Zaker and by Effantin et al., respectively. Recently, Aboulker et
al. (STACS 2020 and Algorithmica 2022) resolved the question for \Grundycol\ in
the negative by showing that the problem is W[1]-hard. For {\sc Partial Grundy
Coloring}, they obtain an FPT algorithm on graphs that do not contain $K_{i,j}$
as a subgraph (a.k.a. $K_{i,j}$-free graphs). Aboulker et al.~re-iterate the
question of whether there exists an FPT algorithm for {\sc Partial Grundy
Coloring} on general graphs and also asks whether {\sc Grundy Coloring} admits
an FPT algorithm on $K_{i,j}$-free graphs. We give FPT algorithms for {\sc
Partial Grundy Coloring} on general graphs and for {\sc Grundy Coloring} on
$K_{i,j}$-free graphs, resolving both the questions in the affirmative. We
believe that our new structural theorems for partial Grundy coloring and
``representative-family'' like sets for $K_{i,j}$-free graphs that we use in
obtaining our results may have wider algorithmic applications.
Authors: David Dekker, Carl Henrik Häll, Anders Peterson, Christiane Schmidt
A seemingly simple, yet widely applicable subroutine in automated train
scheduling is the insertion of a new train path to a timetable in a railway
network. We believe it to be the first step towards a new train-rerouting
framework in case of large disturbances or maintenance works. Other
applications include handling ad-hoc requests and modifying train paths upon
request from railway undertakings. We propose a fast and scalable
path-insertion algorithm based on dynamic programming that is able to output
multiple suitable paths. Our algorithm uses macroscopic data and can run on
railway networks with any number of tracks. We apply the algorithm on the line
from G\"oteborg S\"aven\"as to the Norwegian border at Kornsj\"o. For a time
window of seven hours, we obtain eight suitable paths for a freight train
within 0.3 seconds after preprocessing.
A seemingly simple, yet widely applicable subroutine in automated train
scheduling is the insertion of a new train path to a timetable in a railway
network. We believe it to be the first step towards a new train-rerouting
framework in case of large disturbances or maintenance works. Other
applications include handling ad-hoc requests and modifying train paths upon
request from railway undertakings. We propose a fast and scalable
path-insertion algorithm based on dynamic programming that is able to output
multiple suitable paths. Our algorithm uses macroscopic data and can run on
railway networks with any number of tracks. We apply the algorithm on the line
from G\"oteborg S\"aven\"as to the Norwegian border at Kornsj\"o. For a time
window of seven hours, we obtain eight suitable paths for a freight train
within 0.3 seconds after preprocessing.
We consider algorithms and spectral bounds for sparsest cut and conductance
in directed polymatrodal networks. This is motivated by recent work on
submodular hypergraphs \cite{Yoshida19,LiM18,ChenOT23,Veldt23} and previous
work on multicommodity flows and cuts in polymatrodial networks
\cite{ChekuriKRV15}. We obtain three results. First, we obtain an $O(\sqrt{\log
n})$-approximation for sparsest cut and point out how this generalizes the
result in \cite{ChenOT23}. Second, we consider the symmetric version of
conductance and obtain an $O(\sqrt{OPT \log r})$ approximation where $r$ is the
maximum degree and we point out how this generalizes previous work on vertex
expansion in graphs. Third, we prove a non-constructive Cheeger like inequality
that generalizes previous work on hypergraphs. We provide a unified treatment
via line-embeddings which were shown to be effective for submodular cuts in
\cite{ChekuriKRV15}.
We consider algorithms and spectral bounds for sparsest cut and conductance
in directed polymatrodal networks. This is motivated by recent work on
submodular hypergraphs \cite{Yoshida19,LiM18,ChenOT23,Veldt23} and previous
work on multicommodity flows and cuts in polymatrodial networks
\cite{ChekuriKRV15}. We obtain three results. First, we obtain an $O(\sqrt{\log
n})$-approximation for sparsest cut and point out how this generalizes the
result in \cite{ChenOT23}. Second, we consider the symmetric version of
conductance and obtain an $O(\sqrt{OPT \log r})$ approximation where $r$ is the
maximum degree and we point out how this generalizes previous work on vertex
expansion in graphs. Third, we prove a non-constructive Cheeger like inequality
that generalizes previous work on hypergraphs. We provide a unified treatment
via line-embeddings which were shown to be effective for submodular cuts in
\cite{ChekuriKRV15}.
A reachability preserver is a basic kind of graph sparsifier, which preserves
the reachability relation of an $n$-node directed input graph $G$ among a set
of given demand pairs $P$ of size $|P|=p$. We give constructions of sparse
reachability preservers in the online setting, where $G$ is given on input, the
demand pairs $(s, t) \in P$ arrive one at a time, and we must irrevocably add
edges to a preserver $H$ to ensure reachability for the pair $(s, t)$ before we
can see the next demand pair. Our main results are:
-- There is a construction that guarantees a maximum preserver size of
$$|E(H)| \le O\left( n^{0.72}p^{0.56} + n^{0.6}p^{0.7} + n\right).$$ This
improves polynomially on the previous online upper bound of $O( \min\{np^{0.5},
n^{0.5}p\}) + n$, implicit in the work of Coppersmith and Elkin [SODA '05].
-- Given a promise that the demand pairs will satisfy $P \subseteq S \times
V$ for some vertex set $S$ of size $|S|=:\sigma$, there is a construction that
guarantees a maximum preserver size of $$|E(H)| \le O\left( (np\sigma)^{1/2} +
n\right).$$ A slightly different construction gives the same result for the
setting $P \subseteq V \times S$. This improves polynomially on the previous
online upper bound of $O( \sigma n)$ (folklore).
All of these constructions are polynomial time, deterministic, and they do
not require knowledge of the values of $p, \sigma$, or $S$. Our techniques also
give a small polynomial improvement in the current upper bounds for offline
reachability preservers, and they extend to a stronger model in which we must
commit to a path for all possible reachable pairs in $G$ before any demand
pairs have been received. As an application, we improve the competitive ratio
for Online Unweighted Directed Steiner Forest to $O(n^{3/5 + \varepsilon})$.
A reachability preserver is a basic kind of graph sparsifier, which preserves
the reachability relation of an $n$-node directed input graph $G$ among a set
of given demand pairs $P$ of size $|P|=p$. We give constructions of sparse
reachability preservers in the online setting, where $G$ is given on input, the
demand pairs $(s, t) \in P$ arrive one at a time, and we must irrevocably add
edges to a preserver $H$ to ensure reachability for the pair $(s, t)$ before we
can see the next demand pair. Our main results are:
-- There is a construction that guarantees a maximum preserver size of
$$|E(H)| \le O\left( n^{0.72}p^{0.56} + n^{0.6}p^{0.7} + n\right).$$ This
improves polynomially on the previous online upper bound of $O( \min\{np^{0.5},
n^{0.5}p\}) + n$, implicit in the work of Coppersmith and Elkin [SODA '05].
-- Given a promise that the demand pairs will satisfy $P \subseteq S \times
V$ for some vertex set $S$ of size $|S|=:\sigma$, there is a construction that
guarantees a maximum preserver size of $$|E(H)| \le O\left( (np\sigma)^{1/2} +
n\right).$$ A slightly different construction gives the same result for the
setting $P \subseteq V \times S$. This improves polynomially on the previous
online upper bound of $O( \sigma n)$ (folklore).
All of these constructions are polynomial time, deterministic, and they do
not require knowledge of the values of $p, \sigma$, or $S$. Our techniques also
give a small polynomial improvement in the current upper bounds for offline
reachability preservers, and they extend to a stronger model in which we must
commit to a path for all possible reachable pairs in $G$ before any demand
pairs have been received. As an application, we improve the competitive ratio
for Online Unweighted Directed Steiner Forest to $O(n^{3/5 + \varepsilon})$.
Asymptotically tight lower bounds are derived for the Input/Output (I/O)
complexity of a class of dynamic programming algorithms including matrix chain
multiplication, optimal polygon triangulation, and the construction of optimal
binary search trees. Assuming no recomputation of intermediate values, we
establish an $\Omega\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O lower bound, where
$n$ denotes the size of the input and $M$ denotes the size of the available
fast memory (cache). When recomputation is allowed, we show the same bound
holds for $M < cn$, where $c$ is a positive constant. In the case where $M \ge
2n$, we show an $\Omega\left(n/B\right)$ I/O lower bound. We also discuss
algorithms for which the number of executed I/O operations matches
asymptotically each of the presented lower bounds, which are thus
asymptotically tight.
Additionally, we refine our general method to obtain a lower bound for the
I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the
grammar impacts the I/O complexity. An upper bound with asymptotically matching
performance in many cases is also provided.
Asymptotically tight lower bounds are derived for the Input/Output (I/O)
complexity of a class of dynamic programming algorithms including matrix chain
multiplication, optimal polygon triangulation, and the construction of optimal
binary search trees. Assuming no recomputation of intermediate values, we
establish an $\Omega\left(\frac{n^3}{\sqrt{M}B}\right)$ I/O lower bound, where
$n$ denotes the size of the input and $M$ denotes the size of the available
fast memory (cache). When recomputation is allowed, we show the same bound
holds for $M < cn$, where $c$ is a positive constant. In the case where $M \ge
2n$, we show an $\Omega\left(n/B\right)$ I/O lower bound. We also discuss
algorithms for which the number of executed I/O operations matches
asymptotically each of the presented lower bounds, which are thus
asymptotically tight.
Additionally, we refine our general method to obtain a lower bound for the
I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the
grammar impacts the I/O complexity. An upper bound with asymptotically matching
performance in many cases is also provided.
Authors: Dariusz Dereniowski, Janusz Dybizbański, Przemysław Karpiński, Michał Zakrzewski, Paweł Żyliński
We present a simple linear-time algorithm that finds a spanning tree $T$ of a
given $2$-edge-connected graph $G$ such that each vertex $v$ of $T$ has degree
at most $\lceil \frac{\deg_G(v)}{2}\rceil + 1$.
We present a simple linear-time algorithm that finds a spanning tree $T$ of a
given $2$-edge-connected graph $G$ such that each vertex $v$ of $T$ has degree
at most $\lceil \frac{\deg_G(v)}{2}\rceil + 1$.
I’ve posted quite a bit about the binary tiling of the hyperbolic plane recently, including what you get when you shrink its vertical edges, a related “nowhere-neat” tessellation, the connection to Smith charts and Escher, a method to 3-color its tiles, a half-flipped variation of the tiling, and its applications in proving that folding origami is hard. But I thought there might be room for one more post, in honor of the Wikipedia binary tiling article’s new Good Article Status. This one is about something I wanted to include in the Wikipedia article, but couldn’t, because I couldn’t find published sources describing it: a way of numbering tiles that encodes their position in a tiling and instantly proves the assertion in the article that there are uncountably many binary tilings.
The basic idea is very simple: in the binary tiling (in its conventional view as a pattern of similar squares or rectangles in the Poincaré half-plane), if you look directly upward from any tile, some of the tiles above it will extend farther to the left, and some of them will extend farther to the right. We will encode this by a binary sequence, where a 1 encodes a tile that extends to the left, and a 0 encodes a tile that extends to the right. (This seems backwards, but there’s a reason for this choice that will become clear soon.) To make it backwards in a different way, I want to write this sequence in right-to-left order, so that for instance the encoding …1100 means that the closest two tiles above it extend to the right, and the next two extend to the left. Here’s a picture with some examples. The label in each square only encodes the tiles that you can see in the picture, but the tiling itself can continue above these squares in multiple different ways, resulting in different continuations of these labels.
If you read the binary sequences in a single row, left-to-right, they should look familiar: they’re just the binary encodings of the non-negative integers 0, 1, 2, 3, … in order. That’s why I chose the backwards order of binary digits and backwards choice of what 0 and 1 mean: with the digits in the other order we would get the bit-reversal permutation of these numbers and with the other choice of what 0 and 1 mean they would count down rather than counting up.
The binary representation of an ordinary integer eventually terminates, with all higher-order binary digits equal to zero for a non-negative integer (or equal to one for a two’s-complement negative integer). But the binary sequences coming from a binary tiling might not terminate in this way. Any binary sequence is possible, and uniquely determines the entire tiling surrounding a tile with that sequence as its label. To find the tiling from a binary sequence, just place tiles directly above the labeled tile, as the sequence dictates, and then fill in everything else below them in the only way possible. There are uncountably many binary sequences (for instance, each two real numbers in the unit interval have different binary expansions), but only countably many of them can show up as the labels in a single binary tiling. For this reason we know that there are uncountably many different binary tilings.
But because we’re ordering the binary sequences right-to-left, they’re not the binary expansions of real numbers. And because they aren’t eventually zero, they’re not the binary expansions of ordinary integers. Instead, they’re the binary expansions of a more exotic number system, the 2-adic integers. You can think of the arithmetic of these numbers as just like ordinary binary arithmetic except that it continues infinitely to the left, in the same way that ordinary binary arithmetic on real numbers continues infinitely to the right.
The 2-adic integers contain the ordinary integers (sometimes called in this context rational integers) but they also contain any rational number whose denominator is odd. These can be recognized as the 2-adic numbers whose binary expansion is eventually repeating. More precisely, when a 2-adic number has a repeating pattern of length \(i\) that repeats the binary expansion of the integer \(n\), it can be thought of as equal to the rational number \(-n/(2^i-1)\). As an example that is eventually repeating but not purely repeating, the rational number \(\tfrac13\) is a 2-adic integer with a binary expansion …0101011 that, after the rightmost 1, repeats with a period-2 pattern. (Try multiplying it by 3 in binary and watch all the nonzero bits get carried away!)
We can encode many convenient properties of the tiling in properties of these numbers:
Two tiles of the same tiling have a non-reflective symmetry of the tiling that takes one to the other, if and only if they are labeled by the same 2-adic integer.
The image of a tile labeled \(x\), in the reflection of the tiling, has the label \(-x-1\), the 2-adic integer with all bits flipped.
The left neighbor of a tile labeled \(x\) is labeled \(x-1\), and the right neighbor is labeled \(x+1\). The two neighbors below a tile labeled \(x\) are labeled \(2x\) and \(2x+1\).
Each 2-adic integer is either odd or even (according to its last binary digit, just like ordinary integers). If a tile is labeled by an even number \(x\), it is on the left side of the tile above it, which is labeled \(x/2\). If a tile is labeled by an odd number \(y\), it is on the right side of the tile above it, which is labeled \((x-1)/2\).
Two labels \(x\) and \(y\) appear together in the same tiling if and only if one of the two labels can be obtained from the other by multiplying by a power of two and then adding a rational integer. This is true if and only if their binary sequences are eventually equal (after removing finite prefixes of possibly different lengths), with one exception: negative and positive rational integer labels do belong to the same tiling, but have binary sequences that are eventually all zero or eventually all one.
A tiling has a one-dimensional group of symmetries, obtained by scaling the Poincaré half-plane drawing by a factor of \(2^i\), if and only if its labels are rational numbers whose binary expansions have period \(i\). For instance the unique tiling for which scaling by 2 is a symmetry is the one where all the labels are rational integers.
Based on this labeling, we can count the number of distinct tilings (counting reflections as distinct) for which scaling by \(2^i\) is a symmetry: they are the number of distinct binary sequences of length \(i\), up to rotations, minus one. The minus one is because of the rational integer labels. For instance, there are two tilings for which multiplication by four (\(i=2\)) is a symmetry, with repeating patterns 00 = 11 (the rational integers) and 01 = 10 (integers \(\pm\tfrac13\)), which is its own mirror reflection. There are three tilings for which multiplication by eight is a symmetry: the rational integers again, and two mirror-image tilings with repeating patterns 001 and 011.
Authors: Prabhanjan Ananth, John Bostanci, Aditya Gulati, Yao-Ting Lin
We study the (in)feasibility of quantum pseudorandom notions in a quantum
analog of the random oracle model, where all the parties, including the
adversary, have oracle access to the same Haar random unitary. In this model,
we show the following:
- (Unbounded-query secure) pseudorandom unitaries (PRU) exist. Moreover, the
PRU construction makes two calls to the Haar oracle.
- We consider constructions of PRUs making a single call to the Haar oracle.
In this setting, we show that unbounded-query security is impossible to
achieve. We complement this result by showing that bounded-query secure PRUs do
exist with a single query to the Haar oracle.
- We show that multi-copy pseudorandom state generators and function-like
state generators (with classical query access), making a single call to the
Haar oracle, exist.
Our results have two consequences: (a) when the Haar random unitary is
instantiated suitably, our results present viable approaches for building
quantum pseudorandom objects without relying upon one-way functions and, (b)
for the first time, we show that the key length in pseudorandom unitaries can
be generically shrunk (relative to the output length). Our results are also
some of the first usecases of the new "path recording" formalism for Haar
random unitaries, introduced in the recent breakthrough work of Ma and Huang.
We study the (in)feasibility of quantum pseudorandom notions in a quantum
analog of the random oracle model, where all the parties, including the
adversary, have oracle access to the same Haar random unitary. In this model,
we show the following:
- (Unbounded-query secure) pseudorandom unitaries (PRU) exist. Moreover, the
PRU construction makes two calls to the Haar oracle.
- We consider constructions of PRUs making a single call to the Haar oracle.
In this setting, we show that unbounded-query security is impossible to
achieve. We complement this result by showing that bounded-query secure PRUs do
exist with a single query to the Haar oracle.
- We show that multi-copy pseudorandom state generators and function-like
state generators (with classical query access), making a single call to the
Haar oracle, exist.
Our results have two consequences: (a) when the Haar random unitary is
instantiated suitably, our results present viable approaches for building
quantum pseudorandom objects without relying upon one-way functions and, (b)
for the first time, we show that the key length in pseudorandom unitaries can
be generically shrunk (relative to the output length). Our results are also
some of the first usecases of the new "path recording" formalism for Haar
random unitaries, introduced in the recent breakthrough work of Ma and Huang.
We find a modification to QMA where having one quantum proof is strictly less
powerful than having two unentangled proofs, assuming EXP $\ne$ NEXP. This
gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of
a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our
modification endows each proof with a form of *multipartite* unentanglement:
after tracing out one register, a small number of qubits are separable from the
rest of the state.
We find a modification to QMA where having one quantum proof is strictly less
powerful than having two unentangled proofs, assuming EXP $\ne$ NEXP. This
gives a new route to prove QMA(2) = NEXP that overcomes the primary drawback of
a recent approach [arXiv:2402.18790 , arXiv:2306.13247] (QIP 2024). Our
modification endows each proof with a form of *multipartite* unentanglement:
after tracing out one register, a small number of qubits are separable from the
rest of the state.
We study the quantum-classical polynomial hierarchy, QCPH, which is the class
of languages solvable by a constant number of alternating classical quantifiers
followed by a quantum verifier. Our main result is that QCPH is infinite
relative to a random oracle (previously, this was not even known relative to
any oracle). We further prove that higher levels of PH are not contained in
lower levels of QCPH relative to a random oracle; this is a strengthening of
the somewhat recent result that PH is infinite relative to a random oracle
(Rossman, Servedio, and Tan 2016).
The oracle separation requires lower bounding a certain type of low-depth
alternating circuit with some quantum gates. To establish this, we give a new
switching lemma for quantum algorithms which may be of independent interest.
Our lemma says that for any $d$, if we apply a random restriction to a function
$f$ with quantum query complexity $\mathrm{Q}(f)\le n^{1/3}$, the restricted
function becomes exponentially close (in terms of $d$) to a depth-$d$ decision
tree. Our switching lemma works even in a "worst-case" sense, in that only the
indices to be restricted are random; the values they are restricted to are
chosen adversarially. Moreover, the switching lemma also works for polynomial
degree in place of quantum query complexity.
We study the quantum-classical polynomial hierarchy, QCPH, which is the class
of languages solvable by a constant number of alternating classical quantifiers
followed by a quantum verifier. Our main result is that QCPH is infinite
relative to a random oracle (previously, this was not even known relative to
any oracle). We further prove that higher levels of PH are not contained in
lower levels of QCPH relative to a random oracle; this is a strengthening of
the somewhat recent result that PH is infinite relative to a random oracle
(Rossman, Servedio, and Tan 2016).
The oracle separation requires lower bounding a certain type of low-depth
alternating circuit with some quantum gates. To establish this, we give a new
switching lemma for quantum algorithms which may be of independent interest.
Our lemma says that for any $d$, if we apply a random restriction to a function
$f$ with quantum query complexity $\mathrm{Q}(f)\le n^{1/3}$, the restricted
function becomes exponentially close (in terms of $d$) to a depth-$d$ decision
tree. Our switching lemma works even in a "worst-case" sense, in that only the
indices to be restricted are random; the values they are restricted to are
chosen adversarially. Moreover, the switching lemma also works for polynomial
degree in place of quantum query complexity.
Filamentary structures (topologically embedded graphs with a metric
structure) are ubiquitous in science and engineering. A challenging problem in
topological data analysis (TDA) is to reconstruct the topology and geometry of
such an underlying (usually unknown) metric graph from possibly noisy data
sampled around it. Reeb graphs have recently been successfully employed in
abstract metric graph reconstruction under Gromov$\unicode{x2013}$Hausdorff
noise: the sample is assumed to be metrically close to the ground truth.
However, such a strong global density assumption is hardly achieved in
applications, making the existing Reeb graph-based methods untractible. We
relax the density assumption to give provable geometric reconstruction schemes,
even when the sample is metrically close only locally. A very different yet
more relevant paradigm focuses on the reconstruction of metric
graphs$\unicode{x2014}$embedded in the Euclidean space$\unicode{x2014}$from
Euclidean samples that are only Hausdorff-close. We further extend our
methodologies to provide novel, provable guarantees for the successful
geometric reconstruction of Euclidean graphs under the Hausdorff noise model.
Our technique produces promising results in reconstructing earthquake plate
tectonic boundaries from the global earthquake catalog.
Filamentary structures (topologically embedded graphs with a metric
structure) are ubiquitous in science and engineering. A challenging problem in
topological data analysis (TDA) is to reconstruct the topology and geometry of
such an underlying (usually unknown) metric graph from possibly noisy data
sampled around it. Reeb graphs have recently been successfully employed in
abstract metric graph reconstruction under Gromov$\unicode{x2013}$Hausdorff
noise: the sample is assumed to be metrically close to the ground truth.
However, such a strong global density assumption is hardly achieved in
applications, making the existing Reeb graph-based methods untractible. We
relax the density assumption to give provable geometric reconstruction schemes,
even when the sample is metrically close only locally. A very different yet
more relevant paradigm focuses on the reconstruction of metric
graphs$\unicode{x2014}$embedded in the Euclidean space$\unicode{x2014}$from
Euclidean samples that are only Hausdorff-close. We further extend our
methodologies to provide novel, provable guarantees for the successful
geometric reconstruction of Euclidean graphs under the Hausdorff noise model.
Our technique produces promising results in reconstructing earthquake plate
tectonic boundaries from the global earthquake catalog.
We study the token swapping problem, in which we are given a graph with an
initial assignment of one distinct token to each vertex, and a final desired
assignment (again with one token per vertex). The goal is to find the minimum
length sequence of swaps of adjacent tokens required to get from the initial to
final assignment.
The token swapping problem is known to be NP-complete. It is also known to
have a polynomial-time 4-approximation algorithm. From the
hardness-of-approximation side, it is known to be NP-hard to approximate with
ratio better than 1001/1000.
Our main result is an improvement of the approximation ratio of the lower
bound: We show that it is NP-hard to approximate with ratio better than 14/13.
We then turn our attention to the 0/1-weighted version, in which every token
has a weight of either 0 or 1, and the cost of a swap is the sum of the weights
of the two participating tokens. Unlike standard token swapping, no
constant-factor approximation is known for this version, and we provide an
explanation. We prove that 0/1-weighted token swapping is NP-hard to
approximate with ratio better than $(1-\varepsilon) \ln(n)$ for any constant
$\epsilon>0$.
Lastly, we prove two barrier results for the standard (unweighted) token
swapping problem. We show that one cannot beat the current best known
approximation ratio of 4 using a large class of algorithms which includes all
known algorithms, nor can one beat it using a common analysis framework.
We study the token swapping problem, in which we are given a graph with an
initial assignment of one distinct token to each vertex, and a final desired
assignment (again with one token per vertex). The goal is to find the minimum
length sequence of swaps of adjacent tokens required to get from the initial to
final assignment.
The token swapping problem is known to be NP-complete. It is also known to
have a polynomial-time 4-approximation algorithm. From the
hardness-of-approximation side, it is known to be NP-hard to approximate with
ratio better than 1001/1000.
Our main result is an improvement of the approximation ratio of the lower
bound: We show that it is NP-hard to approximate with ratio better than 14/13.
We then turn our attention to the 0/1-weighted version, in which every token
has a weight of either 0 or 1, and the cost of a swap is the sum of the weights
of the two participating tokens. Unlike standard token swapping, no
constant-factor approximation is known for this version, and we provide an
explanation. We prove that 0/1-weighted token swapping is NP-hard to
approximate with ratio better than $(1-\varepsilon) \ln(n)$ for any constant
$\epsilon>0$.
Lastly, we prove two barrier results for the standard (unweighted) token
swapping problem. We show that one cannot beat the current best known
approximation ratio of 4 using a large class of algorithms which includes all
known algorithms, nor can one beat it using a common analysis framework.
A recent work by Christiansen, Nowicki, and Rotenberg provides dynamic
algorithms for coloring sparse graphs, concretely as a function of the
arboricity alpha of the input graph. They give two randomized algorithms:
O({alpha} log {alpha}) implicit coloring in poly(log n) worst-case update and
query times, and O(min{{alpha} log {alpha}, {alpha} log log log n}) implicit
coloring in poly(log n) amortized update and query times (against an oblivious
adversary). We improve these results in terms of the number of colors and the
time guarantee: First, we present an extremely simple algorithm that computes
an O({alpha})-implicit coloring with poly(log n) amortized update and query
times. Second, and as the main technical contribution of our work, we show that
the time complexity guarantee can be strengthened from amortized to worst-case.
That is, we give a dynamic algorithm for implicit O({alpha})-coloring with
poly(log n) worst-case update and query times (against an oblivious adversary).
A recent work by Christiansen, Nowicki, and Rotenberg provides dynamic
algorithms for coloring sparse graphs, concretely as a function of the
arboricity alpha of the input graph. They give two randomized algorithms:
O({alpha} log {alpha}) implicit coloring in poly(log n) worst-case update and
query times, and O(min{{alpha} log {alpha}, {alpha} log log log n}) implicit
coloring in poly(log n) amortized update and query times (against an oblivious
adversary). We improve these results in terms of the number of colors and the
time guarantee: First, we present an extremely simple algorithm that computes
an O({alpha})-implicit coloring with poly(log n) amortized update and query
times. Second, and as the main technical contribution of our work, we show that
the time complexity guarantee can be strengthened from amortized to worst-case.
That is, we give a dynamic algorithm for implicit O({alpha})-coloring with
poly(log n) worst-case update and query times (against an oblivious adversary).
This paper improves and in two cases nearly settles, up to logarithmically
lower-order factors, the deterministic complexity of some of the most central
problems in distributed graph algorithms, which have been studied for over
three decades:
Near-Optimal Network Decomposition: We present a deterministic distributed
algorithm that computes a network decomposition in approximately O(log^2 n)
rounds, with O(log n) diameter and O(log n) colors. This round complexity is
near-optimal in the following sense: even given an ideal network decomposition,
using it (in the standard way) requires round complexity equal to the product
of diameter and number of colors, which is known to be approximately
Omega(log^2 n). This near-optimality is remarkable, considering the rarity of
optimal deterministic distributed algorithms and that for network
decomposition, the first polylogarithmic-round algorithm was achieved only
recently, by Rozhon and Ghaffari [STOC 2020], after three decades.
Near-Optimal Ruling Set: We present a deterministic distributed algorithm
that computes an O(log log n) ruling set in approximately O(log n) rounds. This
is an exponential improvement over the O(log n) ruling set of Awerbuch,
Goldberg, Luby, and Plotkin [FOCS 1989], while almost matching their O(log n)
round complexity. Our result's round complexity nearly matches the
approximately Omega(log n) lower bound established by Balliu, Brandt, Kuhn, and
Olivetti [STOC 2022], which applies to any poly(log log n) ruling set.
Improved Maximal Independent Set (MIS): We present a deterministic
distributed algorithm for computing an MIS in approximately O(log^(5/3) n)
rounds. This improves upon the approximately O(log^2 n) complexity achieved by
Ghaffari and Grunau [STOC 2023] and breaks the log-squared barrier necessary
for any method based on network decomposition.
This paper improves and in two cases nearly settles, up to logarithmically
lower-order factors, the deterministic complexity of some of the most central
problems in distributed graph algorithms, which have been studied for over
three decades:
Near-Optimal Network Decomposition: We present a deterministic distributed
algorithm that computes a network decomposition in approximately O(log^2 n)
rounds, with O(log n) diameter and O(log n) colors. This round complexity is
near-optimal in the following sense: even given an ideal network decomposition,
using it (in the standard way) requires round complexity equal to the product
of diameter and number of colors, which is known to be approximately
Omega(log^2 n). This near-optimality is remarkable, considering the rarity of
optimal deterministic distributed algorithms and that for network
decomposition, the first polylogarithmic-round algorithm was achieved only
recently, by Rozhon and Ghaffari [STOC 2020], after three decades.
Near-Optimal Ruling Set: We present a deterministic distributed algorithm
that computes an O(log log n) ruling set in approximately O(log n) rounds. This
is an exponential improvement over the O(log n) ruling set of Awerbuch,
Goldberg, Luby, and Plotkin [FOCS 1989], while almost matching their O(log n)
round complexity. Our result's round complexity nearly matches the
approximately Omega(log n) lower bound established by Balliu, Brandt, Kuhn, and
Olivetti [STOC 2022], which applies to any poly(log log n) ruling set.
Improved Maximal Independent Set (MIS): We present a deterministic
distributed algorithm for computing an MIS in approximately O(log^(5/3) n)
rounds. This improves upon the approximately O(log^2 n) complexity achieved by
Ghaffari and Grunau [STOC 2023] and breaks the log-squared barrier necessary
for any method based on network decomposition.
We study the following distance realization problem. Given a quasi-metric $D$
on a set $T$ of terminals, does there exist a directed Okamura-Seymour graph
that realizes $D$ as the (directed) shortest-path distance metric on $T$? We
show that, if we are further given the circular ordering of terminals lying on
the boundary, then Monge property is a sufficient and necessary condition. This
generalizes previous results for undirected Okamura-Seymour instances.
With the circular ordering, we give a greedy algorithm for constructing a
directed Okamura-Seymour instance that realizes the input quasi-metric. The
algorithm takes the dual perspective concerning flows and routings, and is
based on a new way of analyzing graph structures, by viewing graphs as
\emph{paths and their intersections}. We believe this new understanding is of
independent interest and will prove useful in other problems in graph theory
and graph algorithms.
We also design an efficient algorithm for finding such a circular ordering
that makes $D$ satisfy Monge property, if one exists. Combined with our result
above, this gives an efficient algorithm for the distance realization problem.
We study the following distance realization problem. Given a quasi-metric $D$
on a set $T$ of terminals, does there exist a directed Okamura-Seymour graph
that realizes $D$ as the (directed) shortest-path distance metric on $T$? We
show that, if we are further given the circular ordering of terminals lying on
the boundary, then Monge property is a sufficient and necessary condition. This
generalizes previous results for undirected Okamura-Seymour instances.
With the circular ordering, we give a greedy algorithm for constructing a
directed Okamura-Seymour instance that realizes the input quasi-metric. The
algorithm takes the dual perspective concerning flows and routings, and is
based on a new way of analyzing graph structures, by viewing graphs as
\emph{paths and their intersections}. We believe this new understanding is of
independent interest and will prove useful in other problems in graph theory
and graph algorithms.
We also design an efficient algorithm for finding such a circular ordering
that makes $D$ satisfy Monge property, if one exists. Combined with our result
above, this gives an efficient algorithm for the distance realization problem.
Given a network with an ongoing epidemic, the network immunization problem
seeks to identify a fixed number of nodes to immunize in order to maximize the
number of infections prevented. One of the fundamental computational challenges
in network immunization is that the objective function is generally neither
submodular nor supermodular. As a result, no efficient algorithm is known to
consistently find a solution with a constant approximation guarantee.
Traditionally, this problem is addressed using proxy objectives, which offer
better approximation properties. However, converting to these indirect
optimizations often introduces losses in effectiveness. In this paper, we
overcome these fundamental barriers by utilizing the underlying stochastic
structures of the diffusion process. Similar to the traditional influence
objective, the immunization objective is an expectation that can be expressed
as the sum of objectives over deterministic instances. However, unlike the
former, some of these terms are not submodular. The key step is proving that
this sum has a bounded deviation from submodularity, thereby enabling the
greedy algorithm to achieve constant factor approximation. We show that this
approximation still stands considering a variety of immunization settings and
spread models.
Given a network with an ongoing epidemic, the network immunization problem
seeks to identify a fixed number of nodes to immunize in order to maximize the
number of infections prevented. One of the fundamental computational challenges
in network immunization is that the objective function is generally neither
submodular nor supermodular. As a result, no efficient algorithm is known to
consistently find a solution with a constant approximation guarantee.
Traditionally, this problem is addressed using proxy objectives, which offer
better approximation properties. However, converting to these indirect
optimizations often introduces losses in effectiveness. In this paper, we
overcome these fundamental barriers by utilizing the underlying stochastic
structures of the diffusion process. Similar to the traditional influence
objective, the immunization objective is an expectation that can be expressed
as the sum of objectives over deterministic instances. However, unlike the
former, some of these terms are not submodular. The key step is proving that
this sum has a bounded deviation from submodularity, thereby enabling the
greedy algorithm to achieve constant factor approximation. We show that this
approximation still stands considering a variety of immunization settings and
spread models.
Authors: MohammadTaghi Hajiaghayi, Shayan Chashm Jahan, Mohammad Sharifi, Suho Shin, Max Springer
The online bipartite matching problem, extensively studied in the literature,
deals with the allocation of online arriving vertices (items) to a
predetermined set of offline vertices (agents). However, little attention has
been given to the concept of class fairness, where agents are categorized into
different classes, and the matching algorithm must ensure equitable
distribution across these classes.
We here focus on randomized algorithms for the fair matching of indivisible
items, subject to various definitions of fairness. Our main contribution is the
first (randomized) non-wasteful algorithm that simultaneously achieves a $1/2$
approximation to class envy-freeness (CEF) while simultaneously ensuring an
equivalent approximation to the class proportionality (CPROP) and utilitarian
social welfare (USW) objectives. We supplement this result by demonstrating
that no non-wasteful algorithm can achieve an $\alpha$-CEF guarantee for
$\alpha > 0.761$. In a similar vein, we provide a novel input instance for
deterministic divisible matching that demonstrates a nearly tight CEF
approximation.
Lastly, we define the ``price of fairness,'' which represents the trade-off
between optimal and fair matching. We demonstrate that increasing the level of
fairness in the approximation of the solution leads to a decrease in the
objective of maximizing USW, following an inverse proportionality relationship.
The online bipartite matching problem, extensively studied in the literature,
deals with the allocation of online arriving vertices (items) to a
predetermined set of offline vertices (agents). However, little attention has
been given to the concept of class fairness, where agents are categorized into
different classes, and the matching algorithm must ensure equitable
distribution across these classes.
We here focus on randomized algorithms for the fair matching of indivisible
items, subject to various definitions of fairness. Our main contribution is the
first (randomized) non-wasteful algorithm that simultaneously achieves a $1/2$
approximation to class envy-freeness (CEF) while simultaneously ensuring an
equivalent approximation to the class proportionality (CPROP) and utilitarian
social welfare (USW) objectives. We supplement this result by demonstrating
that no non-wasteful algorithm can achieve an $\alpha$-CEF guarantee for
$\alpha > 0.761$. In a similar vein, we provide a novel input instance for
deterministic divisible matching that demonstrates a nearly tight CEF
approximation.
Lastly, we define the ``price of fairness,'' which represents the trade-off
between optimal and fair matching. We demonstrate that increasing the level of
fairness in the approximation of the solution leads to a decrease in the
objective of maximizing USW, following an inverse proportionality relationship.
Authors: Daniel Salwasser, Daniel Seemaier, Lars Gottesbüren, Peter Sanders
We present TeraPart, a memory-efficient multilevel graph partitioning method
that is designed to scale to extremely large graphs.
In balanced graph partitioning, the goal is to divide the vertices into $k$
blocks with balanced size while cutting as few edges as possible.
Due to its NP-hard nature, heuristics are prevalent in this field, with the
multilevel framework as the state-of-the-art method.
Recent work has seen tremendous progress in speeding up partitioning
algorithms through parallelism. The current obstacle in scaling to larger
graphs is the high memory usage due to auxiliary data structures and storing
the graph itself in memory.
In this paper, we present and study several optimizations to significantly
reduce their memory footprint.
We devise parallel label propagation clustering and graph contraction
algorithms that use $O(n)$ auxiliary space instead of $O(np)$, where $p$ is the
number of processors.
Moreover, we employ an existing compressed graph representation that enables
iterating over a neighborhood by on-the-fly decoding at speeds close to the
uncompressed graph.
Combining these optimizations yields up to a 16-fold reduction in peak
memory, while retaining the same solution quality and similar speed.
This configuration can partition a graph with one trillion edges in under 8
minutes \emph{on a single machine} using around 900\,GiB of RAM.
This is the first work to employ the multilevel framework at this scale,
which is vital to achieving low edge cuts.
Moreover, our distributed memory implementation handles graphs of up to 16
trillion edges on 128 machines with 256\,GiB each in just under 10 minutes.
Finally, we present a version of shared-memory parallel FM local search that
uses $O(m)$ space instead of $O(nk)$, reducing peak memory by factor 5.8 on
medium-sized graphs without affecting running time.
We present TeraPart, a memory-efficient multilevel graph partitioning method
that is designed to scale to extremely large graphs.
In balanced graph partitioning, the goal is to divide the vertices into $k$
blocks with balanced size while cutting as few edges as possible.
Due to its NP-hard nature, heuristics are prevalent in this field, with the
multilevel framework as the state-of-the-art method.
Recent work has seen tremendous progress in speeding up partitioning
algorithms through parallelism. The current obstacle in scaling to larger
graphs is the high memory usage due to auxiliary data structures and storing
the graph itself in memory.
In this paper, we present and study several optimizations to significantly
reduce their memory footprint.
We devise parallel label propagation clustering and graph contraction
algorithms that use $O(n)$ auxiliary space instead of $O(np)$, where $p$ is the
number of processors.
Moreover, we employ an existing compressed graph representation that enables
iterating over a neighborhood by on-the-fly decoding at speeds close to the
uncompressed graph.
Combining these optimizations yields up to a 16-fold reduction in peak
memory, while retaining the same solution quality and similar speed.
This configuration can partition a graph with one trillion edges in under 8
minutes \emph{on a single machine} using around 900\,GiB of RAM.
This is the first work to employ the multilevel framework at this scale,
which is vital to achieving low edge cuts.
Moreover, our distributed memory implementation handles graphs of up to 16
trillion edges on 128 machines with 256\,GiB each in just under 10 minutes.
Finally, we present a version of shared-memory parallel FM local search that
uses $O(m)$ space instead of $O(nk)$, reducing peak memory by factor 5.8 on
medium-sized graphs without affecting running time.
Given a fixed arity $k \geq 2$, Min-$k$-CSP on complete instances involves a
set of $n$ variables $V$ and one nontrivial constraint for every $k$-subset of
variables (so there are $\binom{n}{k}$ constraints). The goal is to find an
assignment that minimizes unsatisfied constraints. Unlike Max-$k$-CSP that
admits a PTAS on dense or expanding instances, the approximability of
Min-$k$-CSP is less understood. For some CSPs like Min-$k$-SAT, there's an
approximation-preserving reduction from general to dense instances, making
complete instances unique for potential new techniques.
This paper initiates a study of Min-$k$-CSPs on complete instances. We
present an $O(1)$-approximation algorithm for Min-2-SAT on complete instances,
the minimization version of Max-2-SAT. Since $O(1)$-approximation on dense or
expanding instances refutes the Unique Games Conjecture, it shows a strict
separation between complete and dense/expanding instances.
Then we study the decision versions of CSPs, aiming to satisfy all
constraints; which is necessary for any nontrivial approximation. Our second
main result is a quasi-polynomial time algorithm for every Boolean $k$-CSP on
complete instances, including $k$-SAT. We provide additional algorithmic and
hardness results for CSPs with larger alphabets, characterizing (arity,
alphabet size) pairs that admit a quasi-polynomial time algorithm on complete
instances.
Given a fixed arity $k \geq 2$, Min-$k$-CSP on complete instances involves a
set of $n$ variables $V$ and one nontrivial constraint for every $k$-subset of
variables (so there are $\binom{n}{k}$ constraints). The goal is to find an
assignment that minimizes unsatisfied constraints. Unlike Max-$k$-CSP that
admits a PTAS on dense or expanding instances, the approximability of
Min-$k$-CSP is less understood. For some CSPs like Min-$k$-SAT, there's an
approximation-preserving reduction from general to dense instances, making
complete instances unique for potential new techniques.
This paper initiates a study of Min-$k$-CSPs on complete instances. We
present an $O(1)$-approximation algorithm for Min-2-SAT on complete instances,
the minimization version of Max-2-SAT. Since $O(1)$-approximation on dense or
expanding instances refutes the Unique Games Conjecture, it shows a strict
separation between complete and dense/expanding instances.
Then we study the decision versions of CSPs, aiming to satisfy all
constraints; which is necessary for any nontrivial approximation. Our second
main result is a quasi-polynomial time algorithm for every Boolean $k$-CSP on
complete instances, including $k$-SAT. We provide additional algorithmic and
hardness results for CSPs with larger alphabets, characterizing (arity,
alphabet size) pairs that admit a quasi-polynomial time algorithm on complete
instances.
The CS department at the University of Wisconsin-Madison is hiring in algorithmic fairness, accountability, and transparency, safety, and privacy (all broadly construed), please see the first URL. The department is broadly hiring in all other areas as well, please see the second URL, including understanding the strengths and limitations of AI, both theoretically and experimentally. […]
The CS department at the University of Wisconsin-Madison is hiring in algorithmic fairness, accountability, and transparency, safety, and privacy (all broadly construed), please see the first URL.
The department is broadly hiring in all other areas as well, please see the second URL, including understanding the strengths and limitations of AI, both theoretically and experimentally.
a) Candidates Gender or Race. The people who say its about time we had a female president might not want to vote for a President Marjorie Taylor Green. (A while back I thought that the first african-american president and/or first female president would be a republican since such a candidates might take some usually-democratic voters into the republican camp. One of many predictions I was wrong about.)
b) Candidates personal lives. Attempts to tie a candidates affairs to their policies never made sense to me.
c) How well the candidate did in school. I care what they know and don't know now, and also if they know what they don't know. (Who was the last president to not have a college degree? I will tell you at the end of this post.)
d) Their religion. There were people who agreed with JFK on policy issues but did not want to vote for him because he was Catholic. I didn't understand it then nor do I understand it now. Biden is Catholic but this rarely comes up. Romney was Mormon and this only came up in the Republican primary, not in the general. So I am glad it is no longer an issue. Having said that, we still haven't had a Jewish president, a Muslim President, or an Atheist president.
e) Do I care if the candidate X will benefit me personally? It is very hard to tell that. Someone like Elon Musk is clearly going to support Kamala since she believes global warming is true and the e-cars will be a part of dealing with it. This is an example of someone supporting someone since it benefits them personally. Oh, bad example.
Vance thinks people vote this way as he recently said that women past child-bearing age should not care about abortion rights.
f) There are ads that say things like I served in the military defending our country, and now I want to defined your rights to XXX. I don't see how serving in the military makes them a better senator or whatever.
g) I don't care how they are doing at polls. Some of the articles saying that candidate X is ahead also tend to say that that shows X is better. I campaigned for George McGovern in 1972 and he went on to lose by a lot. Some of my friends told me that I backed a loser and tried to make that an insult (I have better friends now). This puzzled me then since the fact that my candidate lost says NOTHING about how he would do as president.
2) DO I care about if they lie? Depends on how much and about what. That Vance changes his mind about Trump (he was anti-Trump in 2016) or that Kamala changed her mind on fracking are the standard lies that politicians always tell so I don't care about that. This may be a reflection on the low standards we have. More serious are lies that they KNOW are false and might ENDANGER people.
3) DO I care if they changed their mind on an issue. All I care about is how they feel NOW, though if they changed their mind I might not believe them.
4) I DO care about policy and ability to get things done and to consider all sides of an issue. (I won't say what policies I like since I am trying to keep this post non-partisan).
5) Some of the attacks on Kamala have been a women should not be president. This puzzles me since there will come a time when the Republicans have a female candidate.
6) I am surprised there is anyone who is still undecided. We know both candidates VERY WELL. What more information do you need?
7) Articles like Five Reasons Kamala Will Win or Five Reasons Trump Will Win are usually crap. For example, one of the reasons Kamala will win is People are tired of Trump's corruption. But that just means that the author of the article is tired of it, and the author does not speak for the American people. An argument like Kamala is ahead in 5 of the 7 swing states (if it were true) is the kind of argument I want to see. More to the point- an argument that someone will win should not be partisan.
8) Since JD Vance might lose Trump some votes (actually I doubt that) I have heard the old argument that Sarah Palin cost McCain the Presidency, or at least cost him some votes. I began to think do we really know that? so I looked at some articles both new and old about this. I found things like:
The American public did not want Sarah Palin a heartbeat away from the presidency because of her views, or because of her perceived lack of intelligence or blah blah. Hence she cost McCain votes.
NONE of the articles I read pointed to polls or other EVIDENCE for this point of view.
There probably is some evidence on the issue (I do not know which way it would go) somewhere but the LACK of any INTEREST in it bothers me.
9) I am surprised there are any undecided voters at this point. Both candidates are known to the public, so I don't see what more there is to think about. I accidentally already said this, however (a) I don't want to mess up my numbering and (ii) I do feel strongly about this point, so its worth having twice.
10) Because of Americas only-2-party-system you end up voting for people you agree with on some things but not others. I can imagine Mike Pence saying:
I prefer Trump to Kamala on the abortion issue.
I prefer Kamala to Trump on the Hang Mike Pence issue.
Gee, who do I vote for?
Actually he has said he is voting for neither one.
11) IF Kamala wins then the decision to make Tim Walz her VP will be seen as genius.
IF Kamala does not win Pennsylvania and loses the election then NOT picking Josh Shapiro (popular governor of PA) will be seen as stupid.
I call bullshit on both of those. There are SO MANY factors at play here. This reminds me of when a basketball team wins 100-99 and the sportscasters are saying things like
The decision to concentrate on 3-point shots was genius!
12) More generally, after-the-fact pundits all have their own theories about why candidate X won, even those who were confident that candidate Y was going to win, and those theories are either partisan or just uninformed. It is hard to know what works, even after the fact.
13) I had a post, here, about breaking the record for number-of-living-ex-presidents. I speculated that if
a) Biden won in 2020 and lost in 2024 (I overlooked the option of his not running.)
b) Carter lives to see the winner of the 2024 election inaugurated
THEN we would have SIX living ex-presidents, which would break the record. They would be
Carter, Clinton, Bush Jr, Obama, Trump, Biden.
If Trump wins then should Trump count? I think so- he would be a president AND an ex-president. If Kamala wins I won't have that issue. When I wrote that I didn't think Carter would last this long (he is 100), but he may very well. In fact, he has already voted!
14) Allan Lichtman is an American Historian (does that mean he studies American History or that he is American AND a historian?) who has a system to predict who will win the presidential election that has been correct 9 out of the last 10 elections. See here for his system. He predicts Kamala. I personally do not put to much stock in that since its going to be VERY CLOSE (hmmm- that's my prediction, and I could be wrong). While he is a democrat his system is OBJECTIVE-- he would have to be to be right so often. Even so, he is getting hate mail. This makes no sense. Predicting that X will happen does not mean you have an opinion about if X is good or bad.
15) When people argue passionately about a rules change (e.g., get rid of the electoral college) I do not believe them- they would argue the other way if the current rules favored their candidate.
16) JD Vance recently came out against the laws that say you can't wear political stuff at the polling place. He said that BOTH Kamala supporters and Trump supporters should be allowed to wear political T-shirts and hats and what not at the polling place. NO HE DIDN"T. He applauded a Trump Supporter for calling a Poll Worker a XXX and told him to YYY in for asking her to follow the polling place's rules prohibiting political merchandise. See here. (I use XXX and YYY so that this post won't get censored as happened in the past, see here. Oddly enough, this morning the ban was lifted, so for the original post that was banned see here.) No word yet on if he is going to praise a Texas man for punching a poll worker who told him to remove his Trump hat, see here.
The last president who did not have a college degree was Harry Truman.
By gasarch
Here are my random thoughts on the election:
1) Here is a list of things I DONT care about
a) Candidates Gender or Race. The people who say its about time we had a female president might not want to vote for a President Marjorie Taylor Green. (A while back I thought that the first african-american president and/or first female president would be a republican since such a candidates might take some usually-democratic voters into the republican camp. One of many predictions I was wrong about.)
b) Candidates personal lives. Attempts to tie a candidates affairs to their policies never made sense to me.
c) How well the candidate did in school. I care what they know and don't know now, and also if they know what they don't know. (Who was the last president to not have a college degree? I will tell you at the end of this post.)
d) Their religion. There were people who agreed with JFK on policy issues but did not want to vote for him because he was Catholic. I didn't understand it then nor do I understand it now. Biden is Catholic but this rarely comes up. Romney was Mormon and this only came up in the Republican primary, not in the general. So I am glad it is no longer an issue. Having said that, we still haven't had a Jewish president, a Muslim President, or an Atheist president.
e) Do I care if the candidate X will benefit me personally? It is very hard to tell that. Someone like Elon Musk is clearly going to support Kamala since she believes global warming is true and the e-cars will be a part of dealing with it. This is an example of someone supporting someone since it benefits them personally. Oh, bad example.
Vance thinks people vote this way as he recently said that women past child-bearing age should not care about abortion rights.
f) There are ads that say things like I served in the military defending our country, and now I want todefined your rights to XXX. I don't see how serving in the military makes them a better senator or whatever.
g) I don't care how they are doing at polls. Some of the articles saying that candidate X is ahead also tend to say that that shows X is better. I campaigned for George McGovern in 1972 and he went on to lose by a lot. Some of my friends told me that I backed a loser and tried to make that an insult (I have better friends now). This puzzled me then since the fact that my candidate lost says NOTHING about how he would do as president.
2) DO I care about if they lie? Depends on how much and about what. That Vance changes his mind about Trump (he was anti-Trump in 2016) or that Kamala changed her mind on fracking are the standard lies that politicians always tell so I don't care about that. This may be a reflection on the low standards we have. More serious are lies that they KNOW are false and might ENDANGER people.
3) DO I care if they changed their mind on an issue. All I care about is how they feel NOW, though if they changed their mind I might not believe them.
4) I DO care about policy and ability to get things done and to consider all sides of an issue. (I won't say what policies I like since I am trying to keep this post non-partisan).
5) Some of the attacks on Kamala have been a women should not be president. This puzzles me since there will come a time when the Republicans have a female candidate.
6) I am surprised there is anyone who is still undecided. We know both candidates VERY WELL. What more information do you need?
7) Articles like Five Reasons Kamala Will Win or Five Reasons Trump Will Win are usually crap. For example, one of the reasons Kamala will win is People are tired of Trump's corruption. But that just means that the author of the article is tired of it, and the author does not speak for the American people. An argument like Kamala is ahead in 5 of the 7 swing states (if it were true) is the kind of argument I want to see. More to the point- an argument that someone will win should not be partisan.
8) Since JD Vance might lose Trump some votes (actually I doubt that) I have heard the old argument that Sarah Palin cost McCain the Presidency, or at least cost him some votes. I began to think do wereally know that? so I looked at some articles both new and old about this. I found things like:
The American public did not want Sarah Palin a heartbeat away from the presidency because of her views, or because of her perceived lack of intelligence or blah blah. Hence she cost McCain votes.
NONE of the articles I read pointed to polls or other EVIDENCE for this point of view.
There probably is some evidence on the issue (I do not know which way it would go) somewhere but the LACK of any INTEREST in it bothers me.
9) I am surprised there are any undecided voters at this point. Both candidates are known to the public, so I don't see what more there is to think about. I accidentally already said this, however (a) I don't want to mess up my numbering and (ii) I do feel strongly about this point, so its worth having twice.
10) Because of Americas only-2-party-system you end up voting for people you agree with on some things but not others. I can imagine Mike Pence saying:
I prefer Trump to Kamala on the abortion issue.
I prefer Kamala to Trump on the Hang Mike Pence issue.
Gee, who do I vote for?
Actually he has said he is voting for neither one.
11) IF Kamala wins then the decision to make Tim Walz her VP will be seen as genius.
IF Kamala does not win Pennsylvania and loses the election then NOT picking Josh Shapiro (popular governor of PA) will be seen as stupid.
I call bullshit on both of those. There are SO MANY factors at play here. This reminds me of when a basketball team wins 100-99 and the sportscasters are saying things like
The decision to concentrate on 3-point shots was genius!
12) More generally, after-the-fact pundits all have their own theories about why candidate X won, even those who were confident that candidate Y was going to win, and those theories are either partisan or just uninformed. It is hard to know what works, even after the fact.
13) I had a post, here, about breaking the record for number-of-living-ex-presidents. I speculated that if
a) Biden won in 2020 and lost in 2024 (I overlooked the option of his not running.)
b) Carter lives to see the winner of the 2024 election inaugurated
THEN we would have SIX living ex-presidents, which would break the record. They would be
Carter, Clinton, Bush Jr, Obama, Trump, Biden.
If Trump wins then should Trump count? I think so- he would be a president AND an ex-president. If Kamala wins I won't have that issue. When I wrote that I didn't think Carter would last this long (he is 100), but he may very well. In fact, he has already voted!
14) Allan Lichtman is an American Historian (does that mean he studies American History or that he is American AND a historian?) who has a system to predict who will win the presidential election that has been correct 9 out of the last 10 elections. See here for his system. He predicts Kamala. I personally do not put to much stock in that since its going to be VERY CLOSE (hmmm- that's my prediction, and I could be wrong). While he is a democrat his system is OBJECTIVE-- he would have to be to be right so often. Even so, he is getting hate mail. This makes no sense. Predicting that X will happen does not mean you have an opinion about if X is good or bad.
15) When people argue passionately about a rules change (e.g., get rid of the electoral college) I do not believe them- they would argue the other way if the current rules favored their candidate.
16) JD Vance recently came out against the laws that say you can't wear political stuff at the polling place. He said that BOTH Kamala supporters and Trump supporters should be allowed to wear political T-shirts and hats and what not at the polling place. NO HE DIDN"T. He applauded a Trump Supporter for calling a Poll Worker a XXX and told him to YYY in for asking her to follow the polling place's rules prohibiting political merchandise. See here. (I use XXX and YYY so that this post won't get censored as happened in the past, see here. Oddly enough, this morning the ban was lifted, so for the original post that was banned see here.) No word yet on if he is going to praise a Texas man for punching a poll worker who told him to remove his Trump hat, see here.
The last president who did not have a college degree was Harry Truman.
A natural model of a source of randomness consists of a long stream of symbols $X = X_1\circ\ldots\circ X_t$, with some guarantee on the entropy of $X_i$ conditioned on the outcome of the prefix $x_1,\dots,x_{i-1}$. We study unpredictable sources, a generalization of the almost Chor--Goldreich (CG) sources considered in [DMOZ23]. In an unpredictable source $X$, for a typical draw of $x\sim X$, for most $i$, $x_i$ has a low probability of occurring given $x_1,\dots,x_{i-1}$. Such a model relaxes the unrealistic assumption of a CG source that for every $i$, and every $x_1,\dots,x_{i-1}$, the next symbol $X_i$ has sufficiently large entropy.
Unpredictable sources subsume all previously considered notions of almost CG sources, including those for which it was unknown whether random walks using $X$ mix, and including those that are equivalent to general sources with high min entropy.
We prove that random walks using unpredictable sources do mix, and as a result obtain seeded online condensers with constant entropy gap, and (seedless) deterministic condensers outputting a constant fraction of the entropy. In particular, our condensers run in space comparable to the total entropy of the stream $X$, even when its length is not known ahead of time. As another corollary, we obtain a new extractor based on expander random walks handling lower entropy than the classic expander based construction relying on spectral techniques [Gil98].
As our main technical tool, we provide a novel analysis covering a key case of adversarial random walks on lossless expanders that [DMOZ23] fails to address. As part of the analysis, we provide a ``chain rule for vertex probabilities''. The standard chain rule states that for every $x \sim X$ and $i$, $\Pr(x_1,\dots,x_i)= \Pr[X_i = x_i|X_{[1,i-1]}=x_1,\dots,x_{i-1}] \cdot \Pr(x_1,\dots,x_{i-1})$. If $W(x_1,\dots,x_i)$ is the vertex reached using $x_1,\dots,x_i$, then the chain rule for vertex probabilities essentially states that the same phenomena occurs for a typical $x$:
\[\Pr [V_i = W(x_1,\dots,x_i)] \leq \Pr[X_i = x_i|X_{[1,i-1]}=x_1,\dots,x_{i-1}] \cdot \Pr[V_{i-1} = W(x_1,\dots,x_{i-1})],\]
where $V_i$ is the vertex distribution of the random walk at step $i$ using $X$.
A natural model of a source of randomness consists of a long stream of symbols $X = X_1\circ\ldots\circ X_t$, with some guarantee on the entropy of $X_i$ conditioned on the outcome of the prefix $x_1,\dots,x_{i-1}$. We study unpredictable sources, a generalization of the almost Chor--Goldreich (CG) sources considered in [DMOZ23]. In an unpredictable source $X$, for a typical draw of $x\sim X$, for most $i$, $x_i$ has a low probability of occurring given $x_1,\dots,x_{i-1}$. Such a model relaxes the unrealistic assumption of a CG source that for every $i$, and every $x_1,\dots,x_{i-1}$, the next symbol $X_i$ has sufficiently large entropy.
Unpredictable sources subsume all previously considered notions of almost CG sources, including those for which it was unknown whether random walks using $X$ mix, and including those that are equivalent to general sources with high min entropy.
We prove that random walks using unpredictable sources do mix, and as a result obtain seeded online condensers with constant entropy gap, and (seedless) deterministic condensers outputting a constant fraction of the entropy. In particular, our condensers run in space comparable to the total entropy of the stream $X$, even when its length is not known ahead of time. As another corollary, we obtain a new extractor based on expander random walks handling lower entropy than the classic expander based construction relying on spectral techniques [Gil98].
As our main technical tool, we provide a novel analysis covering a key case of adversarial random walks on lossless expanders that [DMOZ23] fails to address. As part of the analysis, we provide a ``chain rule for vertex probabilities''. The standard chain rule states that for every $x \sim X$ and $i$, $\Pr(x_1,\dots,x_i)= \Pr[X_i = x_i|X_{[1,i-1]}=x_1,\dots,x_{i-1}] \cdot \Pr(x_1,\dots,x_{i-1})$. If $W(x_1,\dots,x_i)$ is the vertex reached using $x_1,\dots,x_i$, then the chain rule for vertex probabilities essentially states that the same phenomena occurs for a typical $x$:
\[\Pr [V_i = W(x_1,\dots,x_i)] \leq \Pr[X_i = x_i|X_{[1,i-1]}=x_1,\dots,x_{i-1}] \cdot \Pr[V_{i-1} = W(x_1,\dots,x_{i-1})],\]
where $V_i$ is the vertex distribution of the random walk at step $i$ using $X$.
Kyle is far more gracious in his post than he needed to be. My post was over the top. If you are a regular reader, you know I try to be playful and polemical in my writing. Part of what makes my writing fun for me and the people who engage with me is my habitual line stepping. Sometimes, playful writing leads to imprecision, and I’m fine with that. There is a delicate trade-off between reach and precision in scientific writing that all science writers balance.
My main point was that the Higgs discovery doesn’t provide a good defense of statistical testing. Kyle and I disagree here, and that’s fine. But note that I was not pulling my critique out of thin air. There was disagreement among the physics community at the time and the previous post links to some of the relevant debate on the subject. However, I definitely have a tendency to go overboard. There are two parts I’d change if I were allowed a revision.
First, the term “Majority vote.” When I wrote that the participatory decision making in the CERN collaboration was done by majority voting, I didn’t mean this literally. However, there is nothing in the text around the phrase to see that I was exaggerating for emphasis. I apologize for taking poetic license here, as this is a place where I should have been precise. As Kyle points out, the governance structures at CERN are consensus-based and very intricate. The point I was hoping to raise with this passage is that science through complex governance systems is itself kind of weird! These large collaborations are a late 20th century phenomenon and are aberrational in the extended history of modern science. I am deeply interested in the structures you put in place to build deliberative governance structures to make proclamations about scientific results.
The statistical rules were set, as Kyle says, by consensus. They were part of the governance structure. The fact that these rules, which people not named me can debate the validity of, helped 3000+ people reach a consensus is striking. The compelling evidence of the Higgs is the consensus, not the statistics.
The second part that I would delete not because I disagree with it but because it completely detracts from the argument. In describing how the Higgs Boson fails Ian Hacking’s sprayability criterion, I wrote
“The Higgs field has no bearing on any physics at any scale anyone would ever care about. So I don’t care either way if physicists think they found a Higgs. It has zero bearing on my existence.“
I mean, I agree with this, but why should anyone care whether I care? This isn’t a good argument. What I should have said is that it’s not enough to keep banging the same protons together to get further confirmation beyond 20 or 30 𝜎 or whatever. At some point, the confirmation need come from other experimental evidence. For instance, a lot of people raised objections to the statistics used in LIGO’s gravitational wave interferometry. However, their GW170817 event provided auxiliary confirmation. The LIGO interferometer detected a gravitational wave event, triangulated a region in the sky where they thought it came from, and international telescopes confirmed colliding neutron stars in that location. At some point I’m sure we’ll get a similar new means of seeing the Higgs, but we don’t have it yet.
I’d recommend a couple of other rejoinders to the debate. I agree with all of what David Chapman says in this note about the complexity of discovery. Rex Douglass, who tends to be even spicier than me, raises more points about why frequentist tests are not good summaries of experiments with any degree of complexity.
OK, but what about the title? I always overestimate the accessibility of the cutesy references I make in titling posts.2 This one referred to an over-the-top but deeply prescient polemic by Jean Baudrillard “The Gulf War Did Not Take Place.” Baudrillard’s point was never to deny that the violence and death didn’t happen but to describe the multiple levels of mediation on the battlefield and in news propaganda that created a baffling hyperreality where it was impossible to distinguish a presented war from a human rights atrocity. It’s heavy French postmodern stuff, but Baudriallardian hyperreality is evermore present in our social media-driven world. It’s interesting that, despite spending the majority of their lives in a hellish online hyperreality, the number of twitter users who are aware of Baudriallard’s work is near zero.
I don’t think the title is a perfect fit for the Higgs discovery, but what makes contemporary fundamental physics so baffling to everyone (as Kyle admits, physicists included!) is how mediated the highly subatomic is from actionable reality. We’re probing things that we can only know exist through the most complicated, expensive, and specific experiments we’ve ever devised. Kyle’s point, which again I fumbled in an attempt to be provocative and literary, is that establishing that something is happening at such scales requires excessive amounts of deeply human regulatory structures. When you call it bureaucracy, it touches a nerve. No one wants to admit they like bureaucracy. But we could chalk up the Higgs as evidence that bureaucracy is necessary for certain endeavors.
In any event, I use irreverence (i.e., shitposting) to engage with tricky philosophical questions. I know that people unfamiliar with my schtick might read me as just being an asshole.3 That’s fair. One good thing that came out of this post is many readers’ thoughtful and generous engagement with an argument I’m still workshopping. I don’t consider this blog to be the last word on anything, and the conversation is part of what I value about it. Another good thing that came out of the twitter hate was science writer Dan Garisto calling me “a smugly incurious Latour for tech bros.” I need to add that line to my bio.
I don’t want to spend this post quibbling over the parts I don’t agree with, but I’ll highlight a quick two. First, I strongly disagree that we need to understand the Higgs mechanism to understand atoms in any functional way. Quantum Field Theory does not predict the periodic table. I’m strongly Cartwrightian, and fascinated by the locality of physical law despite its professed universality.
Secondly, I’m not willing to give the World Wide Web to high-energy physics. YMMV there. But maybe Tim Berners Lee will get a Physics Nobel next year.
I always overestimate the accessibility of my goofy references. I’m guessing there at most three people who caught that “The Shape of Stats to Come” was simultaneously a shout out to John Tukey and The Refused. You can google the title of this one to catch the reference to the sciencey cold war I find myself reigniting.
In this paper, we present a novel algorithm that integrates deep learning
with the polycube method (DL-Polycube) to generate high-quality hexahedral
(hex) meshes, which are then used to construct volumetric splines for
isogeometric analysis. Our DL-Polycube algorithm begins by establishing a
connection between surface triangular meshes and polycube structures. We employ
deep neural network to classify surface triangular meshes into their
corresponding polycube structures. Following this, we combine the acquired
polycube structural information with unsupervised learning to perform surface
segmentation of triangular meshes. This step addresses the issue of
segmentation not corresponding to a polycube while reducing manual
intervention. Quality hex meshes are then generated from the polycube
structures, with employing octree subdivision, parametric mapping and quality
improvement techniques. The incorporation of deep learning for creating
polycube structures, combined with unsupervised learning for segmentation of
surface triangular meshes, substantially accelerates hex mesh generation.
Finally, truncated hierarchical B-splines are constructed on the generated hex
meshes. We extract trivariate B\'ezier elements from these splines and apply
them directly in isogeometric analysis. We offer several examples to
demonstrate the robustness of our DL-Polycube algorithm.
In this paper, we present a novel algorithm that integrates deep learning
with the polycube method (DL-Polycube) to generate high-quality hexahedral
(hex) meshes, which are then used to construct volumetric splines for
isogeometric analysis. Our DL-Polycube algorithm begins by establishing a
connection between surface triangular meshes and polycube structures. We employ
deep neural network to classify surface triangular meshes into their
corresponding polycube structures. Following this, we combine the acquired
polycube structural information with unsupervised learning to perform surface
segmentation of triangular meshes. This step addresses the issue of
segmentation not corresponding to a polycube while reducing manual
intervention. Quality hex meshes are then generated from the polycube
structures, with employing octree subdivision, parametric mapping and quality
improvement techniques. The incorporation of deep learning for creating
polycube structures, combined with unsupervised learning for segmentation of
surface triangular meshes, substantially accelerates hex mesh generation.
Finally, truncated hierarchical B-splines are constructed on the generated hex
meshes. We extract trivariate B\'ezier elements from these splines and apply
them directly in isogeometric analysis. We offer several examples to
demonstrate the robustness of our DL-Polycube algorithm.
Authors: Juan Juan Gerardo Alcázar, Carlos Hermoso, Hüsnü Anıl Çoban, Uğur Gözütok
In this paper we provide, first, a general symbolic algorithm for computing
the symmetries of a given rational surface, based on the classical differential
invariants of surfaces, i.e. Gauss curvature and mean curvature. In practice,
the algorithm works well for sparse parametrizations (e.g. toric surfaces) and
PN surfaces. Additionally, we provide a specific, also symbolic algorithm for
computing the symmetries of ruled surfaces; this algorithm works extremely well
in practice, since the problem is reduced to that of rational space curves,
which can be efficiently solved by using existing methods. The algorithm for
ruled surfaces is based on the fact, proven in the paper, that every symmetry
of a rational surface must also be a symmetry of its line of striction, which
is a rational space curve. The algorithms have been implemented in the computer
algebra system Maple, and the implementations have been made public; evidence
of their performance is given in the paper.
In this paper we provide, first, a general symbolic algorithm for computing
the symmetries of a given rational surface, based on the classical differential
invariants of surfaces, i.e. Gauss curvature and mean curvature. In practice,
the algorithm works well for sparse parametrizations (e.g. toric surfaces) and
PN surfaces. Additionally, we provide a specific, also symbolic algorithm for
computing the symmetries of ruled surfaces; this algorithm works extremely well
in practice, since the problem is reduced to that of rational space curves,
which can be efficiently solved by using existing methods. The algorithm for
ruled surfaces is based on the fact, proven in the paper, that every symmetry
of a rational surface must also be a symmetry of its line of striction, which
is a rational space curve. The algorithms have been implemented in the computer
algebra system Maple, and the implementations have been made public; evidence
of their performance is given in the paper.
For $S \in \mathbb{N}^n$ and $T \in \mathbb{N}$, the Subset Sum Problem (SSP)
$\exists^? x \in \{0,1\}^n $ such that $S^T\cdot x = T$ can be interpreted as
the problem of deciding whether the intersection of the positive unit hypercube
$Q_n = [0,1]^n$ with the hyperplane $S^T\cdot \left(x - \frac{S}{\|S\|^2 }\cdot
T \right) = 0$ contains at least a vertex. In this paper, we give an algorithm
of complexity $\mathcal{O}\left( \frac{1}{\epsilon}\cdot n^b \right)$, for some
absolute constant $b$, which either proves that there are no vertices in a slab
of thickness $\epsilon$ either finds a vertex in the slab of thickness $4\cdot
\epsilon$. It is shown that any vertex $P$ in a slab of thickness $\epsilon$
meets $\left| \frac{S^T\cdot P}{T} - 1 \right| \leq \epsilon$, therefore making
the proposed algorithm a FPTAS for the SSP.
For $S \in \mathbb{N}^n$ and $T \in \mathbb{N}$, the Subset Sum Problem (SSP)
$\exists^? x \in \{0,1\}^n $ such that $S^T\cdot x = T$ can be interpreted as
the problem of deciding whether the intersection of the positive unit hypercube
$Q_n = [0,1]^n$ with the hyperplane $S^T\cdot \left(x - \frac{S}{\|S\|^2 }\cdot
T \right) = 0$ contains at least a vertex. In this paper, we give an algorithm
of complexity $\mathcal{O}\left( \frac{1}{\epsilon}\cdot n^b \right)$, for some
absolute constant $b$, which either proves that there are no vertices in a slab
of thickness $\epsilon$ either finds a vertex in the slab of thickness $4\cdot
\epsilon$. It is shown that any vertex $P$ in a slab of thickness $\epsilon$
meets $\left| \frac{S^T\cdot P}{T} - 1 \right| \leq \epsilon$, therefore making
the proposed algorithm a FPTAS for the SSP.
We show that the problem of counting the number of 2-optimal tours in
instances of the Travelling Salesperson Problem (TSP) on complete graphs is
#P-complete. In addition, we show that the expected number of 2-optimal tours
in random instances of the TSP on complete graphs is $O(1.2098^n \sqrt{n!})$.
Based on numerical experiments, we conjecture that the true bound is at most
$O(\sqrt{n!})$, which is approximately the square root of the total number of
tours.
We show that the problem of counting the number of 2-optimal tours in
instances of the Travelling Salesperson Problem (TSP) on complete graphs is
#P-complete. In addition, we show that the expected number of 2-optimal tours
in random instances of the TSP on complete graphs is $O(1.2098^n \sqrt{n!})$.
Based on numerical experiments, we conjecture that the true bound is at most
$O(\sqrt{n!})$, which is approximately the square root of the total number of
tours.
We consider the foundational problem of maintaining a
$(1-\varepsilon)$-approximate maximum weight matching (MWM) in an $n$-node
dynamic graph undergoing edge insertions and deletions. We provide a general
reduction that reduces the problem on graphs with a weight range of
$\mathrm{poly}(n)$ to $\mathrm{poly}(1/\varepsilon)$ at the cost of just an
additive $\mathrm{poly}(1/\varepsilon)$ in update time. This improves upon the
prior reduction of Gupta-Peng (FOCS 2013) which reduces the problem to a weight
range of $\varepsilon^{-O(1/\varepsilon)}$ with a multiplicative cost of
$O(\log n)$.
When combined with a reduction of Bernstein-Dudeja-Langley (STOC 2021) this
yields a reduction from dynamic $(1-\varepsilon)$-approximate MWM in bipartite
graphs with a weight range of $\mathrm{poly}(n)$ to dynamic
$(1-\varepsilon)$-approximate maximum cardinality matching in bipartite graphs
at the cost of a multiplicative $\mathrm{poly}(1/\varepsilon)$ in update time,
thereby resolving an open problem in [GP'13; BDL'21]. Additionally, we show
that our approach is amenable to MWM problems in streaming, shared-memory
work-depth, and massively parallel computation models. We also apply our
techniques to obtain an efficient dynamic algorithm for rounding weighted
fractional matchings in general graphs. Underlying our framework is a new
structural result about MWM that we call the "matching composition lemma" and
new dynamic matching subroutines that may be of independent interest.
We consider the foundational problem of maintaining a
$(1-\varepsilon)$-approximate maximum weight matching (MWM) in an $n$-node
dynamic graph undergoing edge insertions and deletions. We provide a general
reduction that reduces the problem on graphs with a weight range of
$\mathrm{poly}(n)$ to $\mathrm{poly}(1/\varepsilon)$ at the cost of just an
additive $\mathrm{poly}(1/\varepsilon)$ in update time. This improves upon the
prior reduction of Gupta-Peng (FOCS 2013) which reduces the problem to a weight
range of $\varepsilon^{-O(1/\varepsilon)}$ with a multiplicative cost of
$O(\log n)$.
When combined with a reduction of Bernstein-Dudeja-Langley (STOC 2021) this
yields a reduction from dynamic $(1-\varepsilon)$-approximate MWM in bipartite
graphs with a weight range of $\mathrm{poly}(n)$ to dynamic
$(1-\varepsilon)$-approximate maximum cardinality matching in bipartite graphs
at the cost of a multiplicative $\mathrm{poly}(1/\varepsilon)$ in update time,
thereby resolving an open problem in [GP'13; BDL'21]. Additionally, we show
that our approach is amenable to MWM problems in streaming, shared-memory
work-depth, and massively parallel computation models. We also apply our
techniques to obtain an efficient dynamic algorithm for rounding weighted
fractional matchings in general graphs. Underlying our framework is a new
structural result about MWM that we call the "matching composition lemma" and
new dynamic matching subroutines that may be of independent interest.