Image de couverture de livre

Near-Optimal Averaging Samplers and Matrix Samplers

Fuente: arXiv

Enregistré dans:

Détails bibliographiques
Auteurs principaux:	Xun, Zhiyang, Zuckerman, David
Format:	Preprint
Publié:	2024
Sujets:	Computational Complexity Data Structures and Algorithms
Accès en ligne:	Acceder al recurso
Tags:	Ajouter un tag Pas de tags, Soyez le premier à ajouter un tag!

Documents similaires

Hypergraph Samplers: Typical and Worst Case Behavior
par: Alev, Vedat Levi, et autres
Publié: (2026)

Linear Hashing Is Optimal
par: Jaber, Michael, et autres
Publié: (2025)

Near Optimal Alphabet-Soundness Tradeoff PCPs
par: Minzer, Dor, et autres
Publié: (2024)

Near-Optimality for Single-Source Personalized PageRank
par: Jiang, Xinpeng, et autres
Publié: (2025)

Near-Optimal Space Lower Bounds for Streaming CSPs
par: Fei, Yumou, et autres
Publié: (2026)

Near Optimal Algorithms for Noisy $k$-XOR under Low-Degree Heuristic
par: Mao, Songtao
Publié: (2026)

Near-Optimal Bounds for Parameterized Euclidean k-means
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Self-referential instances of the dominating set problem are irreducible
par: Zhou, Guangyan
Publié: (2026)

Quantum Worst-Case to Average-Case Reduction for Matrix-Vector Multiplication
par: Aggarwal, Divesh, et autres
Publié: (2025)

More Asymmetry Yields Faster Matrix Multiplication
par: Alman, Josh, et autres
Publié: (2024)

On Optimal Testing of Linearity
par: Arora, Vipul, et autres
Publié: (2024)

Nearly optimal independence oracle algorithms for edge estimation in hypergraphs
par: Dell, Holger, et autres
Publié: (2022)

Subset Sum in Near-Linear Pseudopolynomial Time and Polynomial Space
par: Sajith, Thejas Radhika
Publié: (2025)

Graded Projection Recursion (GPR): Corrections, Obstructions, and Conservative Approximate Matrix Multiplication
par: Uhlmann, Jeffrey
Publié: (2025)

Automated Lower Bounds for Small Matrix Multiplication Complexity over Finite Fields
par: Wang, Chengu
Publié: (2026)

An Exact 56-Addition, Rank-23 Scheme for General 3*3 Matrix Multiplication
par: Sun, Yinqi
Publié: (2026)

A Fast Coloring Oracle for Average Case Hypergraphs
par: Marcussen, Cassandra, et autres
Publié: (2025)

Optimal Parallel Basis Finding in Graphic and Related Matroids
par: Khanna, Sanjeev, et autres
Publié: (2025)

Optimal Single-Pass Streaming Lower Bounds for Approximating CSPs
par: Singer, Noah G., et autres
Publié: (2026)

Placing Green Bridges Optimally, with Close-Range Habitats in Sparse Graphs
par: Wallisch, Christian, et autres
Publié: (2025)

A Refined Laser Method and Faster Matrix Multiplication
par: Alman, Josh, et autres
Publié: (2020)

Quantum Channel Testing in Average-Case Distance
par: Rosenthal, Gregory, et autres
Publié: (2024)

Almost-Optimal Upper and Lower Bounds for Clustering in Low Dimensional Euclidean Spaces
par: Cohen-Addad, Vincent, et autres
Publié: (2026)

Asymptotically Optimal Hardness for $k$-Set Packing and $k$-Matroid Intersection
par: Lee, Euiwoong, et autres
Publié: (2024)

Streaming Complexity Separations for Dense and Sparse Graphs
par: Liu, Yang P., et autres
Publié: (2026)

Gray Codes With Constant Delay and Constant Auxiliary Space
par: Amarilli, Antoine, et autres
Publié: (2026)

3-Local Hamiltonian Problem and Constant Relative Error Quantum Partition Function Approximation: $O(2^{\frac{n}{2}})$ Algorithm Is Nearly Optimal under QSETH
par: Chia, Nai-Hui, et autres
Publié: (2025)

A New Information Complexity Measure for Multi-pass Streaming with Applications
par: Braverman, Mark, et autres
Publié: (2024)

Optimal Trickle-Down Theorems for Path Complexes via C-Lorentzian Polynomials with Applications to Sampling and Log-Concave Sequences
par: Leake, Jonathan, et autres
Publié: (2025)

It's Hard to HAC with Average Linkage!
par: Bateni, MohammadHossein, et autres
Publié: (2024)

Efficient and Near-Optimal Noise Generation for Streaming Differential Privacy
par: Dvijotham, Krishnamurthy, et autres
Publié: (2024)

Optimality of Frequency Moment Estimation
par: Braverman, Mark, et autres
Publié: (2024)

List Decoding Expander-Based Codes up to Capacity in Near-Linear Time
par: Srivastava, Shashank, et autres
Publié: (2025)

Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
par: Abbas, Amira, et autres
Publié: (2025)

Counting Locally Optimal Tours in the TSP
par: Manthey, Bodo, et autres
Publié: (2024)

Can You Link Up With Treewidth?
par: Curticapean, Radu, et autres
Publié: (2024)

Tight Streaming Lower Bounds for Deterministic Approximate Counting
par: Wang, Yichuan
Publié: (2024)

Simple approximation algorithms for Polyamorous Scheduling
par: Biktairov, Yuriy, et autres
Publié: (2024)

Size Minimization For Multi-Output AND-Functions
par: Armbruster, Susanne
Publié: (2024)

TSP Escapes the $O(2^n n^2)$ Curse
par: Stoian, Mihail
Publié: (2024)