Copertina

Ideals, Macaulay Bases, and PCPs

Fuente: arXiv

Salvato in:

Dettagli Bibliografici
Autori principali:	Amireddy, Prashanth, Behera, Amik Raj, Srinivasan, Srikanth, Sudan, Madhu, Willumsgaard, Sophus Valentin
Natura:	Preprint
Pubblicazione:	2025
Soggetti:	Computational Complexity
Accesso online:	Acceder al recurso
Tags:	Aggiungi Tag Nessun Tag, puoi essere il primo ad aggiungerne!!

Documenti analoghi

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

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

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

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

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

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

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

Algebra in Algorithmic Coding Theory
di: Sudan, Madhu
Pubblicazione: (2025)

Obstructions for Associativity in Stable Homotopy Theory
di: Willumsgaard, Sophus Valentin
Pubblicazione: (2026)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Lossy Catalytic Computation
di: Gupta, Chetan, et al.
Pubblicazione: (2024)

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

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

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

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

Parity $\notin$ QAC0 $\iff$ QAC0 is Fourier-Concentrated
di: Gretta, Lucas, et al.
Pubblicazione: (2026)

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