A shortest cycle for each vertex of a graph

We present an algorithm that finds, for each vertex of an undirected graph, a shortest cycle containing it. While for directed graphs this problem reduces to the All-Pairs Shortest Paths problem, this is not known to be the case for undirected graphs.We present a truly sub-cubic randomized algorithm for the undirected case. Given an undirected graph with n vertices and integer weights in $1,\dots ,M$, it runs in $\stackrel{?}{O}(\sqrt{M}{n}^{(\omega +3)/2})$ time where $\omega <2.376$ is the exponent of matrix multiplication. As a by-product, our algorithm can be used to determine which vertices lie on cycles of length at most t in $\stackrel{?}{O}(M{n}^{\omega }t)$ time. For the case of bounded real edge weights, a variant of our algorithm solves the problem up to an additive error of ? in $\stackrel{?}{O}(n^{(\omega +6)/3})$ time.     

Cryptographic hardness for learning intersections of halfspaces

We give the first representation-independent hardness results for PAC learning intersections of halfspaces, a central concept class in computational learning theory. Our hardness results are derived from two public-key cryptosystems due to Regev, which are based on the worst-case hardness of well-studied lattice problems. Specifically, we prove that a polynomial-time algorithm for PAC learning intersections of $n^{\mathrm{?}}$ halfspaces (for a constant $\mathrm{?}>0$) in n dimensions would yield a polynomial-time solution to $\stackrel{?}{O}(n^{1.5})$-$\mathsf{uSVP}$ (unique shortest vector problem). We also prove that PAC learning intersections of $n^{\mathrm{?}}$ low-weight halfspaces would yield a polynomial-time quantum solution to $\stackrel{?}{O}(n^{1.5})$-$\mathsf{SVP}$ and $\stackrel{?}{O}(n^{1.5})$-$\mathsf{SIVP}$ (shortest vector problem and shortest independent vector problem, respectively). Our approach also yields the first representation-independent hardness results for learning polynomial-size depth-2 neural networks and polynomial-size depth-3 arithmetic circuits.     

On the applicability of Postʼs lattice

For decision problems $\Pi (B)$ defined over Boolean circuits using gates from a restricted set B only, we have $\Pi (B){?}_m^{{\mathrm{AC}}^0}\Pi (B^{\prime })$ for all finite sets B and $B^{\prime }$ of gates such that all gates from B can be computed by circuits over gates from $B^{\prime }$. In this note, we show that a weaker version of this statement holds for decision problems defined over Boolean formulae, namely that $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{\wedge ,\vee \})$ and $\Pi (B){?}_m^{{\mathrm{NC}}^2}\Pi (B^{\prime }\cup \{0,1\})$ for all finite sets B and $B^{\prime }$ of Boolean functions such that all $f\in B$ can be defined in $B^{\prime }$.