enter search term and/or author name
Graph Isomorphism is Not AC0-Reducible to Group Isomorphism
Arkadev Chattopadhyay, Jacobo Torán, Fabian Wagner
Article No.: 13
We give a new upper bound for the Group and Quasigroup Isomorphism problems when the input structures are given explicitly by multiplication tables. We show that these problems can be computed by polynomial size nondeterministic circuits of...
Explicit Optimal Hardness via Gaussian Stability Results
Anindya De, Elchanan Mossel
Article No.: 14
The results of Raghavendra  show that assuming Khot’s Unique Games Conjecture , for every constraint satisfaction problem there exists a generic semidefinite program that achieves the optimal approximation factor. This result is...
Robust Satisfiability for CSPs: Hardness and Algorithmic Results
Víctor Dalmau, Andrei Krokhin
Article No.: 15
An algorithm for a constraint satisfaction problem is called robust if it outputs an assignment satisfying at least a (1 − f(ε))-fraction of constraints for each (1 − ε)-satisfiable instance (i.e., such...
We study low-distortion embedding of metric spaces into the line, and more generally, into the shortest path metric of trees, from the parameterized complexity perspective. Let M = M(G) be the shortest path metric of an...
We highlight the challenge of proving correlation bounds between boolean functions and real-valued polynomials, where any non-boolean output counts against correlation.
We prove that real-valued polynomials of degree 1 2 lg2...
Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds
Ryan C. Harkins, John M. Hitchcock
Article No.: 18
This article extends and improves the work of Fortnow and Klivans , who showed that if a circuit class C has an efficient learning algorithm in Angluin’s model of exact learning via equivalence and membership queries [Angluin 1988],...