### Interval Linear Algebra and Computational Complexity

**2016-02-01**

1602.00349 | cs.CC

This work connects two mathematical fields - computational complexity and
interval linear algebra. It introduces the basic topics of interval linear
algebra - regularity and singularity, full column rank, solving a linear
system, deciding solvability of a linear system, computing inverse matrix,
eigenvalues, checking positive (semi)definiteness or stability. We discuss
these problems and relations between them from the view of computational
complexity. Many problems in interval linear algebra are intractable, hence we
emphasize subclasses of these problems that are easily solvable or decidable.
The aim of this work is to provide a basic insight into this field and to
provide materials for further reading and research.

**Login to like/save this paper, take notes and configure your recommendations**

# Related Articles

**2017-01-08**

1701.01994 | cs.SC

Differential (Ore) type polynomials with "approximate" polynomial
coefficients are introduced. These… show more

**2017-12-18**

1712.06309 | math.OC

In this paper, we present FPT-algorithms for special cases of the shortest
lattice vector, integer l… show more

**2019-03-15**

1903.10272 | math.NA

The work is devoted to the development of numerical methods for computing
"formal solutions" of inte… show more

**2017-01-23**

1701.06386 | cs.CC

Weighted counting problems are a natural generalization of counting problems
where a weight is assoc… show more

**2017-08-11**

1708.03495 | cs.DS

We consider two basic algorithmic problems concerning tuples of
(skew-)symmetric matrices. The first… show more

**2018-06-04**

1806.01050 | cs.IT

In this work, we study the computational complexity of the Minimum Distance
Code Detection problem. … show more

**2019-04-02**

1904.01182 | cs.CC

We study the problem of constructing explicit families of matrices which
cannot be expressed as a pr… show more

**2019-03-05**

1903.01869 | math.NA

The main focus of this paper is the characterization and exploitation of the
asymptotic spectrum of … show more

**2018-12-15**

1812.06295 | cs.DS

In this paper we show how to recover a spectral approximations to broad
classes of structured matric… show more

**2019-03-15**

1903.06350 | cs.DS

Subset selection for matrices is the task of extracting a column sub-matrix
from a given matrix $B\i… show more

**2016-10-10**

1610.02962 | stat.ML

This work studies the linear approximation of high-dimensional dynamical
systems using low-rank dyna… show more

**2018-11-05**

1811.01885 | cs.DS

Consider the following fundamental learning problem: given input examples $x
\in \mathbb{R}^d$ and t… show more

**2018-07-22**

1807.09120 | cs.SY

Stabilization of linear systems with unknown dynamics is a canonical problem
in adaptive control. Si… show more

**2018-12-11**

1812.04590 | cs.SC

We consider the problem of computing the nearest matrix polynomial with a
non-trivial Smith Normal F… show more

**2018-10-04**

1810.02348 | cs.DS

In this paper we provide nearly linear time algorithms for several problems
closely associated with … show more

**2017-06-08**

1706.02586 | math.OC

In recent years, optimization theory has been greatly impacted by the advent
of sum of squares (SOS)… show more