Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with tensor decomposition:
TR21-045 | 22nd March 2021
Vishwas Bhargava, Shubhangi Saraf, Ilya Volkovich

Reconstruction Algorithms for Low-Rank Tensors and Depth-3 Multilinear Circuits

We give new and efficient black-box reconstruction algorithms for some classes of depth-$3$ arithmetic circuits. As a consequence, we obtain the first efficient algorithm for computing the tensor rank and for finding the optimal tensor decomposition as a sum of rank-one tensors when then input is a {\it constant-rank} tensor. ... more >>>

TR22-125 | 9th September 2022
Shir Peleg, Amir Shpilka, Ben Lee Volk

Tensor Reconstruction Beyond Constant Rank

We give reconstruction algorithms for subclasses of depth-$3$ arithmetic circuits. In particular, we obtain the first efficient algorithm for finding tensor rank, and an optimal tensor decomposition as a sum of rank-one tensors, when given black-box access to a tensor of super-constant rank. Specifically, we obtain the following results:

1. ... more >>>

TR23-170 | 13th November 2023
Pritam Chandra, Ankit Garg, Neeraj Kayal, Kunal Mittal, Tanmay Sinha

Learning Arithmetic Formulas in the Presence of Noise: A General Framework and Applications to Unsupervised Learning

We present a general framework for designing efficient algorithms for unsupervised learning problems, such as mixtures of Gaussians and subspace clustering. Our framework is based on a meta algorithm that learns arithmetic circuits in the presence of noise, using lower bounds. This builds upon the recent work of Garg, Kayal ... more >>>

ISSN 1433-8092 | Imprint