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 35 items.
- Worst-Case to Average-Case Reductions for Subclasses of P (Q5098780) (← links)
- Constant-Round Interactive Proof Systems for AC0[2] and NC1 (Q5098783) (← links)
- (Q5101347) (← links)
- The Power of Programs over Monoids in DA (Q5111216) (← links)
- New insights on the (non-)hardness of circuit minimization and related problems (Q5111269) (← links)
- Degree lower bounds of tower-type for approximating formulas with parity quantifiers (Q5410333) (← links)
- Reed-Muller Codes (Q5870775) (← links)
- Hardness Characterisations and Size-width Lower Bounds for QBF Resolution (Q5886517) (← links)
- Natural proofs (Q5906823) (← links)
- On the degree of univariate polynomials over the integers (Q5916007) (← links)
- On the modulo degree complexity of Boolean functions (Q5918108) (← links)
- Fine-grained cryptography revisited (Q5918348) (← links)
- Circuit complexity of regular languages (Q5918477) (← links)
- New bounds for energy complexity of Boolean functions (Q5918995) (← links)
- An exact characterization of symmetric functions in \(qAC^{0}[2]\) (Q5941440) (← links)
- A lower bound for primality (Q5943093) (← links)
- On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 (Q6048002) (← links)
- (Q6062153) (← links)
- Propositional proof complexity (Q6064569) (← links)
- On the probabilistic degree of OR over the reals (Q6074648) (← links)
- (Q6084353) (← links)
- Is it possible to improve Yao's XOR lemma using reductions that exploit the efficiency of their oracle? (Q6113106) (← links)
- Fine-grained secure attribute-based encryption (Q6176273) (← links)
- The work of Mark Braverman (Q6200321) (← links)
- Communication and information complexity (Q6200329) (← links)
- Monomial Boolean functions with large high-order nonlinearities (Q6204170) (← links)
- Constructive separations and their consequences (Q6566463) (← links)
- A robust version of Hegedűs's lemma, with applications (Q6566590) (← links)
- Circuit complexity before the dawn of the new millennium (Q6567750) (← links)
- Fine-grained polynomial functional encryption (Q6593672) (← links)
- Parameterized complexity classes defined by threshold circuits and their connection with sorting networks (Q6610088) (← links)
- Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024 (Q6613418) (← links)
- Localizability of the approximation method (Q6624428) (← links)
- Fine-grained non-interactive key-exchange without idealized assumptions (Q6648207) (← links)
- Improved alternating-moduli PRFs and post-quantum signatures (Q6653030) (← links)
