:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Authors:	Amireddy, Prashanth, Behera, Amik Raj, Srinivasan, Srikanth, Sudan, Madhu, Willumsgaard, Sophus Valentin
Format:	Preprint
Published:	2025
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2511.03703
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

A Near-Optimal Polynomial Distance Lemma Over Boolean Slices
by: Amireddy, Prashanth, et al.
Published: (2025)

Eigenvalue Bounds for Symmetric Markov Chains on Multislices With Applications
by: Amireddy, Prashanth, et al.
Published: (2025)

Local Correction of Linear Functions over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Low Degree Local Correction Over the Boolean Cube
by: Amireddy, Prashanth, et al.
Published: (2024)

Low-Degree Testing Over Grids
by: Amireddy, Prashanth, et al.
Published: (2023)

New Bounds for the Ideal Proof System in Positive Characteristic
by: Behera, Amik Raj, et al.
Published: (2025)

Separation Results for Constant-Depth and Multilinear Ideal Proof Systems
by: Behera, Amik Raj, et al.
Published: (2026)

Algebra in Algorithmic Coding Theory
by: Sudan, Madhu
Published: (2025)

Obstructions for Associativity in Stable Homotopy Theory
by: Willumsgaard, Sophus Valentin
Published: (2026)

Improved PIR Schemes using Matching Vectors and Derivatives
by: Ghasemi, Fatemeh, et al.
Published: (2024)

Expanders Meet Reed-Muller: Easy Instances of Noisy k-XOR
by: Błasiok, Jarosław, et al.
Published: (2026)

Sketching approximability of all finite CSPs
by: Chou, Chi-Ning, et al.
Published: (2021)

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

Quasi-Linear Size PCPs with Small Soundness from HDX
by: Bafna, Mitali, et al.
Published: (2024)

Communication with Imperfectly Shared Randomness
by: Canonne, Clément L., et al.
Published: (2014)

Near Optimal Alphabet-Soundness Tradeoff PCPs
by: Minzer, Dor, et al.
Published: (2024)

Low-soundness direct-product testers and PCPs from Kaufman--Oppenheim complexes
by: O'Donnell, Ryan, et al.
Published: (2025)

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

Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians
by: Buhrman, Harry, et al.
Published: (2024)

Classical versus quantum queries in quantum PCPs with classical proofs
by: Buhrman, Harry, et al.
Published: (2024)

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

The Algebraic Cost of a Boolean Sum
by: Orzel, Ian, et al.
Published: (2025)

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

On Closure Properties of Read-Once Oblivious Algebraic Branching Programs
by: Armand, Jules, et al.
Published: (2025)

Hard CNF Instances for Ideal Proof Systems
by: Hakoniemi, Tuomas, et al.
Published: (2026)

Lower Bounds against the Ideal Proof System in Finite Fields
by: Elbaz, Tal, et al.
Published: (2025)

Symmetric Proofs in the Ideal Proof System
by: Dawar, Anuj, et al.
Published: (2025)

Debordering Closure Results in Determinantal and Pfaffian Ideals
by: Dey, Anakin, et al.
Published: (2025)

Macaulay representation of the prolongation matrix and the SOS conjecture
by: Wang, Zhiwei, et al.
Published: (2025)

Primes via Zeros: Interactive Proofs for Testing Primality of Natural Classes of Ideals
by: Garg, Abhibhav, et al.
Published: (2025)

Trade-offs between Entanglement and Communication
by: Arunachalam, Srinivasan, et al.
Published: (2023)

Distributed inner product estimation with limited quantum communication
by: Arunachalam, Srinivasan, et al.
Published: (2024)

Learning stabilizer structure of quantum states
by: Arunachalam, Srinivasan, et al.
Published: (2025)

Quantum Lifting for Invertible Permutations and Ideal Ciphers
by: Cojocaru, Alexandru, et al.
Published: (2025)

Ideal Membership Problem for Boolean Minority and Dual Discriminator
by: Bharathi, Arpitha P., et al.
Published: (2024)

Some results related to Macaulay's Theorem about Hilbert functions and applications
by: Gao, Yun
Published: (2025)

Lossy Catalytic Computation
by: Gupta, Chetan, et al.
Published: (2024)

Constant-Depth Unitary Preparation of Dicke States
by: Joshi, Malvika Raj, et al.
Published: (2026)

Matrix hypercontractivity, streaming algorithms and LDCs: the large alphabet case
by: Arunachalam, Srinivasan, et al.
Published: (2021)

Polynomial-time tolerant testing stabilizer states
by: Arunachalam, Srinivasan, et al.
Published: (2024)