Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > EXPONENTIAL TIME ALGORITHMS:
Reports tagged with exponential time algorithms:
TR16-022 | 22nd February 2016
Alexander Golovnev, Alexander Kulikov, Alexander Smal, Suguru Tamaki

#### Circuit size lower bounds and #SAT upper bounds through a general framework

Revisions: 2

Most of the known lower bounds for binary Boolean circuits with unrestricted depth are proved by the gate elimination method. The most efficient known algorithms for the #SAT problem on binary Boolean circuits use similar case analyses to the ones in gate elimination. Chen and Kabanets recently showed that the ... 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 >>>

ISSN 1433-8092 | Imprint