Cover Image

Tight Space Lower Bound for Pseudo-Deterministic Approximate Counting

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Grossman, Ofer, Gupta, Meghal, Sellke, Mark
Format:	Preprint
Published:	2023
Subjects:	Data Structures and Algorithms Computational Complexity
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Tight Streaming Lower Bounds for Deterministic Approximate Counting
by: Wang, Yichuan
Published: (2024)

Linear Space Streaming Lower Bounds for Approximating CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

From Graph Properties to Graph Parameters: Tight Bounds for Counting on Small Subgraphs
by: Döring, Simon, et al.
Published: (2024)

A Tight Double-Exponentially Lower Bound for High-Multiplicity Bin Packing
by: Jansen, Klaus, et al.
Published: (2025)

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results
by: Focke, Jacob, et al.
Published: (2022)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
by: Singer, Noah G., et al.
Published: (2026)

Near-Optimal Space Lower Bounds for Streaming CSPs
by: Fei, Yumou, et al.
Published: (2026)

Lower Bounds for Convexity Testing
by: Chen, Xi, et al.
Published: (2024)

Sensitivity Lower Bounds for Approximaiton Algorithms
by: Fleming, Noah, et al.
Published: (2024)

Strong Low Degree Hardness for the Number Partitioning Problem
by: Mallarapu, Rushil, et al.
Published: (2025)

Treedepth Inapproximability and Exponential ETH Lower Bound
by: Bonnet, Édouard, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Uniformity Testing
by: Li, Qian, et al.
Published: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
by: Fei, Yumou, et al.
Published: (2025)

Approximating Klee's Measure Problem and a Lower Bound for Union Volume Estimation
by: Bringmann, Karl, et al.
Published: (2024)

A Polynomial Space Lower Bound for Diameter Estimation in Dynamic Streams
by: Khanna, Sanjeev, et al.
Published: (2025)

Polynomial Pass Semi-Streaming Lower Bounds for K-Cores and Degeneracy
by: Assadi, Sepehr, et al.
Published: (2024)

Unifying the Landscape of Super-Logarithmic Dynamic Cell-Probe Lower Bounds
by: Ko, Young Kun
Published: (2025)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
by: Cohen-Addad, Vincent, et al.
Published: (2026)

The Structure of In-Place Space-Bounded Computation
by: Cook, James, et al.
Published: (2025)

Improved Space Bounds for Subset Sum
by: Belova, Tatiana, et al.
Published: (2024)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
by: Wang, Chengu
Published: (2026)

Improved Bounds for Twin-Width Parameter Variants with Algorithmic Applications to Counting Graph Colorings
by: Baril, Ambroise, et al.
Published: (2025)

Non-Boolean OMv: One More Reason to Believe Lower Bounds for Dynamic Problems
by: Hu, Bingbing, et al.
Published: (2024)

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
by: Rai, Shanthanu S
Published: (2024)

A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
by: Kisfaludi-Bak, Sándor, et al.
Published: (2020)

From Donkeys to Kings in Tournaments
by: Abboud, Amir, et al.
Published: (2024)

Lower Bounds for Linear Operators
by: Ko, Young Kun
Published: (2025)

Tight Additive Sensitivity on LZ-style Compressors and String Attractors
by: Fujie, Yuto, et al.
Published: (2025)

Keeping a Secret Requires a Good Memory: Space Lower-Bounds for Private Algorithms
by: Epasto, Alessandro, et al.
Published: (2026)

Deterministic Independent Sets in the Semi-Streaming Model
by: Ye, Daniel
Published: (2025)

Stable algorithms cannot reliably find isolated perceptron solutions
by: Gong, Shuyang, et al.
Published: (2026)

Tight Bounds for Noisy Computation of High-Influence Functions, Connectivity, and Threshold
by: Gu, Yuzhou, et al.
Published: (2025)

Stable Algorithms Lower Bounds for Estimation
by: Yu, Xifan, et al.
Published: (2026)

Self-referential instances of the dominating set problem are irreducible
by: Zhou, Guangyan
Published: (2026)

The Complexity of Finding and Counting Subtournaments
by: Döring, Simon, et al.
Published: (2025)

On Inapproximability of Reconfiguration Problems: PSPACE-Hardness and some Tight NP-Hardness Results
by: Guruswami, Venkatesan, et al.
Published: (2023)

Deterministic factorization of constant-depth algebraic circuits in subexponential time
by: Bhattacharjee, Somnath, et al.
Published: (2025)

The Complexity of Counting Small Sub-Hypergraphs
by: Bressan, Marco, et al.
Published: (2025)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
by: Kumar, Mrinal, et al.
Published: (2024)

Tight (Double) Exponential Bounds for Identification Problems: Locating-Dominating Set and Test Cover
by: Chakraborty, Dipayan, et al.
Published: (2024)