Search ACM DL

Search Issue

enter search term and/or author name

Section:

**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*/*n* ⩽ *r*_{k−...
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, ∥*SAx*∥_{2} = (1 ±...