NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth (Q3010398): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1007/978-3-642-20877-5_17
+Normal rank
@@ Property / OpenAlex ID @@
+W1535289693
@@ Property / OpenAlex ID: W1535289693 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4267800
@@ Property / cites work: Q4267800 / rank @@
+Normal rank
@@ Property / cites work @@
+A Uniform Circuit Lower Bound for the Permanent
@@ Property / cites work: A Uniform Circuit Lower Bound for the Permanent / rank @@
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+Optimal bounds for decision problems on the CRCW PRAM
+Normal rank
@@ Property / cites work @@
+When do extra majority gates help? Polylog\((N)\) majority gates are equivalent to one
+Normal rank
@@ Property / cites work @@
+On ACC
@@ Property / cites work: On ACC / rank @@
+Normal rank
@@ Property / cites work @@
+Q4246733
@@ Property / cites work: Q4246733 / rank @@
+Normal rank
@@ Property / cites work @@
+Robust simulations and significant separations
@@ Property / cites work: Robust simulations and significant separations / rank @@
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
+Normal rank
@@ Property / cites work @@
+Q4393484
@@ Property / cites work: Q4393484 / rank @@
+Normal rank
@@ Property / cites work @@
+Improving exhaustive search implies superpolynomial lower bounds
+Normal rank
@@ Property / cites work @@
+A Turing machine time hierarchy
@@ Property / cites work: A Turing machine time hierarchy / rank @@
+Normal rank