:: Library Catalog

Cover Image

Saved in:

Bibliographic Details
Main Author:	Vrana, Péter
Format:	Preprint
Published:	2024
Subjects:	Computational Complexity
Online Access:	https://arxiv.org/abs/2408.15728
Tags:	Add Tag No Tags, Be the first to tag this record!

Similar Items

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

Asymptotic tensor rank is characterized by polynomials
by: Christandl, Matthias, et al.
Published: (2024)

Barriers for rectangular matrix multiplication
by: Christandl, Matthias, et al.
Published: (2020)

Integer multiplication is at least as hard as matrix transposition
by: Harvey, David, et al.
Published: (2025)

Deterministic Weighted Automata under Partial Observability
by: Michaliszyn, Jakub, et al.
Published: (2024)

One-Way Communication Complexity of Partial XOR Functions
by: Podolskii, Vladimir V., et al.
Published: (2023)

Partial Minimum Branching Program Size Problem is ETH-hard
by: Glinskih, Ludmila, et al.
Published: (2024)

Quantum computational complexity of matrix functions
by: Cifuentes, Santiago, et al.
Published: (2024)

Average-case deterministic query complexity of boolean functions with fixed weight
by: Li, Yuan, et al.
Published: (2024)

Fast interpolation and multiplication of unbalanced polynomials
by: Giorgi, Pascal, et al.
Published: (2024)

Efficient LP warmstarting for linear modifications of the constraint matrix
by: Derval, Guillaume, et al.
Published: (2025)

Partial gathering of mobile agents in dynamic rings
by: Shibata, Masahiro, et al.
Published: (2022)

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

#P-hardness proofs of matrix immanants evaluated on restricted matrices
by: Miklos, Istvan, et al.
Published: (2021)

Approximate all-pairs Hamming distances and 0-1 matrix multiplication
by: Kowaluk, Miroslaw, et al.
Published: (2025)

The moment polytope of matrix multiplication is not maximal
by: Berg, Maxim van den, et al.
Published: (2025)

Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2025)

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes
by: Goyal, Rohan, et al.
Published: (2023)

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

A quasi-optimal lower bound for skew polynomial multiplication
by: Chen, Qiyuan, et al.
Published: (2024)

Hardness of the Binary Covering Radius Problem in Large $\ell_p$ Norms
by: Bennett, Huck, et al.
Published: (2026)

Multiplicative weights, equalizers, and P=PPAD
by: Avramopoulos, Ioannis
Published: (2016)

Exponential Lower Bounds for Smooth 3-LCCs and Sharp Bounds for Designs
by: Kothari, Pravesh K., et al.
Published: (2024)

Fast and simple multiplication of bounded twin-width matrices
by: Kozma, László, et al.
Published: (2026)

Partial Evidence Bench: Benchmarking Authorization-Limited Evidence in Agentic Systems
by: Tallam, Krti
Published: (2026)

Pseudorandomness, symmetry, smoothing: I
by: Derksen, Harm, et al.
Published: (2024)

Pseudorandomness, symmetry, smoothing: II
by: Derksen, Harm, et al.
Published: (2024)

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

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

Uniform Sampling of Proper Graph Colorings via Soft Coloring and Partial Rejection Sampling
by: Moka, Sarat, et al.
Published: (2026)

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

Explicit Commutative ROABPs from Partial Derivatives
by: Bhargava, Vishwas, et al.
Published: (2024)

Computing Hamiltonian Paths with Partial Order Restrictions
by: Beisegel, Jesse, et al.
Published: (2024)

One Color Makes All the Difference in the Tractability of Partial Coloring in Semi-Streaming
by: Das, Avinandan
Published: (2026)

A Graph Width Perspective on Partially Ordered Hamiltonian Paths
by: Beisegel, Jesse, et al.
Published: (2025)

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

Macaulay representation of the prolongation matrix and the SOS conjecture
by: Wang, Zhiwei, et al.
Published: (2025)

Generalization of Cauchy type theorems for matrix Polynomials
by: Qasim, Idrees
Published: (2025)

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

Polynomial time classical versus quantum algorithms for representation theoretic multiplicities
by: Panova, Greta
Published: (2025)