scientific article; zbMATH DE number 7561759

DOI10.4230/LIPICS.CCC.2020.31MaRDI QIDQ5092482zbMATH OpenFDO

Authors Rahul Ilango

Publication date 21 July 2022

Full work available at URL https://doi.org/10.4230/LIPICS.CCC.2020.31

zbMATH Keywords

gate eliminationminimum circuit size problemminimum formula size problemsearch to decision reductionself-reducibility

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25)

Recommendations

• Formal Reductions of the General Combinatorial Decision Problem
• On approximability of Boolean formula minimization
• Applications of minimal unsatisfiable formulas to polynomially reduction for formulas
• Lower Bounds on Minimal Weight of Partial Reducts and Partial Decision Rules
• On minimizing the \(\forall\)-\(\neg\) degree of a connective-free formula
• A tentative approach to minimal reducts by combining several algorithms
• Search-to-decision reductions for lattice problems with approximation factors (slightly) greater than one
• scientific article; zbMATH DE number 4037840
• The complexity of Boolean formula minimization
• The Complexity of Boolean Formula Minimization

Cites work

• \(\mathrm{AC}^0[p]\) lower bounds against MCSP via the coin problem
• A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms
• Circuit minimization problem
• Discrete logarithm and minimum circuit size
• Generating random binary trees -- a survey
• scientific article; zbMATH DE number 5529977 (Why is no real title available?)
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• scientific article; zbMATH DE number 7650416 (Why is no real title available?)
• Information theory and the complexity of boolean functions
• Learning algorithms from natural proofs
• Natural proofs
• On the (non) \(\mathsf{NP}\)-hardness of computing circuit complexity
• Power from Random Strings
• The complexity of Boolean formula minimization
• The new complexity landscape around circuit minimization
• The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory
• Zero knowledge and circuit minimization

Cited in

(3)

• Constant depth formula and partial function versions of MCSP are hard
• Exact search-to-decision reductions for time-bounded Kolmogorov complexity
• An efficient coding theorem via probabilistic representations and its applications

This page was built for publication:

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092482)