:: Library Catalog

Buchumschlag

Gespeichert in:

Bibliographische Detailangaben
1. Verfasser:	Vrana, Péter
Format:	Preprint
Veröffentlicht:	2024
Schlagworte:	Computational Complexity
Online-Zugang:	https://arxiv.org/abs/2408.15728
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!

Ähnliche Einträge

Canonization of a random graph by two matrix-vector multiplications
von: Verbitsky, Oleg, et al.
Veröffentlicht: (2023)

Asymptotic tensor rank is characterized by polynomials
von: Christandl, Matthias, et al.
Veröffentlicht: (2024)

Barriers for rectangular matrix multiplication
von: Christandl, Matthias, et al.
Veröffentlicht: (2020)

Integer multiplication is at least as hard as matrix transposition
von: Harvey, David, et al.
Veröffentlicht: (2025)

Deterministic Weighted Automata under Partial Observability
von: Michaliszyn, Jakub, et al.
Veröffentlicht: (2024)

One-Way Communication Complexity of Partial XOR Functions
von: Podolskii, Vladimir V., et al.
Veröffentlicht: (2023)

Partial Minimum Branching Program Size Problem is ETH-hard
von: Glinskih, Ludmila, et al.
Veröffentlicht: (2024)

Quantum computational complexity of matrix functions
von: Cifuentes, Santiago, et al.
Veröffentlicht: (2024)

Average-case deterministic query complexity of boolean functions with fixed weight
von: Li, Yuan, et al.
Veröffentlicht: (2024)

Fast interpolation and multiplication of unbalanced polynomials
von: Giorgi, Pascal, et al.
Veröffentlicht: (2024)

Efficient LP warmstarting for linear modifications of the constraint matrix
von: Derval, Guillaume, et al.
Veröffentlicht: (2025)

Partial gathering of mobile agents in dynamic rings
von: Shibata, Masahiro, et al.
Veröffentlicht: (2022)

The Price of Being Partial: Complexity of Partial Generalized Dominating Set on Bounded-Treewidth Graphs
von: Greilhuber, Jakob, et al.
Veröffentlicht: (2025)

#P-hardness proofs of matrix immanants evaluated on restricted matrices
von: Miklos, Istvan, et al.
Veröffentlicht: (2021)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
von: Kowaluk, Miroslaw, et al.
Veröffentlicht: (2025)

The moment polytope of matrix multiplication is not maximal
von: Berg, Maxim van den, et al.
Veröffentlicht: (2025)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2025)

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
von: Goyal, Rohan, et al.
Veröffentlicht: (2023)

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decoding
von: Gu, Shouzhen, et al.
Veröffentlicht: (2026)

A quasi-optimal lower bound for skew polynomial multiplication
von: Chen, Qiyuan, et al.
Veröffentlicht: (2024)

Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms
von: Bennett, Huck, et al.
Veröffentlicht: (2026)

Multiplicative weights, equalizers, and P=PPAD
von: Avramopoulos, Ioannis
Veröffentlicht: (2016)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
von: Kothari, Pravesh K., et al.
Veröffentlicht: (2024)

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

Partial Evidence Bench: Benchmarking Authorization-Limited Evidence in Agentic Systems
von: Tallam, Krti
Veröffentlicht: (2026)

Pseudorandomness, symmetry, smoothing: I
von: Derksen, Harm, et al.
Veröffentlicht: (2024)

Pseudorandomness, symmetry, smoothing: II
von: Derksen, Harm, et al.
Veröffentlicht: (2024)

Relaxed vs. Full Local Decodability with Few Queries: Equivalence and Separations for Linear Codes
von: Grigorescu, Elena, et al.
Veröffentlicht: (2025)

Two weights inequality for Hankel operators on weighted Bergman spaces induced by radial weights
von: Li, Mingjin, et al.
Veröffentlicht: (2025)

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
von: Moka, Sarat, et al.
Veröffentlicht: (2026)

Fourier growth of structured $\mathbb{F}_2$-polynomials and applications
von: Błasiok, Jarosław, et al.
Veröffentlicht: (2021)

Explicit Commutative ROABPs from Partial Derivatives
von: Bhargava, Vishwas, et al.
Veröffentlicht: (2024)

Computing Hamiltonian Paths with Partial Order Restrictions
von: Beisegel, Jesse, et al.
Veröffentlicht: (2024)

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
von: Das, Avinandan
Veröffentlicht: (2026)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
von: Beisegel, Jesse, et al.
Veröffentlicht: (2025)

Matrix-by-matrix multiplication algorithm with $O(N^2log_2N)$ computational complexity for variable precision arithmetic
von: Paszyński, Maciej
Veröffentlicht: (2024)

Macaulay representation of the prolongation matrix and the SOS conjecture
von: Wang, Zhiwei, et al.
Veröffentlicht: (2025)

Generalization of Cauchy type theorems for matrix Polynomials
von: Qasim, Idrees
Veröffentlicht: (2025)

A $k^{\frac{q}{q-2}}$ Lower Bound for Odd Query Locally Decodable Codes from Bipartite Kikuchi Graphs
von: Janzer, Oliver, et al.
Veröffentlicht: (2024)

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
von: Panova, Greta
Veröffentlicht: (2025)