Algorithms and lower bounds for de morgan formulas of low-communication leaf gates

DOI10.4230/LIPIcs.CCC.2020.15zbMath1495.68065OpenAlexW3013497680MaRDI QIDQ5092464

Sajin Koroth, Igor C. Oliveira, Zhenjian Lu, Valentine Kabanets, Dimitrios Myrisiotis

Publication date: 21 July 2022

Full work available at URL: https://doi.org/10.4230/LIPIcs.CCC.2020.15

zbMATH Keywords

learningcommunication complexityDe Morgan formulasparitiescircuit lower boundssatisfiability (SAT)pseudorandom generators (PRGs)polynomial threshold functions (PTFs)

Mathematics Subject Classification ID

Randomized algorithms (68W20) Networks and circuits as models of computation; circuit complexity (68Q06) Communication complexity, information complexity (68Q11)

Related Items (4)

MPC-friendly symmetric cryptography from alternating moduli: candidates, protocols, and applications ⋮ Approximate Degree in Classical and Quantum Computing ⋮ Fooling Polytopes ⋮ Algorithms and lower bounds for comparator circuits from shrinkage

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The communication complexity of addition
• Boolean function complexity. Advances and frontiers.
• A method for obtaining more than quadratic effective lower estimates of complexity of \(\pi\) schemes
• Multiparty protocols, pseudorandom generators for Logspace, and time- space trade-offs
• Toward the KRW composition conjecture: cubic formula lower bounds via communication complexity
• Exploring crypto dark matter: new simple PRF candidates and their applications
• The landscape of communication complexity classes
• Upper bounds for the size and the depth of formulae for MOD-functions
• Graph complexity
• Mining circuit lower bound proofs for meta-algorithms
• The quantum adversary method and classical formula size power bounds
• Theory of majority decision elements
• Method of determining lower bounds for the complexity of \(\Pi\)-circuits
• Robust polynomials and quantum algorithms
• Pseudorandomness for network algorithms
• Pseudorandomness
• Span-program-based quantum algorithm for evaluating formulas
• Any AND-OR Formula of Size N Can Be Evaluated in Time $N^{1/2+o(1)}$ on a Quantum Computer
• Nonuniform ACC Circuit Lower Bounds
• Agnostically Learning Halfspaces
• Rapid Multiplication of Rectangular Matrices
• Simple Constructions of Almost k-wise Independent Random Variables
• The Shrinkage Exponent of de Morgan Formulas is 2
• Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits
• On polynomial approximations to AC
• What Circuit Classes Can Be Learned with Non-Trivial Savings?
• The effect of random restrictions on formula size
• Shrinkage of de Morgan formulae under restriction
• Communication Complexity
• Formula lower bounds via the quantum method
• Hardness magnification near state-of-the-art lower bounds
• Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function
• Fooling polytopes
• Pseudorandomness from Shrinkage
• Quantum lower bounds by polynomials

This page was built for publication: Algorithms and lower bounds for de morgan formulas of low-communication leaf gates