Average-case lower bounds and satisfiability algorithms for small threshold circuits

DOI10.4230/LIPIcs.CCC.2016.1zbMath1380.68191arXiv1806.06290OpenAlexW2460503887MaRDI QIDQ5368735

Srikanth Srinivasan, Ruiwen Chen, Rahul Santhanam

Publication date: 10 October 2017

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

zbMATH Keywords

satisfiability algorithmthreshold circuitcircuit lower bound

Mathematics Subject Classification ID

Problem solving in the context of artificial intelligence (heuristics, search strategies, etc.) (68T20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Quantified Derandomization: How to Find Water in the Ocean ⋮ Unnamed Item ⋮ Gate elimination: circuit size lower bounds and \#SAT upper bounds ⋮ Unnamed Item ⋮ Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits

This page was built for publication: Average-case lower bounds and satisfiability algorithms for small threshold circuits