Matrix powering, and more generally iterated matrix multiplication, is a fundamental linear
algebraic primitive with myriad applications in computer science. Of particular interest is the …

Let L be a language that can be decided in linear space and let ϵ\gt0 be any constant. Let A
be the exponential hardness assumption that for every n, membership in L for inputs of …

Rounding has proven to be a fundamental tool in theoretical computer science. By
observing that rounding and partitioning of $\mathbb {R}^ d $ are equivalent, we introduce …

A partition $\mathcal {P} $ of $\mathbb {R}^ d $ is called a $(k,\varepsilon) $-secluded
partition if, for every $\vec {p}\in\mathbb {R}^ d $, the ball $\overline {B} …

In the field of computational complexity theory, we study the power and limits of different
computational resources and the interplay between them. The constraints on space …

Approximating Large Powers of Stochastic Matrices in Small Space Page 1 Approximating Large
Powers of Stochastic Matrices in Small Space Gil Cohen* Dept. of Computer Science Tel Aviv …

We introduce and investigate a natural problem regarding unit cube tilings/partitions of
Euclidean space and also consider broad generalizations of this problem. The problem fits …

For any function $ f: X\times Y\to Z $, we prove that $ Q^{*\text {cc}}(f)\cdot Q^{\text
{OIP}}(f)\cdot (\log Q^{\text {OIP}}(f)+\log| Z|)\geq\Omega (\log| X|) $. Here, $ Q^{*\text {cc}}(f) …