On uniformity and circuit lower bounds (Q488049): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / OpenAlex ID @@
+W2030202224
@@ Property / OpenAlex ID: W2030202224 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4267800
@@ Property / cites work: Q4267800 / rank @@
+Normal rank
@@ Property / cites work @@
+Amplifying lower bounds by means of self-reducibility
+Normal rank
@@ Property / cites work @@
+Computational Complexity
@@ Property / cites work: Computational Complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On uniformity within \(NC^ 1\)
@@ Property / cites work: On uniformity within \(NC^ 1\) / rank @@
+Normal rank
@@ Property / cites work @@
+Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding
+Normal rank
@@ Property / cites work @@
+Short PCPs with Projection Queries
@@ Property / cites work: Short PCPs with Projection Queries / rank @@
+Normal rank
@@ Property / cites work @@
+Parallel computation with threshold functions
@@ Property / cites work: Parallel computation with threshold functions / rank @@
+Normal rank
@@ Property / cites work @@
+Speedups of deterministic machines by synchronous parallel machines
+Normal rank
@@ Property / cites work @@
+Q4440439
@@ Property / cites work: Q4440439 / rank @@
+Normal rank
@@ Property / cites work @@
+On the Computational Complexity of Algorithms
@@ Property / cites work: On the Computational Complexity of Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+The Shrinkage Exponent of de Morgan Formulas is 2
@@ Property / cites work: The Shrinkage Exponent of de Morgan Formulas is 2 / rank @@
+Normal rank
@@ Property / cites work @@
+Two-Tape Simulation of Multitape Turing Machines
@@ Property / cites work: Two-Tape Simulation of Multitape Turing Machines / rank @@
+Normal rank
@@ Property / cites work @@
+In search of an easy witness: Exponential time vs. probabilistic polynomial time.
+Normal rank
@@ Property / cites work @@
+Randomness vs time: Derandomization under a uniform assumption
+Normal rank
@@ Property / cites work @@
+Local Reductions
@@ Property / cites work: Local Reductions / rank @@
+Normal rank
@@ Property / cites work @@
+Circuit-size lower bounds and non-reducibility to sparse sets
+Normal rank
@@ Property / cites work @@
+Short PCPPs verifiable in polylogarithmic time with \(O(1)\) queries
+Normal rank
@@ Property / cites work @@
+On uniform circuit complexity
@@ Property / cites work: On uniform circuit complexity / rank @@
+Normal rank
@@ Property / cites work @@
+On uniformity and circuit lower bounds
@@ Property / cites work: On uniformity and circuit lower bounds / rank @@
+Normal rank
@@ Property / cites work @@
+Extractors and pseudorandom generators
@@ Property / cites work: Extractors and pseudorandom generators / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of constructing pseudorandom generators from hard functions
+Normal rank
@@ Property / cites work @@
+Improving exhaustive search implies superpolynomial lower bounds
+Normal rank