Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

Almost Optimal Super-Constant-Pass Streaming Lower Bounds for Reachability

Bibliographic Details
Main Authors:	Chen, Lijie, Kol, Gillat, Paramonov, Dmitry, Saxena, Raghuvansh R., Song, Zhao, Yu, Huacheng
Other Authors:	Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science
Format:	Article
Language:	English
Published:	ACM\|Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing 2022
Online Access:	https://hdl.handle.net/1721.1/145931

Similar Items

Circuits Resilient to Short-Circuit Errors
by: Efremenko, Klim, et al.
Published: (2022)

An improved lower bound for the Traveling Salesman constant
by: Gaudio, Julia, et al.
Published: (2021)

Almost euclidean isoperimetric inequalities in spaces satisfying local Ricci curvature lower bounds
by: Cavalletti, F, et al.
Published: (2018)

On reachability for hybrid automata over bounded time
by: Brihaye, T, et al.
Published: (2011)

Algorithms and lower bounds in the streaming and sparse recovery models
by: Do Ba, Khanh
Published: (2012)

Improved lower bounds for constant GC-content DNA codes
by: Chee, Yeow Meng, et al.
Published: (2009)

Almost surely asymptotically constant graph neural networks
by: Adam-Day, S, et al.
Published: (2024)

Continuous-Time Stochastic Games with Time-Bounded Reachability.
by: Brázdil, T, et al.
Published: (2009)

Strong Average-Case Lower Bounds from Non-trivial Derandomization
by: Chen, Lijie, et al.
Published: (2022)

Synthesis of Bounded Integer Parameters for Parametric Timed Reachability Games
by: Jovanović, A, et al.
Published: (2013)

Logarithmic bounds for Roth’s theorem via almost-periodicity
by: Bloom, TF, et al.
Published: (2019)

Stronger connections between circuit analysis and circuit lower bounds, via PCPs of proximity
by: Williams, Richard Ryan, et al.
Published: (2021)

Guaranteed Error Bounds on Approximate Model Abstractions through Reachability Analysis
by: Cardelli, L, et al.
Published: (2018)

Guaranteed error bounds on approximate model abstractions through reachability analysis
by: Cardelli, L, et al.
Published: (2018)

Simple and Fast Derandomization from Very Hard Functions: Eliminating Randomness at Almost No Cost
by: Chen, Lijie, et al.
Published: (2022)

Super-multiplicativity and a lower bound for the decay of the signature of a path of finite length
by: Chang, J, et al.
Published: (2018)

A new bound for t−wise almost universal hash functions
by: Nguyen, L, et al.
Published: (2010)

Impossibility of achieving Landauer’s bound for almost every quantum state
by: Riechers, Paul M., et al.
Published: (2022)

Bounded length intervals containing two primes and an almost-prime
by: Maynard, J
Published: (2013)

Bounded length intervals containing two primes and an almost-prime
by: Maynard, J
Published: (2013)

Relations and equivalences between circuit lower bounds and Karp-Lipton theorems
by: Williams, Richard Ryan, et al.
Published: (2021)

Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
by: Rajgopal, N, et al.
Published: (2018)

Functional Reachability
by: Ong, C, et al.
Published: (2009)

Bubbling with L2-almost constant mean curvature and an Alexandrov-type theorem for crystals
by: Delgadino, MG, et al.
Published: (2018)

Bounded length intervals containing two primes and an almost-prime II
by: Maynard, J
Published: (2015)

New Bounds for Restricted Isometry Constants
by: Cai, T. Tony, et al.
Published: (2011)

ALL METRICS ADMITTING SUPER-COVARIANTLY CONSTANT SPINORS
by: Tod, K
Published: (1983)

Almost primes in almost all short intervals
by: Teräväinen, J
Published: (2016)

On affine reachability problems
by: Jaax, S, et al.
Published: (2020)

Lower bound for dilatations
by: Yazdi, M
Published: (2018)

Demons kernel computation with single-pass stream processing on FPGA
by: Chiew, Wei Ming, et al.
Published: (2013)

Classifying passes in soccer using spatio-temporal data streams
by: Narasimhan, Rajesh
Published: (2015)

Closed almost Kähler 4-manifolds of constant non-negative Hermitian holomorphic sectional curvature are Kähler
by: Lejmi, M, et al.
Published: (2020)

Two-dimensional RC/SW constrained codes: bounded weight and almost balanced weight
by: Nguyen, Tuan Thanh, et al.
Published: (2023)

Almost goodbye
by: Mala Hayati Abdul Khir
Published: (2014)

Interval enclosures for reachable sets of chemical kinetic flow systems. Part 3: Indirect-bounding method
by: Tulsyan, Aditya, et al.
Published: (2020)

Interval enclosures for reachable sets of chemical kinetic flow systems. Part 2: Direct-bounding method
by: Tulsyan, Aditya, et al.
Published: (2021)

Minimal Reachability is Hard to Approximate
by: Jadbabaie, A, et al.
Published: (2023)

Reachability Analysis for Annotated Code
by: Janota, M, et al.
Published: (2007)

Expected Reachability−Time Games
by: Forejt, V, et al.
Published: (2010)