Formulas versus Circuits for Small Distance Connectivity (Q4554075): Difference between revisions

@@ Property / cites work @@
+First-order definability on finite structures
@@ Property / cites work: First-order definability on finite structures / rank @@
+Normal rank
@@ Property / cites work @@
+Improved depth lower bounds for small distance connectivity
+Normal rank
@@ Property / cites work @@
+Approximation and Small-Depth Frege Proofs
@@ Property / cites work: Approximation and Small-Depth Frege Proofs / rank @@
+Normal rank
@@ Property / cites work @@
+Near-optimal small-depth lower bounds for small distance connectivity
+Normal rank
@@ Property / cites work @@
+Tight Lower Bounds for <i>st</i>-Connectivity on the NNJAG Model
+Normal rank
@@ Property / cites work @@
+Parity, circuits, and the polynomial-time hierarchy
+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 @@
+Poisson approximation for large deviations
@@ Property / cites work: Poisson approximation for large deviations / rank @@
+Normal rank
@@ Property / cites work @@
+Boolean function complexity. Advances and frontiers.
+Normal rank
@@ Property / cites work @@
+Monotone Circuits for Connectivity Require Super-Logarithmic Depth
+Normal rank
@@ Property / cites work @@
+On the Power of Homogeneous Depth 4 Arithmetic Circuits
+Normal rank
@@ Property / cites work @@
+Lower bounds on arithmetic circuits via partial derivatives
+Normal rank
@@ Property / cites work @@
+Undirected connectivity in log-space
@@ Property / cites work: Undirected connectivity in log-space / rank @@
+Normal rank
@@ Property / cites work @@
+Q5302097
@@ Property / cites work: Q5302097 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4601839
@@ Property / cites work: Q4601839 / rank @@
+Normal rank
@@ Property / cites work @@
+The average sensitivity of bounded-depth formulas
@@ Property / cites work: The average sensitivity of bounded-depth formulas / rank @@
+Normal rank
@@ Property / cites work @@
+The number of Boolean functions computed by formulas of a given size
+Normal rank
@@ Property / cites work @@
+Relationships between nondeterministic and deterministic tape complexities
+Normal rank
@@ Property / cites work @@
+On the depth complexity of formulas
@@ Property / cites work: On the depth complexity of formulas / rank @@
+Normal rank
@@ Property / cites work @@
+A direct version of Shamir and Snir's lower bounds on monotone circuit depth
+Normal rank
@@ Property / cites work @@
+The complexity of graph connectivity
@@ Property / cites work: The complexity of graph connectivity / rank @@
+Normal rank
@@ Property / full work available at URL @@
+https://doi.org/10.1137/15m1027310
+Normal rank
@@ Property / OpenAlex ID @@
+W2898993321
@@ Property / OpenAlex ID: W2898993321 / rank @@
+Normal rank