Cover Image

Optimal $e^{(γ+o(1))n}$-Approximation of the Permanent of Positive Semidefinite Matrices

Fuente: arXiv

Saved in:

Bibliographic Details
Main Authors:	Anari, Nima, Ebrahimnejad, Farzam
Format:	Preprint
Published:	2026
Subjects:	Data Structures and Algorithms
Online Access:	Acceder al recurso
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

On approximability of the Permanent of PSD matrices
by: Ebrahimnejad, Farzam, et al.
Published: (2024)

Sparsifying Sums of Positive Semidefinite Matrices
by: Basu, Arpon, et al.
Published: (2025)

Constant-Stretch Rounding on the Hypersimplex
by: Anari, Nima, et al.
Published: (2026)

Fast Spanning Tree Sampling in Broadcast Congested Clique
by: Anari, Nima, et al.
Published: (2026)

Trickle-Down in Localization Schemes and Applications
by: Anari, Nima, et al.
Published: (2024)

Linear Programming Based Near-Optimal Pricing for Laminar Bayesian Online Selection
by: Anari, Nima, et al.
Published: (2018)

Fast parallel sampling under isoperimetry
by: Anari, Nima, et al.
Published: (2024)

Parallel Sampling via Counting
by: Anari, Nima, et al.
Published: (2024)

Fair-Count-Min: Frequency Estimation under Equal Group-wise Approximation Factor
by: Shahbazi, Nima, et al.
Published: (2025)

Optimal FPT-Approximability for Modular Linear Equations
by: Dabrowski, Konrad K., et al.
Published: (2026)

Optimal 4-Approximation for the Correlated Pandora's Problem
by: Bansal, Nikhil, et al.
Published: (2025)

Approximations for Fault-Tolerant Total and Partial Positive Influence Domination
by: Lamprou, Ioannis, et al.
Published: (2025)

A 0.51-Approximation of Maximum Matching in Sublinear $n^{1.5}$ Time
by: Mahabadi, Sepideh, et al.
Published: (2025)

Optimal Approximate Matrix Multiplication over Sliding Window
by: Xian, Haoming, et al.
Published: (2025)

Constant Approximation of Arboricity in Near-Optimal Sublinear Time
by: Dai, Jiangqi, et al.
Published: (2025)

$O(\log n)$-Approximation Algorithms for Bipartiteness Ratio
by: Soma, Tasuku, et al.
Published: (2025)

An Optimal Product-State Approximation for 2-Local Quantum Hamiltonians with Positive Terms
by: Parekh, Ojas, et al.
Published: (2022)

Variational Quantum Algorithms for Semidefinite Programming
by: Patel, Dhrumil, et al.
Published: (2021)

Sublinear Time Low-Rank Approximation of Hankel Matrices
by: Kapralov, Michael, et al.
Published: (2025)

Sublinear Time Low-Rank Approximation of Toeplitz Matrices
by: Musco, Cameron, et al.
Published: (2024)

Parallel $(1+ε)$-Approximate Multi-Commodity Mincost Flow in Almost Optimal Depth and Work
by: Haeupler, Bernhard, et al.
Published: (2025)

Dynamic $((1+ε)\ln n)$-Approximation Algorithms for Minimum Set Cover and Dominating Set
by: Solomon, Shay, et al.
Published: (2023)

Optimal Approximations for the Requirement Cut Problem on Sparse Graph Classes
by: Mallek, Nadym, et al.
Published: (2025)

Improving the Threshold for Finding Rank-1 Matrices in a Subspace
by: Dastidar, Jeshu, et al.
Published: (2025)

Semidefinite Programming for the Asymmetric Stochastic Block Model
by: Gaudio, Julia, et al.
Published: (2025)

An $O(n^5)$-Time Algorithm for Optimal Broadcast Domination
by: Papadopoulos, Kleitos
Published: (2026)

Sparse Random Matrices for Dimensionality Reduction
by: Mackenzie, Pierre
Published: (2025)

Folklore Sampling is Optimal for Exact Hopsets: Confirming the $\sqrt{n}$ Barrier
by: Bodwin, Greg, et al.
Published: (2023)

Toward Optimal Approximations for Resource-Minimization for Fire Containment on Trees and Non-Uniform k-Center
by: Blauth, Jannis, et al.
Published: (2025)

Dynamic Deterministic Constant-Approximate Distance Oracles with $n^ε$ Worst-Case Update Time
by: Haeupler, Bernhard, et al.
Published: (2024)

Near-Optimal Parallel Approximate Counting via Sampling
by: Harris, David G., et al.
Published: (2026)

Maximum Flow by Augmenting Paths in $n^{2+o(1)}$ Time
by: Bernstein, Aaron, et al.
Published: (2024)

Approximation Algorithms for Optimal Hopsets
by: Dinitz, Michael, et al.
Published: (2025)

Approximating $q \rightarrow p$ Norms of Non-Negative Matrices in Nearly-Linear Time
by: Objois, Étienne, et al.
Published: (2025)

Efficient Algorithms for Partitioning Circulant Graphs with Optimal Spectral Approximation
by: Gavva, Surya Teja, et al.
Published: (2025)

Engineering Insights into Biclique Partitions and Fractional Binary Ranks of Matrices
by: Ghosal, Angikar, et al.
Published: (2025)

A $(\frac32+\frac1{\mathrm{e}})$-Approximation Algorithm for Ordered TSP
by: Armbruster, Susanne, et al.
Published: (2024)

Approximating Optimal Labelings for Temporal Connectivity
by: Carnevale, Daniele, et al.
Published: (2025)

An $n^{2+o(1)}$ Time Algorithm for Single-Source Negative Weight Shortest Paths
by: Khanna, Sanjeev, et al.
Published: (2026)

Maximum Bipartite Matching in $n^{2+o(1)}$ Time via a Combinatorial Algorithm
by: Chuzhoy, Julia, et al.
Published: (2024)