Algorithms and lower bounds for comparator circuits from shrinkage

DOI10.1007/s00453-022-01091-yarXiv2111.14974MaRDI QIDQ6107895

Bruno Pasqualotto Cavalar, Zhenjian Lu

Publication date: 28 June 2023

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2111.14974

zbMATH Keywords

pseudorandom generatorsaverage-case complexitysatisfiability algorithmscomparator circuits

Mathematics Subject Classification ID

Algorithms in computer science (68Wxx) Graph theory (05Cxx)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Boolean function complexity. Advances and frontiers.
• Sorting in \(c \log n\) parallel steps
• The complexity of circuit value and network stability
• Comparator circuits over finite bounded posets
• Mining circuit lower bound proofs for meta-algorithms
• The complexity of the comparator circuit value problem
• Improving Exhaustive Search Implies Superpolynomial Lower Bounds
• Improved Average-Case Lower Bounds for De Morgan Formula Size: Matching Worst-Case Lower Bound
• Nonuniform ACC Circuit Lower Bounds
• What Circuit Classes Can Be Learned with Non-Trivial Savings?
• Chernoff–Hoeffding Bounds for Applications with Limited Independence
• Circuit Lower Bounds for MCSP from Local Pseudorandom Generators
• Adventures in monotone complexity and TFNP
• Hardness magnification near state-of-the-art lower bounds
• Algorithms and lower bounds for de morgan formulas of low-communication leaf gates
• Sharp threshold results for computational complexity
• Pseudorandomness from Shrinkage
• Average-case lower bounds for formula size
• Lower Bounds for (Non-Monotone) Comparator Circuits

This page was built for publication: Algorithms and lower bounds for comparator circuits from shrinkage