Buchumschlag

On approximability of the Permanent of PSD matrices

Fuente: arXiv

Gespeichert in:

Bibliographische Detailangaben
Hauptverfasser:	Ebrahimnejad, Farzam, Nagda, Ansh, Gharan, Shayan Oveis
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Data Structures and Algorithms Computational Complexity
Online-Zugang:	Acceder al recurso
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Trickle-down Theorems via C-Lorentzian Polynomials II: Pairwise Spectral Influence and Improved Dobrushin's Condition
von: Leake, Jonathan, et al.
Veröffentlicht: (2025)

Sampling from the Hardcore Model on Random Regular Bipartite Graphs above the Uniqueness Threshold
von: Kocurek, Nicholas, 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)

On optimal distinguishers for Planted Clique
von: Nagda, Ansh, et al.
Veröffentlicht: (2025)

Optimal $e^{(γ+o(1))n}$-Approximation of the Permanent of Positive Semidefinite Matrices
von: Anari, Nima, et al.
Veröffentlicht: (2026)

On Thin Perfect Matchings up to Polylogarithmic Factors
von: Haqi, Alireza, et al.
Veröffentlicht: (2026)

Unweighted One-Sided Code Sparsifiers and Thin Subgraphs
von: Gharan, Shayan Oveis, et al.
Veröffentlicht: (2025)

Improved approximation algorithms for the EPR Hamiltonian
von: Ju, Nathan, et al.
Veröffentlicht: (2025)

Sketching approximations and LP approximations for finite CSPs are related
von: Singer, Noah G., et al.
Veröffentlicht: (2025)

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

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

A quantum neural network framework for scalable quantum circuit approximation of unitary matrices
von: Sarkar, Rohit Sarma, et al.
Veröffentlicht: (2024)

Streaming approximation resistance of every ordering CSP
von: Singer, Noah G., et al.
Veröffentlicht: (2021)

On the complexity and approximability of Bounded access Lempel Ziv coding
von: Cicalese, Ferdinando, et al.
Veröffentlicht: (2024)

Additive approximation algorithm for geodesic centers in $δ$-hyperbolic graphs
von: Chakraborty, Dibyayan, et al.
Veröffentlicht: (2024)

MAX BISECTION might be harder to approximate than MAX CUT
von: Brakensiek, Joshua, et al.
Veröffentlicht: (2025)

Nine lower bound conjectures on streaming approximation algorithms for CSPs
von: Singer, Noah G.
Veröffentlicht: (2025)

Fast and simple multiplication of bounded twin-width matrices
von: Kozma, László, et al.
Veröffentlicht: (2026)

A note on approximating the average degree of bounded arboricity graphs
von: Eden, Talya, et al.
Veröffentlicht: (2026)

On the tractability and approximability of non-submodular cardinality-based $s$-$t$ cut problems in hypergraphs
von: Bengali, Vedangi, 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)

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)

Cluster Editing on Cographs and Related Classes
von: Lafond, Manuel, et al.
Veröffentlicht: (2024)

Improved Hardness-of-Approximation for Token Swapping
von: Hiken, Sam, et al.
Veröffentlicht: (2024)

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

Parameterized Vertex Integrity Revisited
von: Hanaka, Tesshu, et al.
Veröffentlicht: (2024)

Further Explanations on "SAT Requires Exhaustive Search"
von: Dong, Qingxiu, et al.
Veröffentlicht: (2024)

PCF Learned Sort: a Learning Augmented Sort Algorithm with $O(n \log\log n)$ Expected Complexity
von: Sato, Atsuki, et al.
Veröffentlicht: (2024)

Randomized query composition and product distributions
von: Sanyal, Swagato
Veröffentlicht: (2024)

Minimizing the Weighted Number of Tardy Jobs is W[1]-hard
von: Heeger, Klaus, et al.
Veröffentlicht: (2024)

The Art of Staying Ahead of Deadlines: Improved Algorithms for the Minimum Tardy Processing Time
von: Stoian, Mihail
Veröffentlicht: (2024)

On Permutation Selectors and their Applications in Ad-Hoc Radio Networks Protocols
von: Kuschner, Jordan, et al.
Veröffentlicht: (2024)

A constant time complexity algorithm for the unbounded knapsack problem with bounded coefficients
von: Yang, Yang
Veröffentlicht: (2024)

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
von: Kumar, Mrinal, et al.
Veröffentlicht: (2024)

Solving Polynomial Equations Over Finite Fields
von: Dell, Holger, et al.
Veröffentlicht: (2024)

The Structural Complexity Landscape of Finding Balance-Fair Shortest Paths
von: Bentert, Matthias, et al.
Veröffentlicht: (2024)

Rounding Large Independent Sets on Expanders
von: Bafna, Mitali, et al.
Veröffentlicht: (2024)

Revisiting Tree Canonization using polynomials
von: Arvind, V., et al.
Veröffentlicht: (2024)