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.
In this paper, we initiate the study of deterministic PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any characteristic, where $k$ and $\delta$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition that one of the summands at the top $\Sigma$ gate is squarefree.
Our techniques are purely algebro-geometric: they do not rely on Sylvester--Gallai-type theorems, and our PIT result holds over arbitrary fields.
The core of our proof is based on the normalization of algebraic varieties. Specifically, we carry out the analysis in the integral closure of a coordinate ring, which enjoys better algebraic properties than the original ring.
In this paper, we initiate the study of deterministic PIT for $\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any characteristic, where $k$ and $\delta$ are bounded. Our main result is a deterministic polynomial-time black-box PIT algorithm for $\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition that one of the summands at the top $\Sigma$ gate is squarefree.
Our techniques are purely algebro-geometric: they do not rely on Sylvester--Gallai-type theorems, and our PIT result holds over arbitrary fields.
The core of our proof is based on the normalization of algebraic varieties. Specifically, we carry out the analysis in the integral closure of a coordinate ring, which enjoys better algebraic properties than the original ring.
Multiaccuracy and multicalibration are multigroup fairness notions for
prediction that have found numerous applications in learning and computational
complexity. They can be achieved from a single learning primitive: weak
agnostic learning. Here we investigate the power of multiaccuracy as a learning
primitive, both with and without the additional assumption of calibration. We
find that multiaccuracy in itself is rather weak, but that the addition of
global calibration (this notion is called calibrated multiaccuracy) boosts its
power substantially, enough to recover implications that were previously known
only assuming the stronger notion of multicalibration.
We give evidence that multiaccuracy might not be as powerful as standard weak
agnostic learning, by showing that there is no way to post-process a
multiaccurate predictor to get a weak learner, even assuming the best
hypothesis has correlation $1/2$. Rather, we show that it yields a restricted
form of weak agnostic learning, which requires some concept in the class to
have correlation greater than $1/2$ with the labels. However, by also requiring
the predictor to be calibrated, we recover not just weak, but strong agnostic
learning.
A similar picture emerges when we consider the derivation of hardcore
measures from predictors satisfying multigroup fairness notions. On the one
hand, while multiaccuracy only yields hardcore measures of density half the
optimal, we show that (a weighted version of) calibrated multiaccuracy achieves
optimal density.
Our results yield new insights into the complementary roles played by
multiaccuracy and calibration in each setting. They shed light on why
multiaccuracy and global calibration, although not particularly powerful by
themselves, together yield considerably stronger notions.
Multiaccuracy and multicalibration are multigroup fairness notions for
prediction that have found numerous applications in learning and computational
complexity. They can be achieved from a single learning primitive: weak
agnostic learning. Here we investigate the power of multiaccuracy as a learning
primitive, both with and without the additional assumption of calibration. We
find that multiaccuracy in itself is rather weak, but that the addition of
global calibration (this notion is called calibrated multiaccuracy) boosts its
power substantially, enough to recover implications that were previously known
only assuming the stronger notion of multicalibration.
We give evidence that multiaccuracy might not be as powerful as standard weak
agnostic learning, by showing that there is no way to post-process a
multiaccurate predictor to get a weak learner, even assuming the best
hypothesis has correlation $1/2$. Rather, we show that it yields a restricted
form of weak agnostic learning, which requires some concept in the class to
have correlation greater than $1/2$ with the labels. However, by also requiring
the predictor to be calibrated, we recover not just weak, but strong agnostic
learning.
A similar picture emerges when we consider the derivation of hardcore
measures from predictors satisfying multigroup fairness notions. On the one
hand, while multiaccuracy only yields hardcore measures of density half the
optimal, we show that (a weighted version of) calibrated multiaccuracy achieves
optimal density.
Our results yield new insights into the complementary roles played by
multiaccuracy and calibration in each setting. They shed light on why
multiaccuracy and global calibration, although not particularly powerful by
themselves, together yield considerably stronger notions.
In this paper, we initiate the study of deterministic PIT for
$\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any
characteristic, where $k$ and $\delta$ are bounded. Our main result is a
deterministic polynomial-time black-box PIT algorithm for
$\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition
that one of the summands at the top $\Sigma$ gate is squarefree.
Our techniques are purely algebro-geometric: they do not rely on
Sylvester--Gallai-type theorems, and our PIT result holds over arbitrary
fields.
The core of our proof is based on the normalization of algebraic varieties.
Specifically, we carry out the analysis in the integral closure of a coordinate
ring, which enjoys better algebraic properties than the original ring.
In this paper, we initiate the study of deterministic PIT for
$\Sigma^{[k]}\Pi\Sigma\Pi^{[\delta]}$ circuits over fields of any
characteristic, where $k$ and $\delta$ are bounded. Our main result is a
deterministic polynomial-time black-box PIT algorithm for
$\Sigma^{[3]}\Pi\Sigma\Pi^{[\delta]}$ circuits, under the additional condition
that one of the summands at the top $\Sigma$ gate is squarefree.
Our techniques are purely algebro-geometric: they do not rely on
Sylvester--Gallai-type theorems, and our PIT result holds over arbitrary
fields.
The core of our proof is based on the normalization of algebraic varieties.
Specifically, we carry out the analysis in the integral closure of a coordinate
ring, which enjoys better algebraic properties than the original ring.
Ma and Huang recently proved that the PFC construction, introduced by Metger,
Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary
family PRU. Their proof developed a new path recording technique [MH24].
In this work, we show that a linear number of sequential repetitions of the
parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQSY+24], also
forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it
additionally satisfies strong security against adversaries making inverse
queries. This gives an alternative PRU construction, and provides another
instance demonstrating the power of the path recording technique. We also
discuss some further simplifications and implications.
Ma and Huang recently proved that the PFC construction, introduced by Metger,
Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary
family PRU. Their proof developed a new path recording technique [MH24].
In this work, we show that a linear number of sequential repetitions of the
parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQSY+24], also
forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it
additionally satisfies strong security against adversaries making inverse
queries. This gives an alternative PRU construction, and provides another
instance demonstrating the power of the path recording technique. We also
discuss some further simplifications and implications.
We demonstrate provable (sub)exponential quantum speedups in both discrete
and continuous optimization, achieved through simple and natural quantum
optimization algorithms, namely the quantum adiabatic algorithm for discrete
optimization and quantum Hamiltonian descent for continuous optimization. Our
result builds on the Gily\'en--Hastings--Vazirani (sub)exponential oracle
separation for adiabatic quantum computing. With a sequence of perturbative
reductions, we compile their construction into two standalone objective
functions, whose oracles can be directly leveraged by the plain adiabatic
evolution and Schr\"odinger operator evolution for discrete and continuous
optimization, respectively.
We demonstrate provable (sub)exponential quantum speedups in both discrete
and continuous optimization, achieved through simple and natural quantum
optimization algorithms, namely the quantum adiabatic algorithm for discrete
optimization and quantum Hamiltonian descent for continuous optimization. Our
result builds on the Gily\'en--Hastings--Vazirani (sub)exponential oracle
separation for adiabatic quantum computing. With a sequence of perturbative
reductions, we compile their construction into two standalone objective
functions, whose oracles can be directly leveraged by the plain adiabatic
evolution and Schr\"odinger operator evolution for discrete and continuous
optimization, respectively.
Authors: Abhibhav Garg, Rafael Oliveira, Akash Kumar Sengupta
We prove a non-linear Edelstein-Kelly theorem for polynomials of constant
degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and
generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic
polynomials to polynomials of any constant degree.
As a consequence of our result, we obtain constant rank bounds for depth-4
circuits with top fanin 3 and constant bottom fanin (denoted
$\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits) which compute the zero polynomial. This
settles a stronger form of Conjecture 1 in Gupta (2014) when $k=3$, for any
constant degree bound; additionally this also makes progress on Conjecture 28
in Beecken, Mittmann, and Saxena (Information \& Computation, 2013). Our rank
bounds, when combined with Theorem 2 in Beecken, Mittmann, and Saxena
(Information \& Computation, 2013) yield the first deterministic, polynomial
time PIT algorithm for $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits.
We prove a non-linear Edelstein-Kelly theorem for polynomials of constant
degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and
generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic
polynomials to polynomials of any constant degree.
As a consequence of our result, we obtain constant rank bounds for depth-4
circuits with top fanin 3 and constant bottom fanin (denoted
$\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits) which compute the zero polynomial. This
settles a stronger form of Conjecture 1 in Gupta (2014) when $k=3$, for any
constant degree bound; additionally this also makes progress on Conjecture 28
in Beecken, Mittmann, and Saxena (Information \& Computation, 2013). Our rank
bounds, when combined with Theorem 2 in Beecken, Mittmann, and Saxena
(Information \& Computation, 2013) yield the first deterministic, polynomial
time PIT algorithm for $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits.
Authors: Steven Chaplick, Grzegorz Gutowski, Tomasz Krawczyk
In a graph G, a k-attack A is any set of at most k vertices and l-defense D
is a set of at most l vertices. We say that defense D counters attack A if each
a in A can be matched to a distinct defender d in D with a equal to d or a
adjacent to d in G. In the defensive domination problem, we are interested in
deciding, for a graph G and positive integers k and l given on input, if there
exists an l-defense that counters every possible k-attack on G. Defensive
domination is a natural resource allocation problem and can be used to model
network robustness and security, disaster response strategies, and redundancy
designs.
The defensive domination problem is naturally in the complexity class
$\Sigma^P_2$. The problem was known to be NP-hard in general, and
polynomial-time algorithms were found for some restricted graph classes. In
this note we prove that the defensive domination problem is
$\Sigma^P_2$-complete. We also introduce a natural variant of the defensive
domination problem in which the defense is allowed to be a multiset of
vertices. This variant is also $\Sigma^P_2$-complete, but we show that it
admits a polynomial-time algorithm in the class of interval graphs. A similar
result was known for the original setting in the class of proper interval
graphs.
In a graph G, a k-attack A is any set of at most k vertices and l-defense D
is a set of at most l vertices. We say that defense D counters attack A if each
a in A can be matched to a distinct defender d in D with a equal to d or a
adjacent to d in G. In the defensive domination problem, we are interested in
deciding, for a graph G and positive integers k and l given on input, if there
exists an l-defense that counters every possible k-attack on G. Defensive
domination is a natural resource allocation problem and can be used to model
network robustness and security, disaster response strategies, and redundancy
designs.
The defensive domination problem is naturally in the complexity class
$\Sigma^P_2$. The problem was known to be NP-hard in general, and
polynomial-time algorithms were found for some restricted graph classes. In
this note we prove that the defensive domination problem is
$\Sigma^P_2$-complete. We also introduce a natural variant of the defensive
domination problem in which the defense is allowed to be a multiset of
vertices. This variant is also $\Sigma^P_2$-complete, but we show that it
admits a polynomial-time algorithm in the class of interval graphs. A similar
result was known for the original setting in the class of proper interval
graphs.
The Maker-Maker convention of positional games is played on a hypergraph
whose edges are interpreted as winning sets. Two players take turns picking a
previously unpicked vertex, aiming at being first to pick all the vertices of
some edge. Optimal play can only lead to a first player win or a draw, and
deciding between the two is known to be PSPACE-complete even for 6-uniform
hypergraphs. We establish PSPACE-completeness for hypergraphs of rank 4. As an
intermediary, we use the recently introduced achievement positional games, a
more general convention in which each player has their own winning sets (blue
and red). We show that deciding whether the blue player has a winning strategy
as the first player is PSPACE-complete even with blue edges of size 2 or 3 and
pairwise disjoint red edges of size 2. The result for hypergraphs of rank 4 in
the Maker-Maker convention follows as a simple corollary.
The Maker-Maker convention of positional games is played on a hypergraph
whose edges are interpreted as winning sets. Two players take turns picking a
previously unpicked vertex, aiming at being first to pick all the vertices of
some edge. Optimal play can only lead to a first player win or a draw, and
deciding between the two is known to be PSPACE-complete even for 6-uniform
hypergraphs. We establish PSPACE-completeness for hypergraphs of rank 4. As an
intermediary, we use the recently introduced achievement positional games, a
more general convention in which each player has their own winning sets (blue
and red). We show that deciding whether the blue player has a winning strategy
as the first player is PSPACE-complete even with blue edges of size 2 or 3 and
pairwise disjoint red edges of size 2. The result for hypergraphs of rank 4 in
the Maker-Maker convention follows as a simple corollary.
Holant problems are a general framework to study the computational complexity
of counting problems. It is a more expressive framework than counting
constraint satisfaction problems (CSP) which are in turn more expressive than
counting graph homomorphisms (GH). In this paper, we prove the first complexity
dichotomy of $\mathrm{Holant}_3(\mathcal{F})$ where $\mathcal{F}$ is an
arbitrary set of symmetric, real valued constraint functions on domain size
$3$. We give an explicit tractability criterion and prove that, if
$\mathcal{F}$ satisfies this criterion then $\mathrm{Holant}_3(\mathcal{F})$ is
polynomial time computable, and otherwise it is \#P-hard, with no intermediate
cases. We show that the geometry of the tensor decomposition of the constraint
functions plays a central role in the formulation as well as the structural
internal logic of the dichotomy.
Holant problems are a general framework to study the computational complexity
of counting problems. It is a more expressive framework than counting
constraint satisfaction problems (CSP) which are in turn more expressive than
counting graph homomorphisms (GH). In this paper, we prove the first complexity
dichotomy of $\mathrm{Holant}_3(\mathcal{F})$ where $\mathcal{F}$ is an
arbitrary set of symmetric, real valued constraint functions on domain size
$3$. We give an explicit tractability criterion and prove that, if
$\mathcal{F}$ satisfies this criterion then $\mathrm{Holant}_3(\mathcal{F})$ is
polynomial time computable, and otherwise it is \#P-hard, with no intermediate
cases. We show that the geometry of the tensor decomposition of the constraint
functions plays a central role in the formulation as well as the structural
internal logic of the dichotomy.
Authors: Herbert Edelsbrunner, Elizabeth Stephenson, Martin Hafskjold Thoresen
The medial axis of a smoothly embedded surface in $\mathbb{R}^3$ consists of
all points for which the Euclidean distance function on the surface has at
least two minima. We generalize this notion to the mid-sphere axis, which
consists of all points for which the Euclidean distance function has two
interchanging saddles that swap their partners in the pairing by persistent
homology. It offers a discrete-algebraic multi-scale approach to computing
ridge-like structures on the surface. As a proof of concept, an algorithm that
computes stair-case approximations of the mid-sphere axis is provided.
The medial axis of a smoothly embedded surface in $\mathbb{R}^3$ consists of
all points for which the Euclidean distance function on the surface has at
least two minima. We generalize this notion to the mid-sphere axis, which
consists of all points for which the Euclidean distance function has two
interchanging saddles that swap their partners in the pairing by persistent
homology. It offers a discrete-algebraic multi-scale approach to computing
ridge-like structures on the surface. As a proof of concept, an algorithm that
computes stair-case approximations of the mid-sphere axis is provided.
Discrete exterior calculus offers a coordinate-free discretization of
exterior calculus especially suited for computations on curved spaces. In this
work, we present a wedge product on 2-dimensional pseudomanifolds, whose faces
are any polygons. We prove that this polygonal wedge product is compatible with
the discrete exterior derivative in the sense that it satisfies the Leibniz
product rule. We thus extend previously studied discretizations of wedge
products from simplicial or quadrilateral meshes to general polygonal surface
meshes. We also prove that our discrete wedge product corresponds to a cup
product of cochains on 2-pseudomanifolds.
Discrete exterior calculus offers a coordinate-free discretization of
exterior calculus especially suited for computations on curved spaces. In this
work, we present a wedge product on 2-dimensional pseudomanifolds, whose faces
are any polygons. We prove that this polygonal wedge product is compatible with
the discrete exterior derivative in the sense that it satisfies the Leibniz
product rule. We thus extend previously studied discretizations of wedge
products from simplicial or quadrilateral meshes to general polygonal surface
meshes. We also prove that our discrete wedge product corresponds to a cup
product of cochains on 2-pseudomanifolds.
We give the first construction of explicit constant-degree lossless vertex
expanders. Specifically, for any $\varepsilon > 0$ and sufficiently large $d$,
we give an explicit construction of an infinite family of $d$-regular graphs
where every small set $S$ of vertices has $(1-\varepsilon)d|S|$ neighbors
(which implies $(1-2\varepsilon)d|S|$ unique-neighbors). Our results also
extend naturally to construct biregular bipartite graphs of any constant
imbalance, where small sets on each side have strong expansion guarantees. The
graphs we construct admit a free group action, and hence realize new families
of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding
algorithm.
Our construction is based on taking an appropriate product of a
constant-sized lossless expander with a base graph constructed from Ramanujan
Cayley cubical complexes.
We give the first construction of explicit constant-degree lossless vertex
expanders. Specifically, for any $\varepsilon > 0$ and sufficiently large $d$,
we give an explicit construction of an infinite family of $d$-regular graphs
where every small set $S$ of vertices has $(1-\varepsilon)d|S|$ neighbors
(which implies $(1-2\varepsilon)d|S|$ unique-neighbors). Our results also
extend naturally to construct biregular bipartite graphs of any constant
imbalance, where small sets on each side have strong expansion guarantees. The
graphs we construct admit a free group action, and hence realize new families
of quantum LDPC codes of Lin and M. Hsieh with a linear time decoding
algorithm.
Our construction is based on taking an appropriate product of a
constant-sized lossless expander with a base graph constructed from Ramanujan
Cayley cubical complexes.
Authors: Miroslaw Kowaluk, Andrzej Lingas, Mia Persson
Arslan showed that computing all-pairs Hamming distances is easily
reducible to arithmetic 0-1 matrix multiplication (IPL 2018). We
provide a reverse, linear-time reduction of arithmetic 0-1 matrix
multiplication to computing all-pairs distances in a Hamming space.
On the other hand, we present a fast randomized algorithm for
approximate all-pairs distances in a Hamming space. By combining it
with our reduction, we obtain also a fast randomized algorithm for
approximate 0-1 matrix multiplication. Next, we present an
output-sensitive randomized algorithm for a minimum spanning tree of
a set of points in a generalized Hamming space, the lower is the
cost of the minimum spanning tree the faster is our
algorithm. Finally, we provide $(2+\epsilon)$- approximation
algorithms for the $\ell$-center clustering and minimum-diameter
$\ell$-clustering problems in a Hamming space $\{0,1\}^d$ that are
substantially faster than the known $2$-approximation ones when both
$\ell$ and $d$ are super-logarithmic.
Arslan showed that computing all-pairs Hamming distances is easily
reducible to arithmetic 0-1 matrix multiplication (IPL 2018). We
provide a reverse, linear-time reduction of arithmetic 0-1 matrix
multiplication to computing all-pairs distances in a Hamming space.
On the other hand, we present a fast randomized algorithm for
approximate all-pairs distances in a Hamming space. By combining it
with our reduction, we obtain also a fast randomized algorithm for
approximate 0-1 matrix multiplication. Next, we present an
output-sensitive randomized algorithm for a minimum spanning tree of
a set of points in a generalized Hamming space, the lower is the
cost of the minimum spanning tree the faster is our
algorithm. Finally, we provide $(2+\epsilon)$- approximation
algorithms for the $\ell$-center clustering and minimum-diameter
$\ell$-clustering problems in a Hamming space $\{0,1\}^d$ that are
substantially faster than the known $2$-approximation ones when both
$\ell$ and $d$ are super-logarithmic.
Authors: Ilias Diakonikolas, Daniel M. Kane, Sushrut Karmalkar, Jasper C. H. Lee, Thanasis Pittas
We study the complexity of learning $k$-mixtures of Gaussians ($k$-GMMs) on
$\mathbb{R}^d$. This task is known to have complexity $d^{\Omega(k)}$ in full
generality. To circumvent this exponential lower bound on the number of
components, research has focused on learning families of GMMs satisfying
additional structural properties. A natural assumption posits that the
component weights are not exponentially small and that the components have the
same unknown covariance. Recent work gave a $d^{O(\log(1/w_{\min}))}$-time
algorithm for this class of GMMs, where $w_{\min}$ is the minimum weight. Our
first main result is a Statistical Query (SQ) lower bound showing that this
quasi-polynomial upper bound is essentially best possible, even for the special
case of uniform weights. Specifically, we show that it is SQ-hard to
distinguish between such a mixture and the standard Gaussian. We further
explore how the distribution of weights affects the complexity of this task.
Our second main result is a quasi-polynomial upper bound for the aforementioned
testing task when most of the weights are uniform while a small fraction of the
weights are potentially arbitrary.
We study the complexity of learning $k$-mixtures of Gaussians ($k$-GMMs) on
$\mathbb{R}^d$. This task is known to have complexity $d^{\Omega(k)}$ in full
generality. To circumvent this exponential lower bound on the number of
components, research has focused on learning families of GMMs satisfying
additional structural properties. A natural assumption posits that the
component weights are not exponentially small and that the components have the
same unknown covariance. Recent work gave a $d^{O(\log(1/w_{\min}))}$-time
algorithm for this class of GMMs, where $w_{\min}$ is the minimum weight. Our
first main result is a Statistical Query (SQ) lower bound showing that this
quasi-polynomial upper bound is essentially best possible, even for the special
case of uniform weights. Specifically, we show that it is SQ-hard to
distinguish between such a mixture and the standard Gaussian. We further
explore how the distribution of weights affects the complexity of this task.
Our second main result is a quasi-polynomial upper bound for the aforementioned
testing task when most of the weights are uniform while a small fraction of the
weights are potentially arbitrary.
Authors: Ilias Diakonikolas, Daniel M. Kane, Lisheng Ren
We study the algorithmic task of learning Boolean disjunctions in the
distribution-free agnostic PAC model. The best known agnostic learner for the
class of disjunctions over $\{0, 1\}^n$ is the $L_1$-polynomial regression
algorithm, achieving complexity $2^{\tilde{O}(n^{1/2})}$. This complexity bound
is known to be nearly best possible within the class of Correlational
Statistical Query (CSQ) algorithms. In this work, we develop an agnostic
learner for this concept class with complexity $2^{\tilde{O}(n^{1/3})}$. Our
algorithm can be implemented in the Statistical Query (SQ) model, providing the
first separation between the SQ and CSQ models in distribution-free agnostic
learning.
We study the algorithmic task of learning Boolean disjunctions in the
distribution-free agnostic PAC model. The best known agnostic learner for the
class of disjunctions over $\{0, 1\}^n$ is the $L_1$-polynomial regression
algorithm, achieving complexity $2^{\tilde{O}(n^{1/2})}$. This complexity bound
is known to be nearly best possible within the class of Correlational
Statistical Query (CSQ) algorithms. In this work, we develop an agnostic
learner for this concept class with complexity $2^{\tilde{O}(n^{1/3})}$. Our
algorithm can be implemented in the Statistical Query (SQ) model, providing the
first separation between the SQ and CSQ models in distribution-free agnostic
learning.
We study the problem of estimating the sum of $n$ elements, each with weight
$w(i)$, in a structured universe. Our goal is to estimate $W = \sum_{i=1}^n
w(i)$ within a $(1 \pm \epsilon)$ factor using a sublinear number of samples,
assuming weights are non-increasing, i.e., $w(1) \geq w(2) \geq \dots \geq
w(n)$. The sum estimation problem is well-studied under different access models
to the universe $U$. However, to the best of our knowledge, nothing is known
about the sum estimation problem using non-adaptive conditional sampling. In
this work, we explore the sum estimation problem using non-adaptive conditional
weighted and non-adaptive conditional uniform samples, assuming that the
underlying distribution ($D(i)=w(i)/W$) is monotone. We also extend our
approach to to the case where the underlying distribution of $U$ is unimodal.
Additionally, we consider support size estimation when $w(i) = 0$ or $w(i) \geq
W/n$, using hybrid sampling (both weighted and uniform) to access $U$. We
propose an algorithm to estimate $W$ under the non-increasing weight
assumption, using $O(\frac{1}{\epsilon^3} \log{n} + \frac{1}{\epsilon^6})$
non-adaptive weighted conditional samples and $O(\frac{1}{\epsilon^3} \log{n})$
uniform conditional samples. Our algorithm matches the $\Omega(\log{n})$ lower
bound by \cite{ACK15}. For unimodal distributions, the sample complexity
remains similar, with an additional $O(\log{n})$ evaluation queries to locate
the minimum weighted point in the domain. For estimating the support size $k$
of $U$, where weights are either $0$ or at least $W/n$, our algorithm uses
$O\big( \frac{\log^3(n/\epsilon)}{\epsilon^8} \cdot \log^4
\frac{\log(n/\epsilon)}{\epsilon} \big)$ uniform samples and $O\big(
\frac{\log(n/\epsilon)}{\epsilon^2} \cdot \log
\frac{\log(n/\epsilon)}{\epsilon} \big)$ weighted samples to output $\hat{k}$
satisfying $k - 2\epsilon n \leq \hat{k} \leq k + \epsilon n$.
We study the problem of estimating the sum of $n$ elements, each with weight
$w(i)$, in a structured universe. Our goal is to estimate $W = \sum_{i=1}^n
w(i)$ within a $(1 \pm \epsilon)$ factor using a sublinear number of samples,
assuming weights are non-increasing, i.e., $w(1) \geq w(2) \geq \dots \geq
w(n)$. The sum estimation problem is well-studied under different access models
to the universe $U$. However, to the best of our knowledge, nothing is known
about the sum estimation problem using non-adaptive conditional sampling. In
this work, we explore the sum estimation problem using non-adaptive conditional
weighted and non-adaptive conditional uniform samples, assuming that the
underlying distribution ($D(i)=w(i)/W$) is monotone. We also extend our
approach to to the case where the underlying distribution of $U$ is unimodal.
Additionally, we consider support size estimation when $w(i) = 0$ or $w(i) \geq
W/n$, using hybrid sampling (both weighted and uniform) to access $U$. We
propose an algorithm to estimate $W$ under the non-increasing weight
assumption, using $O(\frac{1}{\epsilon^3} \log{n} + \frac{1}{\epsilon^6})$
non-adaptive weighted conditional samples and $O(\frac{1}{\epsilon^3} \log{n})$
uniform conditional samples. Our algorithm matches the $\Omega(\log{n})$ lower
bound by \cite{ACK15}. For unimodal distributions, the sample complexity
remains similar, with an additional $O(\log{n})$ evaluation queries to locate
the minimum weighted point in the domain. For estimating the support size $k$
of $U$, where weights are either $0$ or at least $W/n$, our algorithm uses
$O\big( \frac{\log^3(n/\epsilon)}{\epsilon^8} \cdot \log^4
\frac{\log(n/\epsilon)}{\epsilon} \big)$ uniform samples and $O\big(
\frac{\log(n/\epsilon)}{\epsilon^2} \cdot \log
\frac{\log(n/\epsilon)}{\epsilon} \big)$ weighted samples to output $\hat{k}$
satisfying $k - 2\epsilon n \leq \hat{k} \leq k + \epsilon n$.
The metric $k$-median problem is a textbook clustering problem. As input, we
are given a metric space $V$ of size $n$ and an integer $k$, and our task is to
find a subset $S \subseteq V$ of at most $k$ `centers' that minimizes the total
distance from each point in $V$ to its nearest center in $S$.
Mettu and Plaxton [UAI'02] gave a randomized algorithm for $k$-median that
computes a $O(1)$-approximation in $\tilde O(nk)$ time. They also showed that
any algorithm for this problem with a bounded approximation ratio must have a
running time of $\Omega(nk)$. Thus, the running time of their algorithm is
optimal up to polylogarithmic factors.
For deterministic $k$-median, Guha et al.~[FOCS'00] gave an algorithm that
computes a $\text{poly}(\log (n/k))$-approximation in $\tilde O(nk)$ time,
where the degree of the polynomial in the approximation is unspecified. To the
best of our knowledge, this remains the state-of-the-art approximation of any
deterministic $k$-median algorithm with this running time.
This leads us to the following natural question: What is the best
approximation of a deterministic $k$-median algorithm with near-optimal running
time? We make progress in answering this question by giving a deterministic
algorithm that computes a $O(\log(n/k))$-approximation in $\tilde O(nk)$ time.
We also provide a lower bound showing that any deterministic algorithm with
this running time must have an approximation ratio of $\Omega(\log n/(\log k +
\log \log n))$, establishing a gap between the randomized and deterministic
settings for $k$-median.
The metric $k$-median problem is a textbook clustering problem. As input, we
are given a metric space $V$ of size $n$ and an integer $k$, and our task is to
find a subset $S \subseteq V$ of at most $k$ `centers' that minimizes the total
distance from each point in $V$ to its nearest center in $S$.
Mettu and Plaxton [UAI'02] gave a randomized algorithm for $k$-median that
computes a $O(1)$-approximation in $\tilde O(nk)$ time. They also showed that
any algorithm for this problem with a bounded approximation ratio must have a
running time of $\Omega(nk)$. Thus, the running time of their algorithm is
optimal up to polylogarithmic factors.
For deterministic $k$-median, Guha et al.~[FOCS'00] gave an algorithm that
computes a $\text{poly}(\log (n/k))$-approximation in $\tilde O(nk)$ time,
where the degree of the polynomial in the approximation is unspecified. To the
best of our knowledge, this remains the state-of-the-art approximation of any
deterministic $k$-median algorithm with this running time.
This leads us to the following natural question: What is the best
approximation of a deterministic $k$-median algorithm with near-optimal running
time? We make progress in answering this question by giving a deterministic
algorithm that computes a $O(\log(n/k))$-approximation in $\tilde O(nk)$ time.
We also provide a lower bound showing that any deterministic algorithm with
this running time must have an approximation ratio of $\Omega(\log n/(\log k +
\log \log n))$, establishing a gap between the randomized and deterministic
settings for $k$-median.
Authors: Lin Chen, Jiayi Lian, Yuchen Mao, Guochuan Zhang
We consider the classic Knapsack problem. Let $t$ and $\mathrm{OPT}$ be the
capacity and the optimal value, respectively. If one seeks a solution with
total profit at least $\mathrm{OPT}/(1 + \varepsilon)$ and total weight at most
$t$, then Knapsack can be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^2)$
time [Chen, Lian, Mao, and Zhang '24][Mao '24]. This running time is the best
possible (up to a logarithmic factor), assuming that $(\min,+)$-convolution
cannot be solved in truly subquadratic time [K\"unnemann, Paturi, and Schneider
'17][Cygan, Mucha, W\k{e}grzycki, and W{\l}odarczyk '19]. The same upper and
lower bounds hold if one seeks a solution with total profit at least
$\mathrm{OPT}$ and total weight at most $(1 + \varepsilon)t$. Therefore, it is
natural to ask the following question.
If one seeks a solution with total profit at least
$\mathrm{OPT}/(1+\varepsilon)$ and total weight at most $(1 + \varepsilon)t$,
can Knsapck be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^{2-\delta})$
time for some constant $\delta > 0$?
We answer this open question affirmatively by proposing an $\tilde{O}(n +
(\frac{1}{\varepsilon})^{7/4})$-time algorithm.
We consider the classic Knapsack problem. Let $t$ and $\mathrm{OPT}$ be the
capacity and the optimal value, respectively. If one seeks a solution with
total profit at least $\mathrm{OPT}/(1 + \varepsilon)$ and total weight at most
$t$, then Knapsack can be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^2)$
time [Chen, Lian, Mao, and Zhang '24][Mao '24]. This running time is the best
possible (up to a logarithmic factor), assuming that $(\min,+)$-convolution
cannot be solved in truly subquadratic time [K\"unnemann, Paturi, and Schneider
'17][Cygan, Mucha, W\k{e}grzycki, and W{\l}odarczyk '19]. The same upper and
lower bounds hold if one seeks a solution with total profit at least
$\mathrm{OPT}$ and total weight at most $(1 + \varepsilon)t$. Therefore, it is
natural to ask the following question.
If one seeks a solution with total profit at least
$\mathrm{OPT}/(1+\varepsilon)$ and total weight at most $(1 + \varepsilon)t$,
can Knsapck be solved in $\tilde{O}(n + (\frac{1}{\varepsilon})^{2-\delta})$
time for some constant $\delta > 0$?
We answer this open question affirmatively by proposing an $\tilde{O}(n +
(\frac{1}{\varepsilon})^{7/4})$-time algorithm.
In this paper, we study the $k$-center problem of uncertain points on a
graph. Given are an undirected graph $G = (V, E)$ and a set $\mathcal{P}$ of
$n$ uncertain points where each uncertain point with a non-negative weight has
$m$ possible locations on $G$ each associated with a probability. The problem
aims to find $k$ centers (points) on $G$ so as to minimize the maximum weighted
expected distance of uncertain points to their expected closest centers. No
previous work exist for the $k$-center problem of uncertain points on
undirected graphs. We propose exact algorithms that solve respectively the case
of $k=2$ in $O(|E|^2m^2n\log |E|mn\log mn )$ time and the problem with $k\geq
3$ in $O(\min\{|E|^km^kn^{k+1}k\log |E|mn\log m,
|E|^kn^\frac{k}{2}m^\frac{k^2}{2}\log |E|mn\})$ time, provided with the
distance matrix of $G$. In addition, an $O(|E|mn\log mn)$-time algorithmic
approach is given for the one-center case.
In this paper, we study the $k$-center problem of uncertain points on a
graph. Given are an undirected graph $G = (V, E)$ and a set $\mathcal{P}$ of
$n$ uncertain points where each uncertain point with a non-negative weight has
$m$ possible locations on $G$ each associated with a probability. The problem
aims to find $k$ centers (points) on $G$ so as to minimize the maximum weighted
expected distance of uncertain points to their expected closest centers. No
previous work exist for the $k$-center problem of uncertain points on
undirected graphs. We propose exact algorithms that solve respectively the case
of $k=2$ in $O(|E|^2m^2n\log |E|mn\log mn )$ time and the problem with $k\geq
3$ in $O(\min\{|E|^km^kn^{k+1}k\log |E|mn\log m,
|E|^kn^\frac{k}{2}m^\frac{k^2}{2}\log |E|mn\})$ time, provided with the
distance matrix of $G$. In addition, an $O(|E|mn\log mn)$-time algorithmic
approach is given for the one-center case.
Authors: Naima Tasnim, Atefeh Gilani, Lalitha Sankar, Oliver Kosut
We introduce a differentially private (DP) algorithm called reveal-or-obscure
(ROO) to generate a single representative sample from a dataset of $n$
observations drawn i.i.d. from an unknown discrete distribution $P$. Unlike
methods that add explicit noise to the estimated empirical distribution, ROO
achieves $\epsilon$-differential privacy by randomly choosing whether to
"reveal" or "obscure" the empirical distribution. While ROO is structurally
identical to Algorithm 1 proposed by Cheu and Nayak (arXiv:2412.10512), we
prove a strictly better bound on the sampling complexity than that established
in Theorem 12 of (arXiv:2412.10512). To further improve the privacy-utility
trade-off, we propose a novel generalized sampling algorithm called
Data-Specific ROO (DS-ROO), where the probability of obscuring the empirical
distribution of the dataset is chosen adaptively. We prove that DS-ROO
satisfies $\epsilon$-DP, and provide empirical evidence that DS-ROO can achieve
better utility under the same privacy budget of vanilla ROO.
We introduce a differentially private (DP) algorithm called reveal-or-obscure
(ROO) to generate a single representative sample from a dataset of $n$
observations drawn i.i.d. from an unknown discrete distribution $P$. Unlike
methods that add explicit noise to the estimated empirical distribution, ROO
achieves $\epsilon$-differential privacy by randomly choosing whether to
"reveal" or "obscure" the empirical distribution. While ROO is structurally
identical to Algorithm 1 proposed by Cheu and Nayak (arXiv:2412.10512), we
prove a strictly better bound on the sampling complexity than that established
in Theorem 12 of (arXiv:2412.10512). To further improve the privacy-utility
trade-off, we propose a novel generalized sampling algorithm called
Data-Specific ROO (DS-ROO), where the probability of obscuring the empirical
distribution of the dataset is chosen adaptively. We prove that DS-ROO
satisfies $\epsilon$-DP, and provide empirical evidence that DS-ROO can achieve
better utility under the same privacy budget of vanilla ROO.
Authors: Sina Bagheri Nezhad, Sayan Bandyapadhyay, Tianzhi Chen
In a seminal work, Chierichetti et al. introduced the $(t,k)$-fair clustering
problem: Given a set of red points and a set of blue points in a metric space,
a clustering is called fair if the number of red points in each cluster is at
most $t$ times and at least $1/t$ times the number of blue points in that
cluster. The goal is to compute a fair clustering with at most $k$ clusters
that optimizes certain objective function. Considering this problem, they
designed a polynomial-time $O(1)$- and $O(t)$-approximation for the $k$-center
and the $k$-median objective, respectively. Recently, Carta et al. studied this
problem with the sum-of-radii objective and obtained a
$(6+\epsilon)$-approximation with running time
$O((k\log_{1+\epsilon}(k/\epsilon))^kn^{O(1)})$, i.e., fixed-parameter
tractable in $k$. Here $n$ is the input size. In this work, we design the first
polynomial-time $O(1)$-approximation for $(t,k)$-fair clustering with the
sum-of-radii objective, improving the result of Carta et al. Our result places
sum-of-radii in the same group of objectives as $k$-center, that admit
polynomial-time $O(1)$-approximations. This result also implies a
polynomial-time $O(1)$-approximation for the Euclidean version of the problem,
for which an $f(k)\cdot n^{O(1)}$-time $(1+\epsilon)$-approximation was known
due to Drexler et al.. Here $f$ is an exponential function of $k$. We are also
able to extend our result to any arbitrary $\ell\ge 2$ number of colors when
$t=1$. This matches known results for the $k$-center and $k$-median objectives
in this case. The significant disparity of sum-of-radii compared to $k$-center
and $k$-median presents several complex challenges, all of which we
successfully overcome in our work. Our main contribution is a novel
cluster-merging-based analysis technique for sum-of-radii that helps us achieve
the constant-approximation bounds.
In a seminal work, Chierichetti et al. introduced the $(t,k)$-fair clustering
problem: Given a set of red points and a set of blue points in a metric space,
a clustering is called fair if the number of red points in each cluster is at
most $t$ times and at least $1/t$ times the number of blue points in that
cluster. The goal is to compute a fair clustering with at most $k$ clusters
that optimizes certain objective function. Considering this problem, they
designed a polynomial-time $O(1)$- and $O(t)$-approximation for the $k$-center
and the $k$-median objective, respectively. Recently, Carta et al. studied this
problem with the sum-of-radii objective and obtained a
$(6+\epsilon)$-approximation with running time
$O((k\log_{1+\epsilon}(k/\epsilon))^kn^{O(1)})$, i.e., fixed-parameter
tractable in $k$. Here $n$ is the input size. In this work, we design the first
polynomial-time $O(1)$-approximation for $(t,k)$-fair clustering with the
sum-of-radii objective, improving the result of Carta et al. Our result places
sum-of-radii in the same group of objectives as $k$-center, that admit
polynomial-time $O(1)$-approximations. This result also implies a
polynomial-time $O(1)$-approximation for the Euclidean version of the problem,
for which an $f(k)\cdot n^{O(1)}$-time $(1+\epsilon)$-approximation was known
due to Drexler et al.. Here $f$ is an exponential function of $k$. We are also
able to extend our result to any arbitrary $\ell\ge 2$ number of colors when
$t=1$. This matches known results for the $k$-center and $k$-median objectives
in this case. The significant disparity of sum-of-radii compared to $k$-center
and $k$-median presents several complex challenges, all of which we
successfully overcome in our work. Our main contribution is a novel
cluster-merging-based analysis technique for sum-of-radii that helps us achieve
the constant-approximation bounds.
Authors: George B. Mertzios, Hendrik Molter, Nils Morawietz, Paul G. Spirakis
A periodic temporal graph, in its simplest form, is a graph in which every
edge appears exactly once in the first $\Delta$ time steps, and then it
reappears recurrently every $\Delta$ time steps, where $\Delta$ is a given
period length. This model offers a natural abstraction of transportation
networks where each transportation link connects two destinations periodically.
From a network design perspective, a crucial task is to assign the time-labels
on the edges in a way that optimizes some criterion. In this paper we introduce
a very natural optimality criterion that captures how the temporal distances of
all vertex pairs are `stretched', compared to their physical distances, i.e.
their distances in the underlying static (non-temporal) graph. Given a static
graph $G$, the task is to assign to each edge one time-label between 1 and
$\Delta$ such that, in the resulting periodic temporal graph with
period~$\Delta$, the duration of the fastest temporal path from any vertex $u$
to any other vertex $v$ is at most $\alpha$ times the distance between $u$ and
$v$ in $G$. Here, the value of $\alpha$ measures how much the shortest paths
are allowed to be \emph{stretched} once we assign the periodic time-labels.
Our results span three different directions: First, we provide a series of
approximation and NP-hardness results. Second, we provide approximation and
fixed-parameter algorithms. Among them, we provide a simple polynomial-time
algorithm (the \textit{radius-algorithm}) which always guarantees an
approximation strictly smaller than $\Delta$, and which also computes the
optimum stretch in some cases. Third, we consider a parameterized local search
extension of the problem where we are given the temporal labeling of the graph,
but we are allowed to change the time-labels of at most $k$ edges; for this
problem we prove that it is W[2]-hard but admits an XP algorithm with respect
to $k$.
A periodic temporal graph, in its simplest form, is a graph in which every
edge appears exactly once in the first $\Delta$ time steps, and then it
reappears recurrently every $\Delta$ time steps, where $\Delta$ is a given
period length. This model offers a natural abstraction of transportation
networks where each transportation link connects two destinations periodically.
From a network design perspective, a crucial task is to assign the time-labels
on the edges in a way that optimizes some criterion. In this paper we introduce
a very natural optimality criterion that captures how the temporal distances of
all vertex pairs are `stretched', compared to their physical distances, i.e.
their distances in the underlying static (non-temporal) graph. Given a static
graph $G$, the task is to assign to each edge one time-label between 1 and
$\Delta$ such that, in the resulting periodic temporal graph with
period~$\Delta$, the duration of the fastest temporal path from any vertex $u$
to any other vertex $v$ is at most $\alpha$ times the distance between $u$ and
$v$ in $G$. Here, the value of $\alpha$ measures how much the shortest paths
are allowed to be \emph{stretched} once we assign the periodic time-labels.
Our results span three different directions: First, we provide a series of
approximation and NP-hardness results. Second, we provide approximation and
fixed-parameter algorithms. Among them, we provide a simple polynomial-time
algorithm (the \textit{radius-algorithm}) which always guarantees an
approximation strictly smaller than $\Delta$, and which also computes the
optimum stretch in some cases. Third, we consider a parameterized local search
extension of the problem where we are given the temporal labeling of the graph,
but we are allowed to change the time-labels of at most $k$ edges; for this
problem we prove that it is W[2]-hard but admits an XP algorithm with respect
to $k$.
Authors: Flavio Chierichetti, Mirko Giacchini, Alessandro Panconesi, Andrea Vattani
Online Bipartite Matching with random user arrival is a fundamental problem
in the online advertisement ecosystem. Over the last 30 years, many algorithms
and impossibility results have been developed for this problem. In particular,
the latest impossibility result was established by Manshadi, Oveis Gharan and
Saberi in 2011. Since then, several algorithms have been published in an effort
to narrow the gap between the upper and the lower bounds on the competitive
ratio.
In this paper we show that no algorithm can achieve a competitive ratio
better than $1- \frac e{e^e} = 0.82062\ldots$, improving upon the $0.823$ upper
bound presented in (Manshadi, Oveis Gharan and Saberi, SODA 2011). Our
construction is simple to state, accompanied by a fully analytic proof, and
yields a competitive ratio bound intriguingly similar to $1 - \frac1e$, the
optimal competitive ratio for the fully adversarial Online Bipartite Matching
problem.
Although the tightness of our upper bound remains an open question, we show
that our construction is extremal in a natural class of instances.
Online Bipartite Matching with random user arrival is a fundamental problem
in the online advertisement ecosystem. Over the last 30 years, many algorithms
and impossibility results have been developed for this problem. In particular,
the latest impossibility result was established by Manshadi, Oveis Gharan and
Saberi in 2011. Since then, several algorithms have been published in an effort
to narrow the gap between the upper and the lower bounds on the competitive
ratio.
In this paper we show that no algorithm can achieve a competitive ratio
better than $1- \frac e{e^e} = 0.82062\ldots$, improving upon the $0.823$ upper
bound presented in (Manshadi, Oveis Gharan and Saberi, SODA 2011). Our
construction is simple to state, accompanied by a fully analytic proof, and
yields a competitive ratio bound intriguingly similar to $1 - \frac1e$, the
optimal competitive ratio for the fully adversarial Online Bipartite Matching
problem.
Although the tightness of our upper bound remains an open question, we show
that our construction is extremal in a natural class of instances.
We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic polynomials to polynomials of any constant degree.
As a consequence of our result, we obtain constant rank bounds for depth-4 circuits with top fanin 3 and constant bottom fanin (denoted $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits) which compute the zero polynomial.
This settles a stronger form of Conjecture 1 in Gupta (2014) when $k=3$, for any constant degree bound; additionally this also makes progress on Conjecture 28 in Beecken, Mittmann, and Saxena (Information \& Computation, 2013). Our rank bounds, when combined with Theorem 2 in Beecken, Mittmann, and Saxena (Information \& Computation, 2013) yield the first deterministic, polynomial time PIT algorithm for $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits.
We prove a non-linear Edelstein-Kelly theorem for polynomials of constant degree, fully settling a stronger form of Conjecture 30 in Gupta (2014), and generalizing the main result of Peleg and Shpilka (STOC 2021) from quadratic polynomials to polynomials of any constant degree.
As a consequence of our result, we obtain constant rank bounds for depth-4 circuits with top fanin 3 and constant bottom fanin (denoted $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits) which compute the zero polynomial.
This settles a stronger form of Conjecture 1 in Gupta (2014) when $k=3$, for any constant degree bound; additionally this also makes progress on Conjecture 28 in Beecken, Mittmann, and Saxena (Information \& Computation, 2013). Our rank bounds, when combined with Theorem 2 in Beecken, Mittmann, and Saxena (Information \& Computation, 2013) yield the first deterministic, polynomial time PIT algorithm for $\Sigma^{3}\Pi\Sigma\Pi^{d}$ circuits.
In this post, we’ll discuss how Galois rings (a recent algebraic structure) improve the communication complexity of dishonest multiparty computation (MPC) protocols.Before we dive into MPC, I’ll take a brief detour to discuss how computation is usually modeled in cryptography. When cryptographers think about computation, they often think about circuits comprised of addition and multiplication gates. You may think ah so like boolean circuits? Nope, cryptographers love circuits over HUGE fields; in fact, the bigger the better! Fields are convenient to work with as 1) every element except for zero is invertible and 2) low-degree, non-zero polynomials have few roots. As such, we can often tie the security of cryptographic protocols directly to the size of the field (as we’ll see shortly). However, deep down, cryptographers really just want to work with circuits over the integers mod (), think /-bit unsigned integers. For ease of notation, we will use . Integer arithmetic (i.e. ) is exactly the arithmetic we already have on our cpus. Just think about how much modern software we could directly capture… but, OOF, is a pain to work with! Half of the elements are not invertible, and low-degree, non-zero polynomials can have TONs of roots (like [...]
In this post, we’ll discuss how Galois rings (a recent algebraic structure) improve the communication complexity of dishonest multiparty computation (MPC) protocols.
Before we dive into MPC, I’ll take a brief detour to discuss how computation is usually modeled in cryptography. When cryptographers think about computation, they often think about circuits comprised of addition and multiplication gates. You may think ah so like boolean circuits? Nope, cryptographers love circuits over HUGE fields; in fact, the bigger the better! Fields are convenient to work with as 1) every element except for zero is invertible and 2) low-degree, non-zero polynomials have few roots. As such, we can often tie the security of cryptographic protocols directly to the size of the field (as we’ll see shortly). However, deep down, cryptographers really just want to work with circuits over the integers mod (), think /-bit unsigned integers. For ease of notation, we will use . Integer arithmetic (i.e. ) is exactly the arithmetic we already have on our cpus. Just think about how much modern software we could directly capture… but, OOF, is a pain to work with! Half of the elements are not invertible, and low-degree, non-zero polynomials can have TONs of roots (like ). If only we had a ring with similar properties to fields that could also capture arithmetic. In fact, we do. GALOIS RINGS!
A Galois ring is a quotient ring for which is a monic polynomial of degree such that is an irreducible polynomial in . Here, we use , but Galois rings are described generally for for any prime . Informally, you can view the elements of as degree polynomials whose coefficients belong to and operations are performed . Galois rings have several nice properties:
1) fraction of elements are invertible [Wan03]. 2) is isomorphic to [Wan03]. 3) A non-zero polynomial with has at most roots [ACDEY19]. 4) There exists -linear maps called reverse multiplication friendly embeddings or RMFEs [EHLXY23].
Property 3) gives us a nice analog of the Schwartz-Zippel lemma, but over Galois rings instead (which are not integral domains)! Namely, . As we will see later, property 3) can help us catch cheaters and 4) will naturally embed arithmetic into arithmetic.
With that aside over, we now have enough to discuss MPC. Let be some ring (like , , ). Multiparty computation [BGW88, CCD88, GMW87, Yao86] is an interactive protocol between multiple parties, , who each have their own private inputs , respectively. They want to compute the output of some public circuit on their inputs. The catch is that no party should learn anything about the other parties private inputs, besides what is revealed by . Ideally, the amount of information the parties can learn is identical to as if they had just asked a trusted third party to do the computation. When all parties follow the protocol honestly, we know of simple MPC protocols (semi-honest MPC) where this trusted third party can be replaced purely with interaction between parties.
Unfortunately, it’s unrealistic to expect that all parties behave honestly. Some malicious parties could arbitrarily deviate from the protocol in an attempt to learn more information about the other parties’ private inputs. So, we need a way to catch when malicious parties misbehave and abort the whole protocol before information is leaked! There are two prevailing paradigms for constructing dishonest MPC:
We will focus on authenticated secret sharing in this post, and what goes wrong when working over . Consider an arbitrary element . An additive secret sharing of is a collection of uniformly sampled elements
For example, I can share my password (private input) with friends (parties possessing , respectively) in such a way that they can recover my password if all of them work together, but without this quorum, they locally can only see uniformly random nonsense. Additive secret shares are also linearly homomorphic; given shares and , parties can derive a share to by locally computing for any constant . This property is essential for constructing semi-honest MPC.
However, if a friend, , is malicious, they may try to mess up recovery by introducing some additive error to their share such that together the parties recover , which is not the correct value. The security of dishonest MPC protocols essentially boils down to catching when malicious parties introduce these additive errors to secret shares. But, how do we actually catch cheaters? During a setup phase, Parties will receive an additive secret sharing of an element , sampled uniformly from the ring, which is unknown to all parties. An authenticated secret share of is a pair of additive secret shares of both and . Intuitively, we can think of this additional share as an MAC (message authenticated code) and as a MAC key. To see why, let’s go over the recovery (opening) procedure. As before, let be a malicious party who wants to shift the opening by an additive error .
1) Parties broadcast their shares . 2) Parties locally compute claimed opening . 3) Honest parties locally compute . Dishonest party locally computes for some of their choice. 4) Parties broadcast their shares and locally check . If not, abort!
For a malicious party to succeed, they must guess such that . If is a field, we can trivially solve for . Thus, the malicious party must be able to guess ! Since is uniformly random and unknown to any party, we can bound the probability the malicious party succeeds with . With a large field (say ), this chance is vanishingly small. However, things go terribly wrong when we choose . Notably, there’s an explicit attack that has a chance of succeeding! The malicious party samples a random bit and choose . Observe where is the -th bit of . This is zero with probability !
Prior works [CDE+18, BBH+22] avoid this issue with by working over a larger ring where . In this setting, and authenticated share for (over the smaller ring) consists of additive shares where belongs to the larger ring. Now, the malicious party must guess such that . Let be the largest power of two that divides . We have that , which means the malicious party must guess at least -bits of the secret . Therefore, we can bound the probability of success by . Unfortunately, this technique sacrifices share size for better security! In particular, higher security requires higher communication overhead (only out of -bits are used meaningfully). Shoot…if only there was a better ring… [Insert heroic entrance!]
[EXY22, LXY24] avoid this tradeoff by setting the underlying ring to be a Galois ring . Leading to a protocol where communication does not scale with the level of security! Let’s perform similar analysis, but now over . Since , we have is a non-zero, degree- polynomial. Thus, by property 3), we have . Yay! We have a security when is large enough. An astute reader might ask: didn’t we want to capture computation over and not this weird ring ? And, they would be right!
Recall, informally, that we can think of as a set of degree polynomials with coefficients in . Maybe we can embed an into by treating it as a constant polynomial? Now, when we compute a circuit over , the constant terms in get added and multiplied together as needed. In fact, this strategy will work and is secure, but we just dug ourselves into a deeper hole! Since (a random degree polynomial), we have that the authenticated secret share size scales with , which itself scales with our security! SHOOT, the rate is terrible. Instead of more bits per share (as in the prior strategy over ), we have a multiplicative factor in communication! But all hope is not lost. [Insert second heroic entrance!]
Reverse multiplication friendly embeddings (RMFEs) (their theory was unified in EHLXY23) are maps with several amazing properties (among many others):
1) (Good rate) Let . There exists families of RMFEs such that is a constant (). 2) (Linearity) Both maps are -linear. In other words, for all , we have and . 3) (Multiplication Friendliness) For all , we have (where is multiplication and is element-wise product). 4) is injective, is surjective, , for all , and (internal direct sum).
Let’s break down why these properties enable communication to be independent of security. First off, the good rate of RMFEs helps us pack integers from into a single ring element in . Thus, now each ring element in can be thought of as integers (avoiding that blowup from the constant embedding). With linearity, additions over the ring naturally simulate additions over the vector space . In particular, if we embed two vectors into the ring, then the ring addition simulates the vector addition. Finally, multiplication friendliness similarly allows us to naturally simulate element-wise multiplication with multiplication over the Galois ring. Therefore, despite each ring element being the size, we do the work per element! Beyond the theoretical independence, [EXY22, LXY24] concretely show roughly less communication over prior work for high security applications (think -bits of statistical security).
In conclusion, we discussed what cryptographers like about different rings (fields, integers mod , and Galois rings), the relationship between MPC and authenticated secret sharing, how different rings affect the security and communication of MPC protocols, and how choosing Galois rings can avoid communication blowups by packing more work into each element. Of course, I skipped over many details including, but not limited to, how to construct MPC from authenticated secret sharing, why security reduces to catching bad openings, why Galois rings have such few roots, and how RMFEs are constructed. I suggest readers who are interested to refer to the works referenced!
Acknowledgements: I wrote this blog post as a part of my qualifying exam. Thank you to Mary Wootters, Dan Boneh, and Clark Barrett for being on my quals committee and occasional chats about algebraic geometry. Special thanks to the Applied Crypto group for their continual support during my quals prep.
We study the computational complexity of fundamental problems over the
$p$-adic numbers ${\mathbb Q}_p$ and the $p$-adic integers ${\mathbb Z}_p$.
Gu\'epin, Haase, and Worrell proved that checking satisfiability of systems of
linear equations combined with valuation constraints of the form $v_p(x) = c$
for $p \geq 5$ is NP-complete (both over ${\mathbb Z}_p$ and over ${\mathbb
Q}_p$), and left the cases $p=2$ and $p=3$ open. We solve their problem by
showing that the problem is NP-complete for ${\mathbb Z}_3$ and for ${\mathbb
Q}_3$, but that it is in P for ${\mathbb Z}_2$ and for ${\mathbb Q}_2$. We also
present different polynomial-time algorithms for solvability of systems of
linear equations in ${\mathbb Q}_p$ with either constraints of the form $v_p(x)
\leq c$ or of the form $v_p(x)\geq c$ for $c \in {\mathbb Z}$. Finally, we show
how our algorithms can be used to decide in polynomial time the satisfiability
of systems of (strict and non-strict) linear inequalities over ${\mathbb Q}$
together with valuation constraints $v_p(x) \geq c$ for several different prime
numbers $p$ simultaneously.
We study the computational complexity of fundamental problems over the
$p$-adic numbers ${\mathbb Q}_p$ and the $p$-adic integers ${\mathbb Z}_p$.
Gu\'epin, Haase, and Worrell proved that checking satisfiability of systems of
linear equations combined with valuation constraints of the form $v_p(x) = c$
for $p \geq 5$ is NP-complete (both over ${\mathbb Z}_p$ and over ${\mathbb
Q}_p$), and left the cases $p=2$ and $p=3$ open. We solve their problem by
showing that the problem is NP-complete for ${\mathbb Z}_3$ and for ${\mathbb
Q}_3$, but that it is in P for ${\mathbb Z}_2$ and for ${\mathbb Q}_2$. We also
present different polynomial-time algorithms for solvability of systems of
linear equations in ${\mathbb Q}_p$ with either constraints of the form $v_p(x)
\leq c$ or of the form $v_p(x)\geq c$ for $c \in {\mathbb Z}$. Finally, we show
how our algorithms can be used to decide in polynomial time the satisfiability
of systems of (strict and non-strict) linear inequalities over ${\mathbb Q}$
together with valuation constraints $v_p(x) \geq c$ for several different prime
numbers $p$ simultaneously.
The class $NP$ can be defined by the means of Monadic Second-Order logic
going back to Fagin and Feder-Vardi, and also by forbidden expanded
substructures (cf. lifts and shadows of Kun and Ne\v{s}et\v{r}il).
Consequently, for such problems there is no dichotomy, unlike for $CSP$'s. We
prove that ordering problems for graphs defined by finitely many forbidden
ordered subgraphs still capture the class $NP$. In particular, we refute a
conjecture of Hell, Mohar and Rafiey that dichotomy holds for this class. On
the positive side, we confirm the conjecture of Duffus, Ginn and R\"odl that
ordering problems defined by one single biconnected ordered graph are
$NP$-complete but for the ordered complete graph. An interesting feature
appeared and was noticed several times. For finite sets of biconnected patterns
(which may be colored structures or ordered structures) complexity dichotomy
holds. A principal tool for obtaining this result is known as the Sparse
Incomparability Lemma, a classical result in the theory of homomorphisms of
graphs and structures. We prove it here in the setting of ordered graphs as a
Temporal Sparse Incomparability Lemma for orderings. Interestingly, our proof
involves the Lov\'asz Local Lemma.
The class $NP$ can be defined by the means of Monadic Second-Order logic
going back to Fagin and Feder-Vardi, and also by forbidden expanded
substructures (cf. lifts and shadows of Kun and Ne\v{s}et\v{r}il).
Consequently, for such problems there is no dichotomy, unlike for $CSP$'s. We
prove that ordering problems for graphs defined by finitely many forbidden
ordered subgraphs still capture the class $NP$. In particular, we refute a
conjecture of Hell, Mohar and Rafiey that dichotomy holds for this class. On
the positive side, we confirm the conjecture of Duffus, Ginn and R\"odl that
ordering problems defined by one single biconnected ordered graph are
$NP$-complete but for the ordered complete graph. An interesting feature
appeared and was noticed several times. For finite sets of biconnected patterns
(which may be colored structures or ordered structures) complexity dichotomy
holds. A principal tool for obtaining this result is known as the Sparse
Incomparability Lemma, a classical result in the theory of homomorphisms of
graphs and structures. We prove it here in the setting of ordered graphs as a
Temporal Sparse Incomparability Lemma for orderings. Interestingly, our proof
involves the Lov\'asz Local Lemma.
Forgetting a specific belief revision episode may not erase information
because the other revisions may provide the same information or allow to deduce
it. Whether it does was proved coNP-hard for sequence of two arbitrary
lexicographic revision or arbitrarily long lexicographic Horn revision. A
polynomial algorithm is presented for the case of two Horn revision.
Heterogeneous sequences of revisions were proved to belong in Delta2. Their
previously proved coNP-hardness is enhanced by a proof of NP-hardness.
Forgetting a specific belief revision episode may not erase information
because the other revisions may provide the same information or allow to deduce
it. Whether it does was proved coNP-hard for sequence of two arbitrary
lexicographic revision or arbitrarily long lexicographic Horn revision. A
polynomial algorithm is presented for the case of two Horn revision.
Heterogeneous sequences of revisions were proved to belong in Delta2. Their
previously proved coNP-hardness is enhanced by a proof of NP-hardness.
Authors: Péter Ágoston, Adrian Dumitrescu, Arsenii Sagdeev, Karamjeet Singh, Ji Zeng
For a positive integer $k$ and an ordered set of $n$ points in the plane,
define its k-sector ordered Yao graphs as follows. Divide the plane around each
point into $k$ equal sectors and draw an edge from each point to its closest
predecessor in each of the $k$ sectors. We analyze several natural parameters
of these graphs. Our main results are as follows:
I) Let $d_k(n)$ be the maximum integer so that for every $n$-element point
set in the plane, there exists an order such that the corresponding $k$-sector
ordered Yao graph has maximum degree at least $d_k(n)$. We show that
$d_k(n)=n-1$ if $k=4$ or $k \ge 6$, and provide some estimates for the
remaining values of $k$. Namely, we show that $d_1(n) = \Theta( \log_2n )$;
$\frac{1}{2}(n-1) \le d_3(n) \le 5\left\lceil\frac{n}{6}\right\rceil-1$;
$\frac{2}{3}(n-1) \le d_5(n) \le n-1$;
II) Let $e_k(n)$ be the minimum integer so that for every $n$-element point
set in the plane, there exists an order such that the corresponding $k$-sector
ordered Yao graph has at most $e_k(n)$ edges. Then
$e_k(n)=\left\lceil\frac{k}{2}\right\rceil\cdot n-o(n)$.
III) Let $w_k$ be the minimum integer so that for every point set in the
plane, there exists an order such that the corresponding $k$-sector ordered Yao
graph has clique number at most $w_k$. Then $\lceil\frac{k}{2}\rceil \le w_k\le
\lceil\frac{k}{2}\rceil+1$.
All the orders mentioned above can be constructed effectively.
For a positive integer $k$ and an ordered set of $n$ points in the plane,
define its k-sector ordered Yao graphs as follows. Divide the plane around each
point into $k$ equal sectors and draw an edge from each point to its closest
predecessor in each of the $k$ sectors. We analyze several natural parameters
of these graphs. Our main results are as follows:
I) Let $d_k(n)$ be the maximum integer so that for every $n$-element point
set in the plane, there exists an order such that the corresponding $k$-sector
ordered Yao graph has maximum degree at least $d_k(n)$. We show that
$d_k(n)=n-1$ if $k=4$ or $k \ge 6$, and provide some estimates for the
remaining values of $k$. Namely, we show that $d_1(n) = \Theta( \log_2n )$;
$\frac{1}{2}(n-1) \le d_3(n) \le 5\left\lceil\frac{n}{6}\right\rceil-1$;
$\frac{2}{3}(n-1) \le d_5(n) \le n-1$;
II) Let $e_k(n)$ be the minimum integer so that for every $n$-element point
set in the plane, there exists an order such that the corresponding $k$-sector
ordered Yao graph has at most $e_k(n)$ edges. Then
$e_k(n)=\left\lceil\frac{k}{2}\right\rceil\cdot n-o(n)$.
III) Let $w_k$ be the minimum integer so that for every point set in the
plane, there exists an order such that the corresponding $k$-sector ordered Yao
graph has clique number at most $w_k$. Then $\lceil\frac{k}{2}\rceil \le w_k\le
\lceil\frac{k}{2}\rceil+1$.
All the orders mentioned above can be constructed effectively.
Authors: Thijs van der Horst, Marc van Kreveld, Tim Ophelders, Bettina Speckmann
Let $P$ be a polygon with $k$ vertices. Let $R$ and $B$ be two simple,
interior disjoint curves on the boundary of $P$, with $n$ and $m$ vertices. We
show how to compute the Fr\'echet distance between $R$ and $B$ using the
geodesic $L_1$-distance in $P$ in $\mathcal{O}(k \log nm + (n+m) (\log^2 nm
\log k + \log^4 nm))$ time.
Let $P$ be a polygon with $k$ vertices. Let $R$ and $B$ be two simple,
interior disjoint curves on the boundary of $P$, with $n$ and $m$ vertices. We
show how to compute the Fr\'echet distance between $R$ and $B$ using the
geodesic $L_1$-distance in $P$ in $\mathcal{O}(k \log nm + (n+m) (\log^2 nm
\log k + \log^4 nm))$ time.
The Hausdorff distance is a fundamental metric with widespread applications
across various fields. However, its computation remains computationally
expensive, especially for large-scale datasets. In this work, we present
RT-HDIST, the first Hausdorff distance algorithm accelerated by ray-tracing
cores (RT-cores). By reformulating the Hausdorff distance problem as a series
of nearest-neighbor searches and introducing a novel quantized index space,
RT-HDIST achieves significant reductions in computational overhead while
maintaining exact results. Extensive benchmarks demonstrate up to a
two-order-of-magnitude speedup over prior state-of-the-art methods,
underscoring RT-HDIST's potential for real-time and large-scale applications.
The Hausdorff distance is a fundamental metric with widespread applications
across various fields. However, its computation remains computationally
expensive, especially for large-scale datasets. In this work, we present
RT-HDIST, the first Hausdorff distance algorithm accelerated by ray-tracing
cores (RT-cores). By reformulating the Hausdorff distance problem as a series
of nearest-neighbor searches and introducing a novel quantized index space,
RT-HDIST achieves significant reductions in computational overhead while
maintaining exact results. Extensive benchmarks demonstrate up to a
two-order-of-magnitude speedup over prior state-of-the-art methods,
underscoring RT-HDIST's potential for real-time and large-scale applications.
In the Telephone Broadcast problem we are given a graph $G=(V,E)$ with a
designated source vertex $s\in V$. Our goal is to transmit a message, which is
initially known only to $s$, to all vertices of the graph by using a process
where in each round an informed vertex may transmit the message to one of its
uninformed neighbors. The optimization objective is to minimize the number of
rounds.
Following up on several recent works, we investigate the structurally
parameterized complexity of Telephone Broadcast. In particular, we first
strengthen existing NP-hardness results by showing that the problem remains
NP-complete on graphs of bounded tree-depth and also on cactus graphs which are
one vertex deletion away from being path forests. Motivated by this (severe)
hardness, we study several other parameterizations of the problem and obtain
FPT algorithms parameterized by vertex integrity (generalizing a recent FPT
algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS
2024]) and by distance to clique, as well as FPT approximation algorithms
parameterized by clique-cover and cluster vertex deletion. Furthermore, we
obtain structural results that relate the length of the optimal broadcast
protocol of a graph $G$ with its pathwidth and tree-depth. By presenting a
substantial improvement over the best previously known bound for pathwidth
(Aminian, Kamali, Seyed-Javadi, and Sumedha [arXiv 2025]) we exponentially
improve the approximation ratio achievable in polynomial time on graphs of
bounded pathwidth from $\mathcal{O}(4^\mathrm{pw})$ to
$\mathcal{O}(\mathrm{pw})$.
In the Telephone Broadcast problem we are given a graph $G=(V,E)$ with a
designated source vertex $s\in V$. Our goal is to transmit a message, which is
initially known only to $s$, to all vertices of the graph by using a process
where in each round an informed vertex may transmit the message to one of its
uninformed neighbors. The optimization objective is to minimize the number of
rounds.
Following up on several recent works, we investigate the structurally
parameterized complexity of Telephone Broadcast. In particular, we first
strengthen existing NP-hardness results by showing that the problem remains
NP-complete on graphs of bounded tree-depth and also on cactus graphs which are
one vertex deletion away from being path forests. Motivated by this (severe)
hardness, we study several other parameterizations of the problem and obtain
FPT algorithms parameterized by vertex integrity (generalizing a recent FPT
algorithm parameterized by vertex cover by Fomin, Fraigniaud, and Golovach [TCS
2024]) and by distance to clique, as well as FPT approximation algorithms
parameterized by clique-cover and cluster vertex deletion. Furthermore, we
obtain structural results that relate the length of the optimal broadcast
protocol of a graph $G$ with its pathwidth and tree-depth. By presenting a
substantial improvement over the best previously known bound for pathwidth
(Aminian, Kamali, Seyed-Javadi, and Sumedha [arXiv 2025]) we exponentially
improve the approximation ratio achievable in polynomial time on graphs of
bounded pathwidth from $\mathcal{O}(4^\mathrm{pw})$ to
$\mathcal{O}(\mathrm{pw})$.
Authors: Dankrad Feist, Gottfried Herold, Mark Simkin, Benedikt Wagner
Data Availability Sampling (DAS), a central component of Ethereum's roadmap,
enables clients to verify data availability without requiring any single client
to download the entire dataset. DAS operates by having clients randomly
retrieve individual symbols of erasure-encoded data from a peer-to-peer
network. While the cryptographic and encoding aspects of DAS have recently
undergone formal analysis, the peer-to-peer networking layer remains
underexplored, with a lack of security definitions and efficient, provably
secure constructions.
In this work, we address this gap by introducing a novel distributed data
structure that can serve as the networking layer for DAS, which we call
\emph{robust distributed arrays}. That is, we rigorously define a robustness
property of a distributed data structure in an open permissionless network,
that mimics a collection of arrays.
Then, we give a simple and efficient construction and formally prove its
robustness. Notably, every individual node is required to store only small
portions of the data, and accessing array positions incurs minimal latency. The
robustness of our construction relies solely on the presence of a minimal
\emph{absolute} number of honest nodes in the network. In particular, we avoid
any honest majority assumption.
Beyond DAS, we anticipate that robust distributed arrays can have wider
applications in distributed systems.
Data Availability Sampling (DAS), a central component of Ethereum's roadmap,
enables clients to verify data availability without requiring any single client
to download the entire dataset. DAS operates by having clients randomly
retrieve individual symbols of erasure-encoded data from a peer-to-peer
network. While the cryptographic and encoding aspects of DAS have recently
undergone formal analysis, the peer-to-peer networking layer remains
underexplored, with a lack of security definitions and efficient, provably
secure constructions.
In this work, we address this gap by introducing a novel distributed data
structure that can serve as the networking layer for DAS, which we call
\emph{robust distributed arrays}. That is, we rigorously define a robustness
property of a distributed data structure in an open permissionless network,
that mimics a collection of arrays.
Then, we give a simple and efficient construction and formally prove its
robustness. Notably, every individual node is required to store only small
portions of the data, and accessing array positions incurs minimal latency. The
robustness of our construction relies solely on the presence of a minimal
\emph{absolute} number of honest nodes in the network. In particular, we avoid
any honest majority assumption.
Beyond DAS, we anticipate that robust distributed arrays can have wider
applications in distributed systems.
Authors: Zhiyi Huang, Chui Shan Lee, Xinkai Shu, Zhaozi Wang
We study the online allocation of divisible items to $n$ agents with additive
valuations for $p$-mean welfare maximization, a problem introduced by Barman,
Khan, and Maiti~(2022). Our algorithmic and hardness results characterize the
optimal competitive ratios for the entire spectrum of $-\infty \le p \le 1$.
Surprisingly, our improved algorithms for all $p \le \frac{1}{\log n}$ are
simply the greedy algorithm for the Nash welfare, supplemented with two
auxiliary components to ensure all agents have non-zero utilities and to help a
small number of agents with low utilities. In this sense, the long arm of
Nashian allocation achieves near-optimal competitive ratios not only for Nash
welfare but also all the way to egalitarian welfare.
We study the online allocation of divisible items to $n$ agents with additive
valuations for $p$-mean welfare maximization, a problem introduced by Barman,
Khan, and Maiti~(2022). Our algorithmic and hardness results characterize the
optimal competitive ratios for the entire spectrum of $-\infty \le p \le 1$.
Surprisingly, our improved algorithms for all $p \le \frac{1}{\log n}$ are
simply the greedy algorithm for the Nash welfare, supplemented with two
auxiliary components to ensure all agents have non-zero utilities and to help a
small number of agents with low utilities. In this sense, the long arm of
Nashian allocation achieves near-optimal competitive ratios not only for Nash
welfare but also all the way to egalitarian welfare.
I recently revisited the Wikipedia article on normal spanning trees, rooted spanning trees of infinite undirected graphs that act like depth-first search trees in the sense that every non-tree edge of the graph connects an ancestor to a descendant. They exist in every connected countable undirected graph, but cannot always be generated by a depth-first search. It occurred to me to wonder: in which connected countable undirected graphs is it possible for a depth-first search to visit all vertices? It turns out to be possible if and only if the graph has one of the following two connectivity properties. Either:
I recently revisited the Wikipedia article on normal spanning trees, rooted spanning trees of infinite undirected graphs that act like depth-first search trees in the sense that every non-tree edge of the graph connects an ancestor to a descendant. They exist in every connected countable undirected graph, but cannot always be generated by a depth-first search. It occurred to me to wonder: in which connected countable undirected graphs is it possible for a depth-first search to visit all vertices? It turns out to be possible if and only if the graph has one of the following two connectivity properties. Either:
there exists a finite path \(P\) whose removal splits the remaining subgraph into infinitely many finite connected components, all but finitely many of which are adjacent to the endpoint of the path, or
deleting any finite path splits the remaining subgraph into a single infinite component and finitely many finite connected components.
If path \(P\) exists, we can guide a depth first search as follows: start at the other end of the path. Then, whenever the remaining unexplored vertices have a component adjacent to the current search vertex, start a recursive finite depth first search in one of these components, the one containing the earliest unexplored vertex in an enumeration of the graph’s vertices. Otherwise, take one more step along \(P\). This choice of which component to explore next ensures that every component will eventually be visited by the search.
In the second case, choose an arbitrary root for the depth first search, and then, at each step, while there is a finite component adjacent to the endpoint of the current search, chose one arbitrarily and explore it using a recursive finite depth first search. If there are no adjacent finite components, step into the infinite component along an edge that reduces the distance to the earliest unexplored vertex. Every finite component left by removing the depth-first search path will eventually be visited, from the last vertex adjacent to it on the search path, and the strategy of moving towards the earliest unexplored vertex ensures that the vertices that remain in the infinite component will also eventually be visited.
It remains to show that every graph that can be completely searched has one of these two properties. Consider any depth-first search that explores the whole graph. If there is a vertex \(v\) that is returned to infinitely often, then the depth-first search path to that vertex is a path \(P\) whose removal splits the remaining subgraph into infinitely many finite connected components: the components formed by the vertices between each repeat visit to \(v\), and possibly some finitely many earlier components. So when \(v\) exists, the graph mast have the first of the two connectivity properties.
On the other hand, suppose that no vertex is repeated infinitely often. Find an infinite ray \(R\) in the depth-first search tree that, from each vertex \(v\) in the path (starting from the root) chooses the next vertex in the ray to be the last vertex explored from \(v\). If any finite path \(P\) is removed from the graph, \(P\) and its depth-first ancestors can only cover finitely many vertices of \(R\). If \(P\) is removed, the rest of \(R\) and the finite branches of the depth-first search tree explored between repetitions along the rest of \(R\) all belong to a single infinite component. There are only finitely many other vertices which can form only finitely many finite components. So the graph must have the second of the two connectivity properties.
This may well all be known; I didn’t search very hard for prior work and my searches mostly turned up material on the more general normal spanning trees. If it is known, I would appreciate pointers to where it might be published.
Luca Trevisan I’m reblogging here a beautiful post by Luca Trevisan from his blog “In Theory”. The original post appeared a year ago in April 2024. A few weeks after this post was published, Luca sadly passed away at the … Continue reading →
I’m reblogging here a beautiful post by Luca Trevisan from his blog “In Theory”. The original post appeared a year ago in April 2024. A few weeks after this post was published, Luca sadly passed away at the age of 52.
In this post, Luca masterfully describes the resolution of Feige’s conjecture regarding Moore’s bound for hypergraphs. The conjecture was proved by Guruswami, Kothari and Manohar and the post described a simplified solution by Hsieh, Kothari and Mohanty.
Luca’s blog “In theory” began in March 2006 with a story about a coyote found in Central Park. Over the years, it featured many excellent mathematical posts, great posts about places— stories from China, Italy, San Francisco, and other places, including a tale with a moral from his 2014 visit to Jerusalem. The blog also touched on food, philosophy, women in science (humorously categorized as “Larry Sammers”), history, politics and more.
In 2012 Luca solicited essays from gay and lesbian colleagues on the occasion of the Turing centennial, resulting in ten important and moving posts on his blog. For more about Luca Trevisan see here, here and here.
One word about the mathematics: the proof of Feige’s conjecture involves Kikuchi graphs, which originated in the work of physicist Ryoichi Kikuchi. Let be positive integers with . Given a -uniform hypergraph on a vertex set , the Kikuchi graph associated with (and parameter ), is defined as follows: its vertices are -subsets of , and two vertices are adjacent if their symmetric difference forms a hyperedge of .
Datafication, online societies, and the war on academia.
Earlier this month, I participated in a lively discussion with Marion Fourcade about her excellent new book with Kieran Healy, The Ordinal Society. This was part of a series of engaging AI & Society salons organized by Irene Chen, Colleen Chien, and Deb Raji at Berkeley. I intended to blog about this when it happened, but got sidelined by a combination of some fun extraacademic activities and a head cold.
The Ordinal Society is primarily a critique of platform capitalism, the sorting it induces upon us, and how people act to please this algorithmic distortion of their behavior. But, wearing my predilections on my sleeve, I read it as an insightful qualitative critique of quantitative social science. Certainly, online platforms are implementing behavioral economics and social regression at scale. But issues with this quantified mindset manifest with small n too. The societal structures induced by deep learning algorithms and their classification errors differ in degree from those of antecedent regression methods. It is the quantification and quantization that are the root cause of the troubling feedback loops examined in the book.
One passage from the book that captures the heart of the critique makes an argument only controversial to those who have been too steeped in the mindset of overquantification
“As social phenomena, naming and ranking are much more general than quantification. Catechisms, shibboleths, purity regimes, ritual compliance, degradation ceremonies—in short, symbolically infused distinction making in all its forms—can serve in the place of numerical measures of position. Insofar as they are about distinguishing better from worse, as opposed to simply affirming the uniqueness of every single thing in the world, qualitative modes of classification can be as powerfully disciplining as quantitative ones.”
A quantitative mindset would assert instead that naming and ranking are quantitative. This mindset asserts that elicitation of preferences is quantifying. Preferences are just another way of describing “utility,” and we can construct optimal actions just by laying out our rankings in a systematic way.
This is the modern economic view, crystallized in post-war applied mathematics. In the computer age, we decided that ranking things, listing preferences, and then acting on those preferences was formalizable as mathematics. But Fourcade and Healy remind us that people and societies rank, classify, and choose without the formal scaffolding of Bayesian decision theory. And they have done so throughout history.
Healy and Fourcade continue:
“What is of real interest is the fusion of socially fundamental processes of naming and ranking with novel tools and data for carrying out those tasks. Large-scale measurement allows for thinking about scores and ranks through the lens of small differences and high dimensionality. What does it mean for computers to intervene in the business of seeing and organizing society?”
It’s always interesting how the quantitative person sees paradoxes as a math challenge and not a suggestion that quantification is a language game, and that the mathematical language is limited just like qualitative language.
I was thinking about this recently as I was working my way through Paul Meehl’s posthumous monograph, The Seven Sacred Cows of Academia, summarizing Meehl’s thoughts on how to make higher education more cost effective. Given the vicious war on higher education being waged by the Trump administration, I’ve been reading more about the long history of right-wing agitation against the academy and the associated academic responses. Every time, you’ll find academics writing their version of the Onion article “The Worst Person You Know Just Made A Great Point.” Here’s a great recent example by Anna Krylov, where I agree with everything the author writes, even though saying these things out loud right now only further imperils our institutions. I’ll blog about Meehl’s version of this meme once I’ve worked my way through the book (it’s 180 rambly pages).
I got stuck at the end of the introduction, where Meehl writes a six-page screed against those unwilling to quantify academic research merit, entitled “Miscounting by Pretending Not to Count.”
“When one suggests that some sort of composite index of these plausible criteria of scholarly merit should be used by the institutional decision-maker in sorting departments into the pure teaching and the mixed research and teaching categories, I find many persons, including psychologists (not, I am happy to report, all of them), express objections on the grounds that these things cannot reliably be quantified.”
For Meehl, numbers are more objective, even if the measures are unreliable. He rails against the imprecision of “a subjective, impressionistic pseudo-quantifying, instead of counting and measuring.” He firmly believes that using numbers and systems of numbers brings more clarity to decision making, and doing otherwise is irrational.
“The basic mistake here is not realizing that when you’re talking about things that exist in degree or frequency (e.g., how often, or how strong, or how intense), you are engaging in a tallying or measuring operation whether you use words or numbers. The main difference is that the words are less precise and less objective than the numbers.”
The idea that counts are more “objective” than words is a classic blindspot of the sciences, and I’m sure many people here reading it agree with Meehl. “We want data, not anecdotes” is the motto of quantified America. Fourcade and Healy write a well-needed reminder that organizing a society around unreliable counts bakes in a huge helping of irrationality.
And even the most adherent capital-R Rationalists know this to be true if you press them on it a bit. Assuming that classification and ranking are quantitative and building a mathematical framework for decision making on top leads to a system riddled with paradoxes and small-mindedness. We choose to ignore the paradoxes because we normatively decide that a quantified system is better than the alternatives. But this faith in quantification leads to institutional inertia that makes the university miserable for all of us (Meehl) or a society with pernicious hidden hierarchies that we all tailor our behavior to appease (Fourcade and Healy).
Efficiently solving the Shortest Vector Problem (SVP) in two-dimensional
lattices holds practical significance in cryptography and computational
geometry. While simpler than its high-dimensional counterpart, two-dimensional
SVP motivates scalable solutions for high-dimensional lattices and benefits
applications like sequence cipher cryptanalysis involving large integers. In
this work, we first propose a novel definition of reduced bases and develop an
efficient adaptive lattice reduction algorithm \textbf{CrossEuc} that
strategically applies the Euclidean algorithm across dimensions. Building on
this framework, we introduce \textbf{HVec}, a vectorized generalization of the
Half-GCD algorithm originally defined for integers, which can efficiently halve
the bit-length of two vectors and may have independent interest. By iteratively
invoking \textbf{HVec}, our optimized algorithm \textbf{HVecSBP} achieves a
reduced basis in $O(\log n M(n) )$ time for arbitrary input bases with
bit-length $n$, where $M(n)$ denotes the cost of multiplying two $n$-bit
integers. Compared to existing algorithms, our design is applicable to general
forms of input lattices, eliminating the cost of pre-converting input bases to
Hermite Normal Form (HNF). The comprehensive experimental results demonstrate
that for the input lattice bases in HNF, the optimized algorithm
\textbf{HVecSBP} achieves at least a $13.5\times$ efficiency improvement
compared to existing methods. For general-form input lattice bases, converting
them to HNF before applying \textbf{HVecSBP} offers only marginal advantages in
extreme cases where the two basis vectors are nearly degenerate. However, as
the linear dependency between input basis vectors decreases, directly employing
\textbf{HVecSBP} yields increasingly significant efficiency gains,
outperforming hybrid approaches that rely on prior \textbf{HNF} conversion.
Efficiently solving the Shortest Vector Problem (SVP) in two-dimensional
lattices holds practical significance in cryptography and computational
geometry. While simpler than its high-dimensional counterpart, two-dimensional
SVP motivates scalable solutions for high-dimensional lattices and benefits
applications like sequence cipher cryptanalysis involving large integers. In
this work, we first propose a novel definition of reduced bases and develop an
efficient adaptive lattice reduction algorithm \textbf{CrossEuc} that
strategically applies the Euclidean algorithm across dimensions. Building on
this framework, we introduce \textbf{HVec}, a vectorized generalization of the
Half-GCD algorithm originally defined for integers, which can efficiently halve
the bit-length of two vectors and may have independent interest. By iteratively
invoking \textbf{HVec}, our optimized algorithm \textbf{HVecSBP} achieves a
reduced basis in $O(\log n M(n) )$ time for arbitrary input bases with
bit-length $n$, where $M(n)$ denotes the cost of multiplying two $n$-bit
integers. Compared to existing algorithms, our design is applicable to general
forms of input lattices, eliminating the cost of pre-converting input bases to
Hermite Normal Form (HNF). The comprehensive experimental results demonstrate
that for the input lattice bases in HNF, the optimized algorithm
\textbf{HVecSBP} achieves at least a $13.5\times$ efficiency improvement
compared to existing methods. For general-form input lattice bases, converting
them to HNF before applying \textbf{HVecSBP} offers only marginal advantages in
extreme cases where the two basis vectors are nearly degenerate. However, as
the linear dependency between input basis vectors decreases, directly employing
\textbf{HVecSBP} yields increasingly significant efficiency gains,
outperforming hybrid approaches that rely on prior \textbf{HNF} conversion.
Authors: Saulo Queiroz, João P. Vilela, Benjamin Koon Kei Ng, Chan-Tong Lam, Edmundo Monteiro
In~\cite{sic-magazine-2025}, the authors show that the square index
coefficients (SICs) of the \(N\)-point discrete Fourier transform (DFT) -- that
is, the coefficients \(X_{k\sqrt{N}}\) for \(k = 0, 1, \ldots, \sqrt{N} - 1\)
-- can be losslessly compressed from \(N\) to \(\sqrt{N}\) points, thereby
accelerating the computation of these specific DFT coefficients accordingly.
Following up on that, in this article we generalize SICs into what we refer to
as rectangular index coefficients (RICs) of the DFT, formalized as $X_{kL},
k=0,1,\cdots,C-1$, in which the integers $C$ and $L$ are generic roots of $N$
such that $N=LC$. We present an algorithm to compress the $N$-point input
signal $\mathbf{x}$ into a $C$-point signal $\mathbf{\hat{x}}$ at the expense
of $\mathcal{O}(N)$ complex sums and no complex multiplication. We show that a
DFT on $\mathbf{\hat{x}}$ is equivalent to a DFT on the RICs of $\mathbf{x}$.
In cases where specific frequencies of \(\mathbf{x}\) are of interest -- as in
harmonic analysis -- one can conveniently adjust the signal parameters (e.g.,
frequency resolution) to align the RICs with those frequencies, and use the
proposed algorithm to compute them significantly faster. If $N$ is a power of
two -- as required by the fast Fourier transform (FFT) algorithm -- then $C$
can be any power of two in the range $[2, N/2]$ and one can use our algorithm
along with FFT to compute all RICs in $\mathcal{O}(C\log C)$ time complexity.
In~\cite{sic-magazine-2025}, the authors show that the square index
coefficients (SICs) of the \(N\)-point discrete Fourier transform (DFT) -- that
is, the coefficients \(X_{k\sqrt{N}}\) for \(k = 0, 1, \ldots, \sqrt{N} - 1\)
-- can be losslessly compressed from \(N\) to \(\sqrt{N}\) points, thereby
accelerating the computation of these specific DFT coefficients accordingly.
Following up on that, in this article we generalize SICs into what we refer to
as rectangular index coefficients (RICs) of the DFT, formalized as $X_{kL},
k=0,1,\cdots,C-1$, in which the integers $C$ and $L$ are generic roots of $N$
such that $N=LC$. We present an algorithm to compress the $N$-point input
signal $\mathbf{x}$ into a $C$-point signal $\mathbf{\hat{x}}$ at the expense
of $\mathcal{O}(N)$ complex sums and no complex multiplication. We show that a
DFT on $\mathbf{\hat{x}}$ is equivalent to a DFT on the RICs of $\mathbf{x}$.
In cases where specific frequencies of \(\mathbf{x}\) are of interest -- as in
harmonic analysis -- one can conveniently adjust the signal parameters (e.g.,
frequency resolution) to align the RICs with those frequencies, and use the
proposed algorithm to compute them significantly faster. If $N$ is a power of
two -- as required by the fast Fourier transform (FFT) algorithm -- then $C$
can be any power of two in the range $[2, N/2]$ and one can use our algorithm
along with FFT to compute all RICs in $\mathcal{O}(C\log C)$ time complexity.
Authors: Miles Simmons, Ishan Bansal, Joe Cheriyan
Jain's iterative rounding theorem is a well-known result in the area of
approximation algorithms and, more broadly, in combinatorial optimization. The
theorem asserts that LP relaxations of several problems in network design and
combinatorial optimization have the following key property: for every basic
solution $x$ there exists a variable $x_e$ that has value at least a constant
(e.g., $x_e\geq\frac12$).
We construct an example showing that this property fails to hold for the
Cover Small Cuts problem. In this problem, we are given an undirected,
capacitated graph $G=(V,E),u$ and a threshold value $\lambda$, as well as a set
of links $L$ with end-nodes in $V$ and a non-negative cost for each link
$\ell\in L$; the goal is to find a minimum-cost set of links such that each
non-trivial cut of capacity less than $\lambda$ is covered by a link.
This indicates that the polyhedron of feasible solutions to the LP relaxation
(of Cover Small Cuts) differs in an essential way from the polyhedrons
associated with several problems in combinatorial optimization. Moreover, our
example shows that a direct application of Jain's iterative rounding algorithm
does not give an $O(1)$ approximation algorithm for Cover Small Cuts. We
mention that Bansal et al. (Algorithmica 2024) present an $O(1)$ approximation
algorithm for Cover Small Cuts based on the primal-dual method of Williamson et
al. (Combinatorica 1995).
Jain's iterative rounding theorem is a well-known result in the area of
approximation algorithms and, more broadly, in combinatorial optimization. The
theorem asserts that LP relaxations of several problems in network design and
combinatorial optimization have the following key property: for every basic
solution $x$ there exists a variable $x_e$ that has value at least a constant
(e.g., $x_e\geq\frac12$).
We construct an example showing that this property fails to hold for the
Cover Small Cuts problem. In this problem, we are given an undirected,
capacitated graph $G=(V,E),u$ and a threshold value $\lambda$, as well as a set
of links $L$ with end-nodes in $V$ and a non-negative cost for each link
$\ell\in L$; the goal is to find a minimum-cost set of links such that each
non-trivial cut of capacity less than $\lambda$ is covered by a link.
This indicates that the polyhedron of feasible solutions to the LP relaxation
(of Cover Small Cuts) differs in an essential way from the polyhedrons
associated with several problems in combinatorial optimization. Moreover, our
example shows that a direct application of Jain's iterative rounding algorithm
does not give an $O(1)$ approximation algorithm for Cover Small Cuts. We
mention that Bansal et al. (Algorithmica 2024) present an $O(1)$ approximation
algorithm for Cover Small Cuts based on the primal-dual method of Williamson et
al. (Combinatorica 1995).
Authors: Manuel Jakob, Yannic Maus, Florian Schager
We design a deterministic distributed $\mathcal{O}(\log n)$-round reduction
from the $(2\Delta-2)$-edge coloring problem to the much easier
$(2\Delta-1)$-edge coloring problem. This is almost optimal, as the
$(2\Delta-2)$-edge coloring problem admits an $\Omega(\log_\Delta n)$ lower
bound. Further, we also obtain an optimal $\mathcal{O}(\log_\Delta n)$-round
reduction, albeit to the harder maximal independent set (MIS) problem.
The current state-of-the-art for $(2\Delta - 1)$-edge coloring actually comes
from an MIS algorithm by [Ghaffari \& Grunau, FOCS'24], which runs in
$\widetilde{\mathcal{O}}(\log^{5/3} n)$ rounds. With our new reduction, this
round complexity now carries over to the $(2\Delta - 2)$-edge coloring problem
as well. Alternatively, one can also plug in the $(\mathrm{poly} \log \Delta +
\mathcal{O}(\log^{\ast} n))$-round $(2\Delta - 1)$-edge coloring algorithm from
[Balliu, Brandt, Kuhn \& Olivetti, PODC'22], which yields an optimal runtime of
$\mathcal{O}(\log n)$ rounds for $\Delta \leq \mathrm{poly} \log n$.
Previously, the fastest deterministic algorithm using less than $2\Delta - 1$
colors for general graphs by [Brandt, Maus, Narayanan, Schager \& Uitto,
SODA'25] ran in $\widetilde{\mathcal{O}}(\log^3 n)$ rounds. In addition, we
also obtain a $\mathcal{O}(\log \log n)$-round randomized reduction of
$(2\Delta - 2)$-edge coloring to $(2\Delta - 1)$-edge coloring. This improves
upon the (very recent) best randomized algorithm using less than $2\Delta - 1$
colors from [Bourreau, Brandt \& Nolin, STOC'25] by reducing the round
complexity from $\widetilde{\mathcal{O}}(\log^{8/3}\log n)$ down to
$\widetilde{\mathcal{O}}(\log^{5/3} \log n)$.
We design a deterministic distributed $\mathcal{O}(\log n)$-round reduction
from the $(2\Delta-2)$-edge coloring problem to the much easier
$(2\Delta-1)$-edge coloring problem. This is almost optimal, as the
$(2\Delta-2)$-edge coloring problem admits an $\Omega(\log_\Delta n)$ lower
bound. Further, we also obtain an optimal $\mathcal{O}(\log_\Delta n)$-round
reduction, albeit to the harder maximal independent set (MIS) problem.
The current state-of-the-art for $(2\Delta - 1)$-edge coloring actually comes
from an MIS algorithm by [Ghaffari \& Grunau, FOCS'24], which runs in
$\widetilde{\mathcal{O}}(\log^{5/3} n)$ rounds. With our new reduction, this
round complexity now carries over to the $(2\Delta - 2)$-edge coloring problem
as well. Alternatively, one can also plug in the $(\mathrm{poly} \log \Delta +
\mathcal{O}(\log^{\ast} n))$-round $(2\Delta - 1)$-edge coloring algorithm from
[Balliu, Brandt, Kuhn \& Olivetti, PODC'22], which yields an optimal runtime of
$\mathcal{O}(\log n)$ rounds for $\Delta \leq \mathrm{poly} \log n$.
Previously, the fastest deterministic algorithm using less than $2\Delta - 1$
colors for general graphs by [Brandt, Maus, Narayanan, Schager \& Uitto,
SODA'25] ran in $\widetilde{\mathcal{O}}(\log^3 n)$ rounds. In addition, we
also obtain a $\mathcal{O}(\log \log n)$-round randomized reduction of
$(2\Delta - 2)$-edge coloring to $(2\Delta - 1)$-edge coloring. This improves
upon the (very recent) best randomized algorithm using less than $2\Delta - 1$
colors from [Bourreau, Brandt \& Nolin, STOC'25] by reducing the round
complexity from $\widetilde{\mathcal{O}}(\log^{8/3}\log n)$ down to
$\widetilde{\mathcal{O}}(\log^{5/3} \log n)$.
In the single stock trading prophet problem formulated by Correa et al.\
(2023), an online algorithm observes a sequence of prices of a stock. At each
step, the algorithm can either buy the stock by paying the current price if it
doesn't already hold the stock, or it can sell the currently held stock and
collect the current price as a reward. The goal of the algorithm is to maximize
its overall profit.
In this work, we generalize the model and the results of Correa et al.\ by
allowing the algorithm to trade multiple stocks. First, we formulate the
$(k,\ell,\ell')$-Trading Prophet Problem, wherein there are $k$ stocks in the
market, and the online algorithm can hold up to $\ell$ stocks at any time,
where $\ell\leq k$. The online algorithm competes against an offline algorithm
that can hold at most $\ell'\leq\ell$ stocks at any time. Under the assumption
that prices of different stocks are independent, we show that, for any $\ell$,
$\ell'$, and $k$, the optimal competitive ratio of $(k,\ell,\ell')$-Trading
Prophet Problem is $\min(1/2,\ell/k)$.
We further introduce the more general $\cal{M}$-Trading Prophet Problem over
a matroid $\cal{M}$ on the set of $k$ stocks, wherein the stock prices at any
given time are possibly correlated (but are independent across time). The
algorithm is allowed to hold only a feasible subset of stocks at any time. We
prove a tight bound of $1/(1+d)$ on the competitive ratio of the
$\cal{M}$-Trading Prophet Problem, where $d$ is the density of the matroid.
We then consider the non-i.i.d.\ random order setting over a matroid, wherein
stock prices drawn independently from $n$ potentially different distributions
are presented in a uniformly random order. In this setting, we achieve a
competitive ratio of at least $1/(1+d)-\cal{O}(1/n)$, where $d$ is the density
of the matroid, matching the hardness result for i.i.d.\ instances as $n$
approaches $\infty$.
In the single stock trading prophet problem formulated by Correa et al.\
(2023), an online algorithm observes a sequence of prices of a stock. At each
step, the algorithm can either buy the stock by paying the current price if it
doesn't already hold the stock, or it can sell the currently held stock and
collect the current price as a reward. The goal of the algorithm is to maximize
its overall profit.
In this work, we generalize the model and the results of Correa et al.\ by
allowing the algorithm to trade multiple stocks. First, we formulate the
$(k,\ell,\ell')$-Trading Prophet Problem, wherein there are $k$ stocks in the
market, and the online algorithm can hold up to $\ell$ stocks at any time,
where $\ell\leq k$. The online algorithm competes against an offline algorithm
that can hold at most $\ell'\leq\ell$ stocks at any time. Under the assumption
that prices of different stocks are independent, we show that, for any $\ell$,
$\ell'$, and $k$, the optimal competitive ratio of $(k,\ell,\ell')$-Trading
Prophet Problem is $\min(1/2,\ell/k)$.
We further introduce the more general $\cal{M}$-Trading Prophet Problem over
a matroid $\cal{M}$ on the set of $k$ stocks, wherein the stock prices at any
given time are possibly correlated (but are independent across time). The
algorithm is allowed to hold only a feasible subset of stocks at any time. We
prove a tight bound of $1/(1+d)$ on the competitive ratio of the
$\cal{M}$-Trading Prophet Problem, where $d$ is the density of the matroid.
We then consider the non-i.i.d.\ random order setting over a matroid, wherein
stock prices drawn independently from $n$ potentially different distributions
are presented in a uniformly random order. In this setting, we achieve a
competitive ratio of at least $1/(1+d)-\cal{O}(1/n)$, where $d$ is the density
of the matroid, matching the hardness result for i.i.d.\ instances as $n$
approaches $\infty$.
Authors: Gustavo Alves Bezerra, Andris Ambainis, Renato Portugal
Quantum walks provide a powerful framework for achieving algorithmic speedup
in quantum computing. This paper presents a quantum search algorithm for
2-tessellable graphs, a generalization of bipartite graphs, achieving a
quadratic speedup over classical Markov chain-based search methods. Our
approach employs an adapted version of the Szegedy quantum walk model (adapted
SzQW), which takes place on bipartite graphs, and an adapted version of
Staggered Quantum Walks (Adapted StQW), which takes place on 2-tessellable
graphs, with the goal of efficiently finding a marked vertex by querying an
oracle. The Ambainis, Gily\'en, Jeffery, and Kokainis' algorithm (AGJK), which
provides a quadratic speedup on balanced bipartite graphs, is used as a
subroutine in our algorithm. Our approach generalizes existing quantum walk
techniques and offers a quadratic speedup in the number of queries needed,
demonstrating the utility of our adapted quantum walk models in a broader class
of graphs.
Quantum walks provide a powerful framework for achieving algorithmic speedup
in quantum computing. This paper presents a quantum search algorithm for
2-tessellable graphs, a generalization of bipartite graphs, achieving a
quadratic speedup over classical Markov chain-based search methods. Our
approach employs an adapted version of the Szegedy quantum walk model (adapted
SzQW), which takes place on bipartite graphs, and an adapted version of
Staggered Quantum Walks (Adapted StQW), which takes place on 2-tessellable
graphs, with the goal of efficiently finding a marked vertex by querying an
oracle. The Ambainis, Gily\'en, Jeffery, and Kokainis' algorithm (AGJK), which
provides a quadratic speedup on balanced bipartite graphs, is used as a
subroutine in our algorithm. Our approach generalizes existing quantum walk
techniques and offers a quadratic speedup in the number of queries needed,
demonstrating the utility of our adapted quantum walk models in a broader class
of graphs.
We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let $X$ be the $n$-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter $\lambda$. We prove that the bitwise XOR of $t$ independent copies of $X$ fools width-$w$ programs with error $n^{\log(w + 1)} \cdot (\lambda \cdot \log n)^t$. Notably, this error bound is meaningful even for relatively large values of $\lambda$ such as $\lambda = 1/O(\log n)$.
Admittedly, our analysis does not yet imply any improvement in the bottom-line overall seed length required for fooling such programs -- it just gives a new way of re-proving the well-known $O(\log^2 n)$ bound. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our ``XOR of INW'' approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-$3$ programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably $\Omega(\log^2 n)$.
Still, we hope that our work might be a step toward constructing near-optimal PRGs fooling constant-width ROBPs. We suggest that one could try running the INW PRG on $t$ \emph{correlated} seeds, sampled via another PRG, and taking the bitwise XOR of the outputs.
We study a new approach for constructing pseudorandom generators (PRGs) that fool constant-width standard-order read-once branching programs (ROBPs). Let $X$ be the $n$-bit output distribution of the INW PRG (Impagliazzo, Nisan, and Wigderson, STOC 1994), instantiated using expansion parameter $\lambda$. We prove that the bitwise XOR of $t$ independent copies of $X$ fools width-$w$ programs with error $n^{\log(w + 1)} \cdot (\lambda \cdot \log n)^t$. Notably, this error bound is meaningful even for relatively large values of $\lambda$ such as $\lambda = 1/O(\log n)$.
Admittedly, our analysis does not yet imply any improvement in the bottom-line overall seed length required for fooling such programs -- it just gives a new way of re-proving the well-known $O(\log^2 n)$ bound. Furthermore, we prove that this shortcoming is not an artifact of our analysis, but rather is an intrinsic limitation of our ``XOR of INW'' approach. That is, no matter how many copies of the INW generator we XOR together, and no matter how we set the expansion parameters, if the generator fools width-$3$ programs and the proof of correctness does not use any properties of the expander graphs except their spectral expansion, then we prove that the seed length of the generator is inevitably $\Omega(\log^2 n)$.
Still, we hope that our work might be a step toward constructing near-optimal PRGs fooling constant-width ROBPs. We suggest that one could try running the INW PRG on $t$ \emph{correlated} seeds, sampled via another PRG, and taking the bitwise XOR of the outputs.
The next TCS+ talk will take place this coming Wednesday, April 23rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Ryan Williams from MIT will speak about “Simulating Time With Square-Root Space” (abstract below). You can reserve a spot as an individual or a group to join us […]
The next TCS+ talk will take place this coming Wednesday, April 23rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 17:00 UTC). Ryan Williams from MIT will speak about “Simulating Time With Square-Root Space” (abstract below).
You can reserve a spot as an individual or a group to join us live by signing up on the online form. Registration is not required to attend the interactive talk, and the link will be posted on the website the day prior to the talk; however, by registering in the form, you will receive a reminder, along with the link. (The recorded talk will also be posted on our website afterwards) As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.
Abstract: We show that for all functions , every multitape Turing machine running in time can be simulated in space only . This is a substantial improvement over Hopcroft, Paul, and Valiant’s simulation of time in space from 50 years ago [FOCS 1975, JACM 1977]. Among other results, our simulation implies that bounded fan-in circuits of size can be evaluated on any input in only space, and that there are explicit problems solvable in space which require at least time on a multitape Turing machine for all , thereby making a little progress on the versus problem.
Our simulation reduces the problem of simulating time-bounded multitape Turing machines to a series of implicitly-defined Tree Evaluation instances with nice parameters, leveraging the remarkable space-efficient algorithm for Tree Evaluation recently found by Cook and Mertz [STOC 2024].
Two fully-funded PhD positions available in the group of Prof. Prantar Ghosh (sites.google.com/view/prantarg/home) at Tennessee Tech University starting Fall 2025. Research will focus broadly on graph algorithms. A good mathematical background and prior experience in Theoretical Computer Science is required. Please email CV and a short description of background before officially applying. Website: www.tntech.edu/graduatestudies/admissions/apply.php Email: […]
Two fully-funded PhD positions available in the group of Prof. Prantar Ghosh (https://sites.google.com/view/prantarg/home) at Tennessee Tech University starting Fall 2025. Research will focus broadly on graph algorithms. A good mathematical background and prior experience in Theoretical Computer Science is required. Please email CV and a short description of background before officially applying.
The Fewest Clues Problem (FCP) framework has been introduced to study the
complexity of determining whether a solution to an \NP~problem can be uniquely
identified by specifying a subset of the certificate. For a given problem $P
\in \NP$, its FCP variant is denoted by FCP-$P$. While several \NP-complete
problems have been shown to have $\Sigma_2^\p$-complete FCP variants, it
remains open whether this holds for all \NP-complete problems.
In this work, we propose a meta-theorem that establishes the
$\Sigma_2^\p$-completeness of FCP-$P$ under the condition that the \NP-hardness
of $P$ is proven via a polynomial-time reduction satisfying certain structural
properties. Furthermore, we apply the meta-theorem to demonstrate the
$\Sigma_2^\p$-completeness of the FCP variants of several \NP-complete
problems.
The Fewest Clues Problem (FCP) framework has been introduced to study the
complexity of determining whether a solution to an \NP~problem can be uniquely
identified by specifying a subset of the certificate. For a given problem $P
\in \NP$, its FCP variant is denoted by FCP-$P$. While several \NP-complete
problems have been shown to have $\Sigma_2^\p$-complete FCP variants, it
remains open whether this holds for all \NP-complete problems.
In this work, we propose a meta-theorem that establishes the
$\Sigma_2^\p$-completeness of FCP-$P$ under the condition that the \NP-hardness
of $P$ is proven via a polynomial-time reduction satisfying certain structural
properties. Furthermore, we apply the meta-theorem to demonstrate the
$\Sigma_2^\p$-completeness of the FCP variants of several \NP-complete
problems.
We present polynomial-time approximation schemes based on local search}
technique for both geometric (discrete) independent set (\mdis) and geometric
(discrete) dominating set (\mdds) problems, where the objects are arbitrary
radii disks and arbitrary side length axis-parallel squares. Further, we show
that the \mdds~problem is \apx-hard for various shapes in the plane. Finally,
we prove that both \mdis~and \mdds~problems are \np-hard for unit disks
intersecting a horizontal line and axis-parallel unit squares intersecting a
straight line with slope $-1$.
We present polynomial-time approximation schemes based on local search}
technique for both geometric (discrete) independent set (\mdis) and geometric
(discrete) dominating set (\mdds) problems, where the objects are arbitrary
radii disks and arbitrary side length axis-parallel squares. Further, we show
that the \mdds~problem is \apx-hard for various shapes in the plane. Finally,
we prove that both \mdis~and \mdds~problems are \np-hard for unit disks
intersecting a horizontal line and axis-parallel unit squares intersecting a
straight line with slope $-1$.
For a fixed integer $q$, the $q$-Coloring problem asks to decide if a given
graph has a vertex coloring with $q$ colors such that no two adjacent vertices
receive the same color. In a series of papers, it has been shown that for every
$q \geq 3$, the $q$-Coloring problem parameterized by the vertex cover number
$k$ admits a kernel of bit-size $\widetilde{O}(k^{q-1})$, but admits no kernel
of bit-size $O(k^{q-1-\varepsilon})$ for $\varepsilon >0$ unless $\mathsf{NP}
\subseteq \mathsf{coNP/poly}$ (Jansen and Kratsch, 2013; Jansen and Pieterse,
2019). In 2020, Schalken proposed the question of the kernelizability of the
$q$-Coloring problem parameterized by the number $k$ of vertices whose removal
results in a disjoint union of edges and isolated vertices. He proved that for
every $q \geq 3$, the problem admits a kernel of bit-size
$\widetilde{O}(k^{2q-2})$, but admits no kernel of bit-size
$O(k^{2q-3-\varepsilon})$ for $\varepsilon >0$ unless $\mathsf{NP} \subseteq
\mathsf{coNP/poly}$. He further proved that for $q \in \{3,4\}$ the problem
admits a near-optimal kernel of bit-size $\widetilde{O}(k^{2q-3})$ and asked
whether such a kernel is achievable for all integers $q \geq 3$. In this short
paper, we settle this question in the affirmative.
For a fixed integer $q$, the $q$-Coloring problem asks to decide if a given
graph has a vertex coloring with $q$ colors such that no two adjacent vertices
receive the same color. In a series of papers, it has been shown that for every
$q \geq 3$, the $q$-Coloring problem parameterized by the vertex cover number
$k$ admits a kernel of bit-size $\widetilde{O}(k^{q-1})$, but admits no kernel
of bit-size $O(k^{q-1-\varepsilon})$ for $\varepsilon >0$ unless $\mathsf{NP}
\subseteq \mathsf{coNP/poly}$ (Jansen and Kratsch, 2013; Jansen and Pieterse,
2019). In 2020, Schalken proposed the question of the kernelizability of the
$q$-Coloring problem parameterized by the number $k$ of vertices whose removal
results in a disjoint union of edges and isolated vertices. He proved that for
every $q \geq 3$, the problem admits a kernel of bit-size
$\widetilde{O}(k^{2q-2})$, but admits no kernel of bit-size
$O(k^{2q-3-\varepsilon})$ for $\varepsilon >0$ unless $\mathsf{NP} \subseteq
\mathsf{coNP/poly}$. He further proved that for $q \in \{3,4\}$ the problem
admits a near-optimal kernel of bit-size $\widetilde{O}(k^{2q-3})$ and asked
whether such a kernel is achievable for all integers $q \geq 3$. In this short
paper, we settle this question in the affirmative.
The storage capacity of a graph measures the maximum amount of information
that can be stored across its vertices, such that the information at any vertex
can be recovered from the information stored at its neighborhood. The study of
this graph quantity is motivated by applications in distributed storage and by
its intimate relations to the index coding problem from the area of network
information theory. In the latter, one wishes to minimize the amount of
information that has to be transmitted to a collection of receivers, in a way
that enables each of them to discover its required data using some prior side
information.
In this paper, we initiate the study of the Storage Capacity and Index Coding
problems from the perspective of parameterized complexity. We prove that the
Storage Capacity problem parameterized by the solution size admits a
kernelization algorithm producing kernels of linear size. We also provide such
a result for the Index Coding problem, in the linear and non-linear settings,
where it is parameterized by the dual value of the solution, i.e., the length
of the transmission that can be saved using the side information. A key
ingredient in the proofs is the crown decomposition technique due to Chor,
Fellows, and Juedes (WG 2003, WG 2004). As an application, we significantly
extend an algorithmic result of Dau, Skachek, and Chee (IEEE Trans. Inform.
Theory, 2014).
The storage capacity of a graph measures the maximum amount of information
that can be stored across its vertices, such that the information at any vertex
can be recovered from the information stored at its neighborhood. The study of
this graph quantity is motivated by applications in distributed storage and by
its intimate relations to the index coding problem from the area of network
information theory. In the latter, one wishes to minimize the amount of
information that has to be transmitted to a collection of receivers, in a way
that enables each of them to discover its required data using some prior side
information.
In this paper, we initiate the study of the Storage Capacity and Index Coding
problems from the perspective of parameterized complexity. We prove that the
Storage Capacity problem parameterized by the solution size admits a
kernelization algorithm producing kernels of linear size. We also provide such
a result for the Index Coding problem, in the linear and non-linear settings,
where it is parameterized by the dual value of the solution, i.e., the length
of the transmission that can be saved using the side information. A key
ingredient in the proofs is the crown decomposition technique due to Chor,
Fellows, and Juedes (WG 2003, WG 2004). As an application, we significantly
extend an algorithmic result of Dau, Skachek, and Chee (IEEE Trans. Inform.
Theory, 2014).