Technical Reports


Display by Author:
A | B | C | D | E | F | G | H | I | J | K | L | M | N | O | P | Q | R | S | T | U | V | W | X | Y | Z
Search by for:

TR-426-93
A Uniform Circuit Lower Bound for the Permanent
Authors: Allender, Eric, Gore, Vivek
Date:June 1993
Pages:38
Download Formats: [Postscript]
Abstract:
We show that uniform families of ACC circuits of subexponential size cannot compute the permanent function. This also implies similar lower bounds for certain sets in PP. This is one of the very few examples of a lower bound in circuit complexity whose proof hinges on the uniformity condition; it is still unknown if there is any set in Ntime ($2^{n^{O(1)}}$) that does not have nonuniform ACC circuits.