:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Ron-Zewi, Noga, Shaltiel, Ronen, Varma, Nithin
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2409.01708
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

Advances in List Decoding of Polynomial Codes
by: Kumar, Mrinal, et al.
Published: (2026)

Simple Constructions of Unique Neighbor Expanders from Error-correcting Codes
by: Kopparty, Swastik, et al.
Published: (2023)

LDPC Codes Achieve List Decoding Capacity
by: Mosheiff, Jonathan, et al.
Published: (2019)

Deterministic list decoding of Reed-Solomon codes
by: Chatterjee, Soham, et al.
Published: (2025)

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2023)

Pseudodeterministic Algorithms for Minimum Cut Problems
by: Agarwala, Aryan, et al.
Published: (2025)

Efficient List-decoding of Polynomial Ideal Codes with Optimal List Size
by: Ron-Zewi, Noga, et al.
Published: (2024)

Negations are powerful even in small depth
by: Cavalar, Bruno, et al.
Published: (2025)

An even simpler hard variant of Not-All-Equal 3-SAT
by: Darmann, Andreas, et al.
Published: (2024)

An exposition of recent list-size bounds of FRS Codes
by: Garg, Abhibhav, et al.
Published: (2025)

Circuit metaconstruction in logspace for Rice-like complexity lower bounds in ANs and SGRs
by: Goubault-Larrecq, Aliénor, et al.
Published: (2025)

Two NP-hard Extensions of the Spearman Footrule even for a Small Constant Number of Voters
by: Durand, Martin
Published: (2026)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
by: Gu, Shouzhen, et al.
Published: (2026)

Rice-like complexity lower bounds for Boolean and uniform automata networks
by: Goubault-Larrecq, Aliénor, et al.
Published: (2024)

A note on quantum lower bounds for local search via congestion and expansion
by: Brânzei, Simina, et al.
Published: (2024)

Exponential lower bound via exponential sums
by: Bhattacharjee, Somnath, et al.
Published: (2026)

Simple general magnification of circuit lower bounds
by: Atserias, Albert, et al.
Published: (2025)

Walking through Doors is Hard, even without Staircases: Universality and PSPACE-hardness of Planar Door Gadgets
by: MIT Gadgets Group, et al.
Published: (2020)

Depth lower bounds in Stabbing Planes for combinatorial principles
by: Dantchev, Stefan, et al.
Published: (2021)

Backward explanations via redefinition of predicates
by: Saulières, Léo, et al.
Published: (2024)

On the consistency of stronger lower bounds for NEXP
by: Thapen, Neil
Published: (2025)

Quantum circuit lower bounds in the magic hierarchy
by: Parham, Natalie
Published: (2025)

A note on Jerabek's paper "A simplified lower bound for implicational logic"
by: Gordeev, Lev, et al.
Published: (2026)

Quasi-linear time decoding of RS and AG codes for burst errors up to the Singleton bound
by: Li, Songsong, et al.
Published: (2025)

Query complexity of Boolean functions on the middle slice of the cube
by: Gerbner, Dániel, et al.
Published: (2023)

A nearly-$4\log n$ depth lower bound for formulas with restriction on top
by: Wu, Hao
Published: (2024)

A Note on the Equivalence Between Zero-knowledge and Quantum CSS Codes
by: Ron-Zewi, Noga, et al.
Published: (2026)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2025)

Robust predicate and function computation in continuous chemical reaction networks
by: Calabrese, Kim, et al.
Published: (2025)

Fermionic Independent Set and Laplacian of an independence complex are QMA-hard
by: Rayudu, Chaithanya
Published: (2024)

On the hardness of recognizing graphs of small mim-width and its variants
by: la Tour, Max Dupré, et al.
Published: (2025)

Query maintenance under batch changes with small-depth circuits
by: Datta, Samir, et al.
Published: (2024)

Computational lower bounds for multi-frequency group synchronization
by: Kireeva, Anastasia, et al.
Published: (2024)

Relative-error testing of conjunctions and decision lists
by: Chen, Xi, et al.
Published: (2025)

Complexity lower bounds for succinct binary structures of bounded clique-width with restrictions
by: Geniet, Colin, et al.
Published: (2026)

A quasi-optimal lower bound for skew polynomial multiplication
by: Chen, Qiyuan, et al.
Published: (2024)

Quantum Polynomial Hierarchies: Karp-Lipton, error reduction, and lower bounds
by: Agarwal, Avantika, et al.
Published: (2024)

Parity Tests with Ties
by: Kupfer, Ron
Published: (2026)

Clifford testing: algorithms and lower bounds
by: Hinsche, Marcel, et al.
Published: (2025)

A simple lower bound for the complexity of estimating partition functions on a quantum computer
by: Chen, Zherui, et al.
Published: (2024)