Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > LINEAR ALGEBRA:
Reports tagged with linear algebra:
TR01-028 | 16th March 2001
Thanh Minh Hoang, Thomas Thierauf

#### The Complexity of the Minimal Polynomial

We investigate the computational complexity
of the minimal polynomial of an integer matrix.

We show that the computation of the minimal polynomial
is in AC^0(GapL), the AC^0-closure of the logspace
counting class GapL, which is contained in NC^2.
Our main result is that the problem is hard ... more >>>

TR11-174 | 30th December 2011
Pavel Hrubes, Iddo Tzameret

#### Short Proofs for the Determinant Identities

Revisions: 1

We study arithmetic proof systems $\mathbb{P}_c(\mathbb{F})$ and $\mathbb{P}_f(\mathbb{F})$ operating with arithmetic circuits and arithmetic formulas, respectively, that prove polynomial identities over a field $\mathbb{F}$. We establish a series of structural theorems about these proof systems, the main one stating that $\mathbb{P}_c(\mathbb{F})$ proofs can be balanced: if a polynomial identity of ... more >>>

TR12-146 | 7th November 2012
Venkatesan Guruswami, Chaoping Xing

#### List decoding Reed-Solomon, Algebraic-Geometric, and Gabidulin subcodes up to the Singleton bound

We consider Reed-Solomon (RS) codes whose evaluation points belong to a subfield, and give a linear-algebraic list decoding algorithm that can correct a fraction of errors approaching the code distance, while pinning down the candidate messages to a well-structured affine space of dimension a constant factor smaller than the code ... more >>>

TR13-060 | 10th April 2013
Venkatesan Guruswami, Swastik Kopparty

#### Explicit Subspace Designs

A subspace design is a collection $\{H_1,H_2,\dots,H_M\}$ of subspaces of ${\mathbf F}_q^m$ with the property that no low-dimensional subspace $W$ of ${\mathbf F}_q^m$ intersects too many subspaces of the collection. Subspace designs were introduced by Guruswami and Xing (STOC 2013) who used them to give a randomized construction of optimal ... more >>>

TR13-170 | 2nd December 2013
Venkatesan Guruswami, Carol Wang

#### Explicit rank-metric codes list-decodable with optimal redundancy

We construct an explicit family of linear rank-metric codes over any field ${\mathbb F}_h$ that enables efficient list decoding up to a fraction $\rho$ of errors in the rank metric with a rate of $1-\rho-\epsilon$, for any desired $\rho \in (0,1)$ and $\epsilon > 0$. Previously, a Monte Carlo construction ... more >>>

TR18-017 | 26th January 2018
Venkatesan Guruswami, Nicolas Resch, Chaoping Xing

For a vector space $\mathbb{F}^n$ over a field $\mathbb{F}$, an $(\eta,\beta)$-dimension expander of degree $d$ is a collection of $d$ linear maps $\Gamma_j : \mathbb{F}^n \to \mathbb{F}^n$ such that for every subspace $U$ of $\mathbb{F}^n$ of dimension at most $\eta n$, the image of $U$ under all the maps, $\sum_{j=1}^d ... more >>> TR18-037 | 21st February 2018 Vijay Bhattiprolu, Mrinalkanti Ghosh, Venkatesan Guruswami, Euiwoong Lee, Madhur Tulsiani #### Inapproximability of Matrix$p \rightarrow q$Norms We study the problem of computing the$p\rightarrow q$norm of a matrix$A \in R^{m \times n}$, defined as $\|A\|_{p\rightarrow q} ~:=~ \max_{x \,\in\, R^n \setminus \{0\}} \frac{\|Ax\|_q}{\|x\|_p}$ This problem generalizes the spectral norm of a matrix ($p=q=2$) and the Grothendieck problem ($p=\infty$,$q=1$), and has been ... more >>> TR18-103 | 30th April 2018 Zhao Song, David Woodruff, Peilin Zhong #### Relative Error Tensor Low Rank Approximation We consider relative error low rank approximation of tensors with respect to the Frobenius norm. Namely, given an order-$q$tensor$A \in \mathbb{R}^{\prod_{i=1}^q n_i}$, output a rank-$k$tensor$B$for which$\|A-B\|_F^2 \leq (1+\epsilon) {\rm OPT}$, where${\rm OPT} = \inf_{\textrm{rank-}k~A'} \|A-A'\|_F^2$. Despite much success on obtaining relative error low ... more >>> TR19-005 | 16th January 2019 Omar Alrabiah, Venkatesan Guruswami #### An Exponential Lower Bound on the Sub-Packetization of MSR Codes Revisions: 1 An$(n,k,\ell)$-vector MDS code is a$\mathbb{F}$-linear subspace of$(\mathbb{F}^\ell)^n$(for some field$\mathbb{F}$) of dimension$k\ell$, such that any$k$(vector) symbols of the codeword suffice to determine the remaining$r=n-k$(vector) symbols. The length$\ell$of each codeword symbol is called the sub-packetization of the code. Such a ... more >>> TR21-145 | 19th October 2021 Omar Alrabiah, Venkatesan Guruswami #### Revisiting a Lower Bound on the Redundancy of Linear Batch Codes A recent work of Li and Wootters (2021) shows a redundancy lower bound of$\Omega(\sqrt{Nk})$for systematic linear$k$-batch codes of block length$N$by looking at the$O(k)\$ tensor power of the dual code. In this note, we present an alternate proof of their result via a linear independence ... more >>>

ISSN 1433-8092 | Imprint