The Minimum Circuit Size Problem (MCSP) has been the focus of intense study recently; MCSP is hard for SZK under rather powerful reductions, and is provably not hard under "local" reductions computable in TIME(n^0.49) . The question of whether MCSP is NPhard (or indeed, hard even for small subclasses of P) under some of the more familiar notions of reducibility (such as manyone or Turing reductions computable in polynomial time or in AC^0) is closely related to many of the longstanding open questions in complexity theory. All prior hardness results for MCSP hold also for computing somewhat weak approximations to the circuit complexity of a function. Some of these results were proved by exploiting a connection to a notion of timebounded Kolmogorov complexity (KT) and the corresponding decision problem (MKTP). More recently, a new approach for proving improved hardness results for MKTP was developed, but this approach establishes only hardness of extremely good approximations of the form 1+o(1), and these improved hardness results are not yet known to hold for MCSP. In particular, it is known that MKTP is hard for the complexity class DET under nonuniform AC^0 mreductions, implying MKTP is not in AC^0[p] for any prime p. Itmore »
Interval universal approximation for neural networks
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 more »
 Award ID(s):
 1652140
 Publication Date:
 NSFPAR ID:
 10328257
 Journal Name:
 Proceedings of the ACM on Programming Languages
 Volume:
 6
 Issue:
 POPL
 Page Range or eLocationID:
 1 to 29
 ISSN:
 24751421
 Sponsoring Org:
 National Science Foundation
More Like this


With the advent of Network Function Virtualization (NFV), Physical Network Functions (PNFs) are gradually being replaced by Virtual Network Functions (VNFs) that are hosted on general purpose servers. Depending on the call flows for specific services, the packets need to pass through an ordered set of network functions (physical or virtual) called Service Function Chains (SFC) before reaching the destination. Conceivably for the next few years during this transition, these networks would have a mix of PNFs and VNFs, which brings an interesting mix of network problems that are studied in this paper: (1) How to find an SFCconstrained shortest path between any pair of nodes? (2) What is the achievable SFCconstrained maximum flow? (3) How to place the VNFs such that the cost (the number of nodes to be virtualized) is minimized, while the maximum flow of the original network can still be achieved even under the SFC constraint? In this work, we will try to address such emerging questions. First, for the SFCconstrained shortest path problem, we propose a transformation of the network graph to minimize the computational complexity of subsequent applications of any shortest path algorithm. Second, we formulate the SFCconstrained maximum flow problem as a fractionalmore »

A robustness certificate is the minimum distance of a given input to the decision boundary of the classifier (or its lower bound). For {\it any} input perturbations with a magnitude smaller than the certificate value, the classification output will provably remain unchanged. Exactly computing the robustness certificates for neural networks is difficult since it requires solving a nonconvex optimization. In this paper, we provide computationallyefficient robustness certificates for neural networks with differentiable activation functions in two steps. First, we show that if the eigenvalues of the Hessian of the network are bounded, we can compute a robustness certificate in the l2 norm efficiently using convex optimization. Second, we derive a computationallyefficient differentiable upper bound on the curvature of a deep network. We also use the curvature bound as a regularization term during the training of the network to boost its certified robustness. Putting these results together leads to our proposed {\bf C}urvaturebased {\bf R}obustness {\bf C}ertificate (CRC) and {\bf C}urvaturebased {\bf R}obust {\bf T}raining (CRT). Our numerical results show that CRT leads to significantly higher certified robust accuracy compared to intervalbound propagation (IBP) based training. We achieve certified robust accuracy 69.79\%, 57.78\% and 53.19\% while IBPbased methods achieve 44.96\%, 44.74\%more »

A new network with superapproximation power is introduced. This network is built with Floor (⌊x⌋) or ReLU (max{0,x}) activation function in each neuron; hence, we call such networks FloorReLU networks. For any hyperparameters N∈N+ and L∈N+, we show that FloorReLU networks with width max{d,5N+13} and depth 64dL+3 can uniformly approximate a Hölder function f on [0,1]d with an approximation error 3λdα/2NαL, where α∈(0,1] and λ are the Hölder order and constant, respectively. More generally for an arbitrary continuous function f on [0,1]d with a modulus of continuity ωf(·), the constructive approximation rate is ωf(dNL)+2ωf(d)NL. As a consequence, this new class of networks overcomes the curse of dimensionality in approximation power when the variation of ωf(r) as r→0 is moderate (e.g., ωf(r)≲rα for Hölder continuous functions), since the major term to be considered in our approximation rate is essentially d times a function of N and L independent of d within the modulus of continuity.

Bojanczy, Mikolaj ; Chekuri, Chandra (Ed.)Oneway functions (OWFs) are central objects of study in cryptography and computational complexity theory. In a seminal work, Liu and Pass (FOCS 2020) proved that the averagecase hardness of computing timebounded Kolmogorov complexity is equivalent to the existence of OWFs. It remained an open problem to establish such an equivalence for the averagecase hardness of some natural NPcomplete problem. In this paper, we make progress on this question by studying a conditional variant of the Minimum KTcomplexity Problem (MKTP), which we call McKTP, as follows. 1) First, we prove that if McKTP is averagecase hard on a polynomial fraction of its instances, then there exist OWFs. 2) Then, we observe that McKTP is NPcomplete under polynomialtime randomized reductions. 3) Finally, we prove that the existence of OWFs implies the nontrivial averagecase hardness of McKTP. Thus the existence of OWFs is inextricably linked to the averagecase hardness of this NPcomplete problem. In fact, building on recentlyannounced results of Ren and Santhanam [Rahul Ilango et al., 2021], we show that McKTP is hardonaverage if and only if there are logspacecomputable OWFs.