Randomness buys depth for approximate counting (Q483707): Difference between revisions

@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1007/s00037-013-0076-6
+Normal rank
@@ Property / OpenAlex ID @@
+W2046927500
@@ Property / OpenAlex ID: W2046927500 / rank @@
+Normal rank
@@ Property / cites work @@
+BQP and the polynomial hierarchy
@@ Property / cites work: BQP and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Q4474207
@@ Property / cites work: Q4474207 / rank @@
+Normal rank
@@ Property / cites work @@
+\(\Sigma_ 1^ 1\)-formulae on finite structures
@@ Property / cites work: \(\Sigma_ 1^ 1\)-formulae on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+Q4287354
@@ Property / cites work: Q4287354 / rank @@
+Normal rank
@@ Property / cites work @@
+Derandomized graph products
@@ Property / cites work: Derandomized graph products / rank @@
+Normal rank
@@ Property / cites work @@
+Bounds on the Size of Small Depth Circuits for Approximating Majority
+Normal rank
@@ Property / cites work @@
+On approximate majority and probabilistic time
@@ Property / cites work: On approximate majority and probabilistic time / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228451
@@ Property / cites work: Q4228451 / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient approximation of product distributions
@@ Property / cites work: Efficient approximation of product distributions / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of promise problems with applications to public-key cryptography
+Normal rank
@@ Property / cites work @@
+Q3585016
@@ Property / cites work: Q3585016 / rank @@
+Normal rank
@@ Property / cites work @@
+Pseudorandomness for network algorithms
@@ Property / cites work: Pseudorandomness for network algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Q4526985
@@ Property / cites work: Q4526985 / rank @@
+Normal rank
@@ Property / cites work @@
+Eigenvalues and expansion of regular graphs
@@ Property / cites work: Eigenvalues and expansion of regular graphs / rank @@
+Normal rank
@@ Property / cites work @@
+BPP and the polynomial hierarchy
@@ Property / cites work: BPP and the polynomial hierarchy / rank @@
+Normal rank
@@ Property / cites work @@
+Improved pseudorandom generators for combinatorial rectangles
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators for space-bounded computation
+Normal rank
@@ Property / cites work @@
+Randomness is linear in space
@@ Property / cites work: Randomness is linear in space / rank @@
+Normal rank
@@ Property / cites work @@
+Linear-size constant-depth polylog-threshold circuits
+Normal rank
@@ Property / cites work @@
+Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
+Normal rank
@@ Property / cites work @@
+Hardness Amplification Proofs Require Majority
@@ Property / cites work: Hardness Amplification Proofs Require Majority / rank @@
+Normal rank
@@ Property / cites work @@
+The complexity of constructing pseudorandom generators from hard functions
+Normal rank
@@ Property / cites work @@
+On Approximation Algorithms for # P
@@ Property / cites work: On Approximation Algorithms for # P / rank @@
+Normal rank