Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 60 Issue 6, November 2013

Tensor-Rank and Lower Bounds for Arithmetic Formulas
Ran Raz
Article No.: 40
DOI: 10.1145/2535928

We show that any explicit example for a tensor A : [n]rF 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
DOI: 10.1145/2535927

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
Dániel Marx
Article No.: 42
DOI: 10.1145/2535926

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
DOI: 10.1145/2535925

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
DOI: 10.1145/2518131

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...

Most Tensor Problems Are NP-Hard
Christopher J. Hillar, Lek-Heng Lim
Article No.: 45
DOI: 10.1145/2512329

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...