To verify safety and robustness of neural networks, researchers have successfully applied abstract interpretation , primarily using the interval abstract domain. In this paper, we study the theoretical power and limits of the interval domain for neuralnetwork verification. First, we introduce the interval universal approximation (IUA) theorem. IUA shows that neural networks not only can approximate any continuous function f (universal approximation) as we have known for decades, but we can find a neural network, using any wellbehaved activation function, whose interval bounds are an arbitrarily close approximation of the set semantics of f (the result of applying f to a set of inputs). We call this notion of approximation interval approximation . Our theorem generalizes the recent result of Baader et al. from ReLUs to a rich class of activation functions that we call squashable functions . Additionally, the IUA theorem implies that we can always construct provably robust neural networks under ℓ ∞ norm using almost any practical activation function. Second, we study the computational complexity of constructing neural networks that are amenable to precise interval analysis. This is a crucial question, as our constructive proof of IUA is exponential in the size of the approximation domain. We boil this question down to the problem of approximating the range of a neural network with squashable activation functions. We show that the range approximation problem (RA) is a Δ 2 intermediate problem, which is strictly harder than NP complete problems, assuming coNP ⊄ NP . As a result, IUA is an inherently hard problem : No matter what abstract domain or computational tools we consider to achieve interval approximation, there is no efficient construction of such a universal approximator. This implies that it is hard to construct a provably robust network, even if we have a robust network to start with.
more »
« less
On the Complexity of Moduloq Arguments and the Chevalley  Warning Theorem
We study the search problem class PPA_q defined as a moduloq analog of the wellknown polynomial parity argument class PPA introduced by Papadimitriou (JCSS 1994). Our first result shows that this class can be characterized in terms of PPA_p for prime p. Our main result is to establish that an explicit version of a search problem associated to the Chevalley  Warning theorem is complete for PPA_p for prime p. This problem is natural in that it does not explicitly involve circuits as part of the input. It is the first such complete problem for PPA_p when p ≥ 3. Finally we discuss connections between ChevalleyWarning theorem and the wellstudied short integer solution problem and survey the structural properties of PPA_q.
more »
« less
 Award ID(s):
 1741137
 NSFPAR ID:
 10220397
 Date Published:
 Journal Name:
 Computational Complexity Conference 2020
 Format(s):
 Medium: X
 Sponsoring Org:
 National Science Foundation
More Like this


Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in nonconvex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLScomplete. We thus provide the first natural complete problem for the class CLS, which was defined in [DP11] to capture the complexity of problems such as Pmatrix LCP, computing KKTpoints, and finding mixed Nash equilibria in congestion and network coordination games.more » « less

Banach's fixed point theorem for contraction maps has been widely used to analyze the convergence of iterative methods in nonconvex problems. It is a common experience, however, that iterative maps fail to be globally contracting under the natural metric in their domain, making the applicability of Banach's theorem limited. We explore how generally we can apply Banach's fixed point theorem to establish the convergence of iterative methods when pairing it with carefully designed metrics. Our first result is a strong converse of Banach's theorem, showing that it is a universal analysis tool for establishing global convergence of iterative methods to unique fixed points, and for bounding their convergence rate. In other words, we show that, whenever an iterative map globally converges to a unique fixed point, there exists a metric under which the iterative map is contracting and which can be used to bound the number of iterations until convergence. We illustrate our approach in the widely used power method, providing a new way of bounding its convergence rate through contraction arguments. We next consider the computational complexity of Banach's fixed point theorem. Making the proof of our converse theorem constructive, we show that computing a fixed point whose existence is guaranteed by Banach's fixed point theorem is CLScomplete. We thus provide the first natural complete problem for the class CLS, which was defined in [Daskalakis, Papadimitriou 2011] to capture the complexity of problems such as Pmatrix LCP, computing KKTpoints, and finding mixed Nash equilibria in congestion and network coordination games.more » « less

null (Ed.)Consider the following two fundamental open problems in complexity theory: • Does a hardonaverage language in NP imply the existence of oneway functions? • Does a hardonaverage language in NP imply a hardonaverage problem in TFNP (i.e., the class of total NP search problem)? Our main result is that the answer to (at least) one of these questions is yes. Both oneway functions and problems in TFNP can be interpreted as promisetrue distributional NP search problems—namely, distributional search problems where the sampler only samples true statements. As a direct corollary of the above result, we thus get that the existence of a hardonaverage distributional NP search problem implies a hardonaverage promisetrue distributional NP search problem. In other words, It is no easier to find witnesses (a.k.a. proofs) for efficientlysampled statements (theorems) that are guaranteed to be true. This result follows from a more general study of interactive puzzles—a generalization of averagecase hardness in NP—and in particular, a novel roundcollapse theorem for computationallysound protocols, analogous to BabaiMoran’s celebrated roundcollapse theorem for informationtheoretically sound protocols. As another consequence of this treatment, we show that the existence of O(1)round publiccoin nontrivial arguments (i.e., argument systems that are not proofs) imply the existence of a hardonaverage problem in NP/poly.more » « less

Kabanets, Valentine (Ed.)In this paper we study some classical complexitytheoretic questions regarding Group Isomorphism (GpI). We focus on pgroups (groups of prime power order) with odd p, which are believed to be a bottleneck case for GpI, and work in the model of matrix groups over finite fields. Our main results are as follows.  Although searchtodecision and countingtodecision reductions have been known for over four decades for Graph Isomorphism (GI), they had remained open for GpI, explicitly asked by Arvind & Torán (Bull. EATCS, 2005). Extending methods from Tensor Isomorphism (Grochow & Qiao, ITCS 2021), we show moderately exponentialtime such reductions within pgroups of class 2 and exponent p.  Despite the widely held belief that pgroups of class 2 and exponent p are the hardest cases of GpI, there was no reduction to these groups from any larger class of groups. Again using methods from Tensor Isomorphism (ibid.), we show the first such reduction, namely from isomorphism testing of pgroups of "small" class and exponent p to those of class two and exponent p. For the first results, our main innovation is to develop linearalgebraic analogues of classical graph coloring gadgets, a key technique in studying the structural complexity of GI. Unlike the graph coloring gadgets, which support restricting to various subgroups of the symmetric group, the problems we study require restricting to various subgroups of the general linear group, which entails significantly different and more complicated gadgets. The analysis of one of our gadgets relies on a classical result from group theory regarding random generation of classical groups (Kantor & Lubotzky, Geom. Dedicata, 1990). For the nilpotency class reduction, we combine a runtime analysis of the Lazard Correspondence with Tensor Isomorphismcompleteness results (Grochow & Qiao, ibid.).more » « less