enter search term and/or author name
Tensor-Rank and Lower Bounds for Arithmetic Formulas
Article No.: 40
We show that any explicit example for a tensor A : [n]r → F with tensor-rank ≥ nrċ(1−o(1)), where r = r(n) ≤ log n/log log n is...
Persistence-Based Clustering in Riemannian Manifolds
Frédéric Chazal, Leonidas J. Guibas, Steve Y. Oudot, Primoz Skraba
Article No.: 41
We present a clustering scheme that combines a mode-seeking phase with a cluster merging phase in the corresponding density map. While mode detection is done by a standard graph-based hill-climbing scheme, the novelty of our approach resides in...
Tractable Hypergraph Properties for Constraint Satisfaction and Conjunctive Queries
Article No.: 42
An important question in the study of constraint satisfaction problems (CSP) is understanding how the graph or hypergraph describing the incidence structure of the constraints influences the complexity of the problem. For binary CSP instances...
On Ideal Lattices and Learning with Errors over Rings
Vadim Lyubashevsky, Chris Peikert, Oded Regev
Article No.: 43
The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems,...
From Low-Distortion Norm Embeddings to Explicit Uncertainty Relations and Efficient Information Locking
Omar Fawzi, Patrick Hayden, Pranab Sen
Article No.: 44
The existence of quantum uncertainty relations is the essential reason that some classically unrealizable cryptographic primitives become realizable when quantum communication is allowed. One operational manifestation of these uncertainty...
We prove that multilinear (tensor) analogues of many efficiently computable problems in numerical linear algebra are NP-hard. Our list includes: determining the feasibility of a system of bilinear equations, deciding whether a 3-tensor possesses a...