Journal of the ACM (JACM)


Search Issue
enter search term and/or author name


Journal of the ACM (JACM), Volume 63 Issue 6, February 2017

Section: Computational Geometry

A Nearly Optimal Algorithm for Deciding Connectivity Queries in Smooth and Bounded Real Algebraic Sets
Mohab Safey El Din, Éric Schost
Article No.: 48
DOI: 10.1145/2996450

A roadmap for a semi-algebraic set S is a curve which has a non-empty and connected intersection with all connected components of S. Hence, this kind of object, introduced by Canny, can be used to answer connectivity queries (with...

Section: Computational Geometry

Belief Propagation Guided Decimation Fails on Random Formulas
Amin Coja-Oghlan
Article No.: 49
DOI: 10.1145/3005398

Let Φ be a uniformly distributed random k-SAT formula with n variables and m clauses. Nonconstructive arguments show that Φ is satisfiable for clause/variable ratios m/nrk...

Section: Computational Geometry

The Power of Localization for Efficiently Learning Linear Separators with Noise
Pranjal Awasthi, Maria Florina Balcan, Philip M. Long
Article No.: 50
DOI: 10.1145/3006384

We introduce a new approach for designing computationally efficient learning algorithms that are tolerant to noise, and we demonstrate its effectiveness by designing algorithms with improved noise tolerance guarantees for learning linear...

Section: Computational Geometry

Homotopy-Initial Algebras in Type Theory
Steve Awodey, Nicola Gambino, Kristina Sojakova
Article No.: 51
DOI: 10.1145/3006383

We investigate inductive types in type theory, using the insights provided by homotopy type theory and univalent foundations of mathematics. We do so by introducing the new notion of a homotopy-initial algebra. This notion is defined by a purely...

Section: Computational Geometry

Faster Polynomial Multiplication over Finite Fields
David Harvey, Joris Van Der Hoeven, Grégoire Lecerf
Article No.: 52
DOI: 10.1145/3005344

Polynomials over finite fields play a central role in algorithms for cryptography, error correcting codes, and computer algebra. The complexity of multiplying such polynomials is still a major open problem. Let p be a prime, and let...

Section: Computational Geometry

Invited Article Foreword
Eva Tardos
Article No.: 53
DOI: 10.1145/3018099

Section: Computational Geometry

Low-Rank Approximation and Regression in Input Sparsity Time
Kenneth L. Clarkson, David P. Woodruff
Article No.: 54
DOI: 10.1145/3019134

We design a new distribution over m × n matrices S so that, for any fixed n × d matrix A of rank r, with probability at least 9/10, ∥SAx2 = (1 ±...