Lower Bounds Against Weakly-Uniform Threshold Circuits

• Published in: Algorithmica 2014-09, Vol.70 (1), p.47-75
• Main Authors: Chen, Ruiwen, Kabanets, Valentine, Kinne, Jeff
• Format: Article
• Language: English
• Subjects: Algorithm Analysis and Problem Complexity; Algorithmics. Computability. Computer arithmetics; Algorithms; Applied sciences; Automata. Abstract machines. Turing machines; Computer Science; Computer science; control theory; systems; Computer Systems Organization and Communication Networks; Data Structures and Information Theory; Exact sciences and technology; Information retrieval. Graph; Mathematics of Computing; Theoretical computing; Theory of Computation
• ISSN: 0178-4617; 1432-0541
• DOI: 10.1007/s00453-013-9823-y

An ongoing line of research has shown super-polynomial lower bounds for uniform and slightly-non-uniform small-depth threshold and arithmetic circuits (Allender, in Chicago J. Theor. Comput. Sci. 1999(7), 1999 ; Koiran and Perifel, in Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC 2009), pp. 35–40, 2009 ; Jansen and Santhanam, in Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), I, pp. 724–735, 2011 ). We give a unified framework that captures and improves each of the previous results. Our main results are that Permanent does not have threshold circuits of the following kinds. Depth O (1), n o (1) bits of non-uniformity, and size n O (1) . Depth O (1), polylog( n ) bits of non-uniformity, and size s ( n ) such that for all constants c the c -fold composition of s , s ( c ) ( n ), is less than 2 n . Depth o (loglog n ), polylog( n ) bits of non-uniformity, and size n O (1) . (1) strengthens a result of Jansen and Santhanam (Jansen and Santhanam, in Proceedings of the 38th International Colloquium on Automata, Languages and Programming (ICALP 2011), I, pp. 724–735, 2011 ), who obtained similar parameters but for arithmetic circuits of constant depth rather than Boolean threshold circuits. (2) and (3) strengthen results of Allender (Allender, in Chicago J. Theor. Comput. Sci. 1999(7), 1999 ) and Koiran and Perifel (Koiran and Perifel, in Proceedings of the 24th Annual IEEE Conference on Computational Complexity (CCC 2009), pp. 35–40, 2009 ), respectively, who obtained results with similar parameters but for completely uniform circuits. Our main technical contribution is to simplify and unify earlier proofs in this area, and adapt the proofs to handle some amount of non-uniformity. We also develop a notion of circuits with a small amount of non-uniformity that naturally interpolates between fully uniform and fully non-uniform circuits. We use this notion, which we term weak uniformity , rather than the earlier and essentially equivalent notion of succinctness used by Jansen and Santhanam because the notion of weak uniformity more fully and easily interpolates between full uniformity and non-uniformity of circuits.