Pages that link to "Item:Q1095871"
From MaRDI portal
The following pages link to Lower bounds on the size of bounded depth circuits over a complete basis with logical addition (Q1095871):
Displaying 50 items.
- Collapsing modular counting in bounded arithmetic and constant depth propositional proofs (Q2944908) (← links)
- The Shifted Partial Derivative Complexity of Elementary Symmetric Polynomials (Q2946403) (← links)
- Constructive Relationships Between Algebraic Thickness and Normality (Q2947873) (← links)
- Learning Read-Constant Polynomials of Constant Degree Modulo Composites (Q3007614) (← links)
- NEXP Does Not Have Non-uniform Quasipolynomial-Size ACC Circuits of o(loglogn) Depth (Q3010398) (← links)
- Correlation Bounds for Poly-size $\mbox{\rm AC}^0$ Circuits with n 1 − o(1) Symmetric Gates (Q3088133) (← links)
- On systems of equations over free partially commutative groups (Q3091752) (← links)
- Asymptotic invariants, complexity of groups and related problems (Q3143713) (← links)
- Nonuniform ACC Circuit Lower Bounds (Q3189637) (← links)
- Skew Circuits of Small Width (Q3196384) (← links)
- Depth Reduction for Circuits with a Single Layer of Modular Counting Gates (Q3392947) (← links)
- Solution Sets for Equations over Free Groups are EDT0L Languages (Q3449471) (← links)
- Ehrenfeucht-Fraïssé Games on Random Structures (Q3638295) (← links)
- Immunity and Simplicity for Exact Counting and Other Counting Classes (Q4265536) (← links)
- Faster All-Pairs Shortest Paths via Circuit Complexity (Q4554074) (← links)
- Randomized feasible interpolation and monotone circuits with a local oracle (Q4562441) (← links)
- Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits (Q4568115) (← links)
- Characterizing Propositional Proofs as Noncommutative Formulas (Q4577770) (← links)
- (Q4612482) (← links)
- (Q4625701) (← links)
- (Q4625702) (← links)
- The Computational Power of Depth Five Arithmetic Circuits (Q4629389) (← links)
- On polynomial approximations to AC (Q4633319) (← links)
- Depth Reduction for Composites (Q4634033) (← links)
- A Hierarchy Theorem for Interactive Proofs of Proximity (Q4638092) (← links)
- On the correlation of symmetric functions (Q4717052) (← links)
- On the correlation of symmetric functions (Q4879208) (← links)
- On the Probabilistic Degrees of Symmetric Boolean Functions (Q4959660) (← links)
- Size, cost and capacity: a semantic technique for hard random QBFs (Q4993272) (← links)
- Agnostic Learning from Tolerant Natural Proofs (Q5002638) (← links)
- Small bias requires large formulas (Q5002692) (← links)
- (Q5005182) (← links)
- From Circuit Complexity to Faster All-Pairs Shortest Paths (Q5009891) (← links)
- Pseudorandom Functions: Three Decades Later (Q5021131) (← links)
- On small depth threshold circuits (Q5056127) (← links)
- Approximate Degree in Classical and Quantum Computing (Q5060675) (← links)
- Strong Average-Case Circuit Lower Bounds from Nontrivial Derandomization (Q5080481) (← links)
- (Q5090385) (← links)
- Expander-Based Cryptography Meets Natural Proofs (Q5090391) (← links)
- Pseudorandom Generators from the Second Fourier Level and Applications to AC0 with Parity Gates (Q5090395) (← links)
- (Q5090396) (← links)
- (Q5090936) (← links)
- (Q5091175) (← links)
- (Q5091223) (← links)
- Parity helps to compute majority (Q5091774) (← links)
- Bounded-Depth Frege Complexity of Tseitin Formulas for All Graphs (Q5092411) (← links)
- On the Symmetries of and Equivalence Test for Design Polynomials. (Q5092415) (← links)
- (Q5092470) (← links)
- Separating counting communication complexity classes (Q5096788) (← links)
- On the Size of Depth-Three Boolean Circuits for Computing Multilinear Functions (Q5098770) (← links)
