Cover Image

Streaming Zero-Knowledge Proofs

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Cormode, Graham, Dall'Agnol, Marcel, Gur, Tom, Hickey, Chris
Format:	Preprint
Published:	2023
Subjects:	Computational Complexity Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Perfect Zero-Knowledge PCPs for #P
by: Gur, Tom, et al.
Published: (2024)

On the Power of Interactive Proofs for Learning
by: Gur, Tom, et al.
Published: (2024)

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

Quantum Channel Testing in Average-Case Distance
by: Rosenthal, Gregory, et al.
Published: (2024)

Does Subset Sum Admit Short Proofs?
by: Włodarczyk, Michał
Published: (2024)

Turnstile Streaming Algorithms Might (Still) as Well Be Linear Sketches, for Polynomial-Length Streams
by: Jiang, Cheng, et al.
Published: (2026)

A Simple Proof that Ricochet Robots is PSPACE-Complete
by: Balanza-Martinez, Jose, et al.
Published: (2024)

Streaming approximation resistance of every ordering CSP
by: Singer, Noah G., et al.
Published: (2021)

Semi-Streaming Algorithms for Graph Property Certification
by: Das, Avinandan, et al.
Published: (2025)

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

Streaming Complexity Separations for Dense and Sparse Graphs
by: Liu, Yang P., et al.
Published: (2026)

Coloring Graphs with Few Colors in the Streaming Model
by: Assadi, Sepehr, et al.
Published: (2025)

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

Characterizing Streaming Decidability of CSPs via Non-Redundancy
by: Sharma, Amatya, et al.
Published: (2026)

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

A Dichotomy Theorem for Multi-Pass Streaming CSPs
by: Fei, Yumou, et al.
Published: (2025)

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

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

Better Bounds for Semi-Streaming Single-Source Shortest Paths
by: Assadi, Sepehr, et al.
Published: (2025)

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

Settling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
by: Assadi, Sepehr, et al.
Published: (2024)

Space Complexity Dichotomies for Subgraph Finding Problems in the Streaming Model
by: Shih, Yu-Sheng, et al.
Published: (2026)

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

A New Information Complexity Measure for Multi-pass Streaming with Applications
by: Braverman, Mark, et al.
Published: (2024)

On the Complexity of 2-club Cluster Editing with Vertex Splitting
by: Abu-Khzam, Faisal N., et al.
Published: (2024)

Fourier Analysis of Iterative Algorithms
by: Jones, Chris, et al.
Published: (2024)

Probabilistically Checkable Reconfiguration Proofs and Inapproximability of Reconfiguration Problems
by: Hirahara, Shuichi, et al.
Published: (2023)

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

Parameterized Complexity of Streaming Diameter and Connectivity Problems
by: Oostveen, Jelle J., et al.
Published: (2022)

Streaming Algorithms for Bin Packing and Vector Scheduling
by: Cormode, Graham, et al.
Published: (2019)

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

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
by: Das, Avinandan
Published: (2026)

A number-theoretic conjecture implying faster algorithms for polynomial factorization and integer factorization
by: Umans, Chris, et al.
Published: (2025)

Near-Optimal Bounds for Parameterized Euclidean k-means
by: Cohen-Addad, Vincent, et al.
Published: (2026)

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

Single-copy stabilizer testing
by: Hinsche, Marcel, et al.
Published: (2024)

Complexity of Local Search for Euclidean Clustering Problems
by: Manthey, Bodo, et al.
Published: (2023)

Conditional lower bounds for sparse parameterized 2-CSP: A streamlined proof
by: S., Karthik C., et al.
Published: (2023)

Bandwidth Parameterized by Cluster Vertex Deletion Number
by: Gima, Tatsuya, et al.
Published: (2023)

Multicut Problems in Embedded Graphs: The Dependency of Complexity on the Demand Pattern
by: Focke, Jacob, et al.
Published: (2023)