More Like this

1. Lower Bounds for Adaptive Relaxation-Based Algorithms for Single-Source Shortest Paths

   https://doi.org/10.4230/LIPIcs.ISAAC.2024.8  

   Atalig, Sunny; Hickerson, Alexander; Srivastav, Arrdya; Zheng, Tingting; Chrobak, Marek (January 2024, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Mestre, Julián; Wirth, Anthony (Ed.)

   We consider the classical single-source shortest path problem in directed weighted graphs. D. Eppstein proved recently an Ω(n³) lower bound for oblivious algorithms that use relaxation operations to update the tentative distances from the source vertex. We generalize this result by extending this Ω(n³) lower bound to adaptive algorithms that, in addition to relaxations, can perform queries involving some simple types of linear inequalities between edge weights and tentative distances. Our model captures as a special case the operations on tentative distances used by Dijkstra’s algorithm. 

   more » « less
2. Lower Bounds for Non-adaptive Shortest Path Relaxation

   Eppstein, David (July 2023, Springer)

   We consider single-source shortest path algorithms that perform a sequence of relaxation steps whose ordering depends only on the input graph structure and not on its weights or the results of prior steps. Each step examines one edge of the graph, and replaces the tentative distance to the endpoint of the edge by its minimum with the tentative distance to the start of the edge, plus the edge length. As we prove, among such algorithms, the Bellman-Ford algorithm has optimal complexity for dense graphs and near-optimal complexity for sparse graphs, as a function of the number of edges and vertices in the given graph. Our analysis holds both for deterministic algorithms and for randomized algorithms that find shortest path distances with high probability. 

   more » « less
3. A Min-Entropy Approach to Multi-Party Communication Lower Bounds

   https://doi.org/10.4230/lipics.ccc.2025.33  

   Huang, Mi-Ying Miryam; Mao, Xinyu; Wang, Shuo; Yang, Guangxu; Zhang, Jiapeng (January 2025, Schloss Dagstuhl – Leibniz-Zentrum für Informatik)

   Srinivasan, Srikanth (Ed.)

   Information complexity is one of the most powerful techniques to prove information-theoretical lower bounds, in which Shannon entropy plays a central role. Though Shannon entropy has some convenient properties, such as the chain rule, it still has inherent limitations. One of the most notable barriers is the square-root loss, which appears in the square-root gap between entropy gaps and statistical distances, e.g., Pinsker’s inequality. To bypass this barrier, we introduce a new method based on min-entropy analysis. Building on this new method, we prove the following results. - An Ω(N^{∑_i α_i - max_i {α_i}}/k) randomized communication lower bound of the k-party set-intersection problem where the i-th party holds a random set of size ≈ N^{1-α_i}. - A tight Ω(n/k) randomized lower bound of the k-party Tree Pointer Jumping problems, improving an Ω(n/k²) lower bound by Chakrabarti, Cormode, and McGregor (STOC 08). - An Ω(n/k+√n) lower bound of the Chained Index problem, improving an Ω(n/k²) lower bound by Cormode, Dark, and Konrad (ICALP 19). Since these problems served as hard problems for numerous applications in streaming lower bounds and cryptography, our new lower bounds directly improve these streaming lower bounds and cryptography lower bounds. On the technical side, min-entropy does not have nice properties such as the chain rule. To address this issue, we enhance the structure-vs-pseudorandomness decomposition used by Göös, Pitassi, and Watson (FOCS 17) and Yang and Zhang (STOC 24); both papers used this decomposition to prove communication lower bounds. In this paper, we give a new breath to this method in the multi-party setting, presenting a new toolkit for proving multi-party communication lower bounds. 

   more » « less
4. Quantum Time-Space Tradeoffs for Matrix Problems

   Beame, Paul; Kornerup, Niels; Whitmeyer, Michael (November 2025, arXivorg)

   We consider the time and space required for quantum computers to solve a wide variety of problems involving matrices, many of which have only been analyzed classically in prior work. Our main results show that for a range of linear algebra problems—including matrix-vector product, matrix inversion, matrix multiplication and powering—existing classical time-space tradeoffs, several of which are tight for every space bound, also apply to quantum algorithms with at most a constant factor loss. For example, for almost all fixed matrices A, including the discrete Fourier transform (DFT) matrix, we prove that quantum circuits with at most T input queries and S qubits of memory require T = Ω(n^2/S) to compute matrix-vector product Ax for x ∈ {0, 1}^n. We similarly prove that matrix multiplication for n × n binary matrices requires T = Ω(n^3/√S). Because many of our lower bounds are matched by deterministic algorithms with the same time and space complexity, our results show that quantum computers cannot provide any asymptotic advantage for these problems with any space bound. We obtain matching lower bounds for the stronger notion of quantum cumulative memory complexity—the sum of the space per layer of a circuit. We also consider Boolean (i.e. AND-OR) matrix multiplication and matrix-vector products, improving the previous quantum time-space tradeoff lower bounds for n × n Boolean matrix multiplication to T = Ω(n^{2.5}/S^{1/4}) from T = Ω(n^{2.5}/S^{1/2}). Our improved lower bound for Boolean matrix multiplication is based on a new coloring argument that extracts more from the strong direct product theorem that was the basis for prior work. To obtain our tight lower bounds for linear algebra problems, we require much stronger bounds than strong direct product theorems. We obtain these bounds by adding a new bucketing method to the quantum recording-query technique of Zhandry that lets us apply classical arguments to upper bound the success probability of quantum circuits. 

   more » « less
5. Near-Optimal Randomized Exploration for Tabular Markov Decision Processes

   Xiong, Zhihan; Shen, Ruoqi; Cui, Qiwen; Fazel, Maryam; Du, Simon S. (December 2022, Advances in neural information processing systems)

   We study algorithms using randomized value functions for exploration in reinforcement learning. This type of algorithms enjoys appealing empirical performance. We show that when we use 1) a single random seed in each episode, and 2) a Bernstein-type magnitude of noise, we obtain a worst-case O~(H√SAT) regret bound for episodic time-inhomogeneous Markov Decision Process where S is the size of state space, A is the size of action space, H is the planning horizon and T is the number of interactions. This bound polynomially improves all existing bounds for algorithms based on randomized value functions, and for the first time, matches the Ω(H√SAT) lower bound up to logarithmic factors. Our result highlights that randomized exploration can be near-optimal, which was previously achieved only by optimistic algorithms. To achieve the desired result, we develop 1) a new clipping operation to ensure both the probability of being optimistic and the probability of being pessimistic are lower bounded by a constant, and 2) a new recursive formula for the absolute value of estimation errors to analyze the regret. 

   more » « less