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. Wemore »
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.
 Award ID(s):
 1741137
 Publication Date:
 NSFPAR ID:
 10220397
 Journal Name:
 Computational Complexity Conference 2020
 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 existencemore »

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 existencemore »

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 ofmore »

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 ofmore »