Buchumschlag

Near Optimal Alphabet-Soundness Tradeoff PCPs

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Minzer, Dor, Zheng, Kai Zhe
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity Data Structures and Algorithms
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Near-Optimal Space Lower Bounds for Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2026)

A Dichotomy Theorem for Multi-Pass Streaming CSPs
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Multi-Pass Streaming Lower Bounds for Approximating Max-Cut
von: Fei, Yumou, et al.
Veröffentlicht: (2025)

Perfect Zero-Knowledge PCPs for #P
von: Gur, Tom, et al.
Veröffentlicht: (2024)

Near-Optimal Averaging Samplers and Matrix Samplers
von: Xun, Zhiyang, et al.
Veröffentlicht: (2024)

Near-Optimality for Single-Source Personalized PageRank
von: Jiang, Xinpeng, et al.
Veröffentlicht: (2025)

Alphabet Reduction for Reconfiguration Problems
von: Ohsaka, Naoto
Veröffentlicht: (2024)

A Unified Approach to Memory-Sample Tradeoffs for Detecting Planted Structures
von: Garg, Sumegha, et al.
Veröffentlicht: (2026)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
von: Mao, Songtao
Veröffentlicht: (2026)

Self-referential instances of the dominating set problem are irreducible
von: Zhou, Guangyan
Veröffentlicht: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
von: Cohen-Addad, Vincent, et al.
Veröffentlicht: (2026)

Computational-Statistical Tradeoffs from NP-hardness
von: Blanc, Guy, et al.
Veröffentlicht: (2025)

On Optimal Testing of Linearity
von: Arora, Vipul, et al.
Veröffentlicht: (2024)

Linear Hashing Is Optimal
von: Jaber, Michael, et al.
Veröffentlicht: (2025)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
von: Dell, Holger, et al.
Veröffentlicht: (2022)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
von: Sajith, Thejas Radhika
Veröffentlicht: (2025)

Near Optimal Hardness of Approximating $k$-CSP
von: Minzer, Dor, et al.
Veröffentlicht: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
von: Khanna, Sanjeev, et al.
Veröffentlicht: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
von: Singer, Noah G., et al.
Veröffentlicht: (2026)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
von: Wallisch, Christian, et al.
Veröffentlicht: (2025)

Gradient Descent is Pareto-Optimal in the Oracle Complexity and Memory Tradeoff for Feasibility Problems
von: Blanchard, Moise
Veröffentlicht: (2024)

Quasi-Linear Size PCPs with Small Soundness from HDX
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

Equivalent Instances for Scheduling and Packing Problems
von: Jansen, Klaus, et al.
Veröffentlicht: (2025)

A General Framework for Low Soundness Homomorphism Testing
von: Mittal, Tushant, et al.
Veröffentlicht: (2025)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
von: Lee, Euiwoong, et al.
Veröffentlicht: (2024)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
von: Chia, Nai-Hui, et al.
Veröffentlicht: (2025)

Computation-Utility-Privacy Tradeoffs in Bayesian Estimation
von: Chen, Sitan, et al.
Veröffentlicht: (2026)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
von: Dvijotham, Krishnamurthy, et al.
Veröffentlicht: (2024)

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

Optimality of Frequency Moment Estimation
von: Braverman, Mark, et al.
Veröffentlicht: (2024)

Constant Degree Networks for Almost-Everywhere Reliable Transmission
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
von: Srivastava, Shashank, et al.
Veröffentlicht: (2025)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
von: Abbas, Amira, et al.
Veröffentlicht: (2025)

Counting Locally Optimal Tours in the TSP
von: Manthey, Bodo, et al.
Veröffentlicht: (2024)

Can You Link Up With Treewidth?
von: Curticapean, Radu, et al.
Veröffentlicht: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
von: Wang, Yichuan
Veröffentlicht: (2024)

Simple approximation algorithms for Polyamorous Scheduling
von: Biktairov, Yuriy, et al.
Veröffentlicht: (2024)

Size Minimization For Multi-Output AND-Functions
von: Armbruster, Susanne
Veröffentlicht: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
von: Stoian, Mihail
Veröffentlicht: (2024)