The independence of the modulo p counting principles

DOI10.1145/195058.195207MaRDI QIDQ2817631zbMATH OpenOpenAlexFDO

Authors Miklós Ajtai

Publication date 1 September 2016

Published in Proceedings of the twenty-sixth annual ACM symposium on Theory of computing - STOC '94 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1145/195058.195207

Mathematics Subject Classification ID

Complexity of proofs (03F20) Representations of finite symmetric groups (20C30)

Recommendations

• scientific article; zbMATH DE number 1114015
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• An exponential lower bound to the size of bounded depth frege proofs of the pigeonhole principle
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• The complexity of the pigeonhole principle

Cited in

(10)

• Proof complexity in algebraic systems and bounded depth Frege systems with modular counting
• \(\text{Count}(q)\) does not imply \(\text{Count}(p)\)
• Polynomial-size Frege and resolution proofs of \(st\)-connectivity and Hex tautologies
• A reduction of proof complexity to computational complexity for 𝐴𝐶⁰[𝑝] Frege systems
• Towards NP-P via proof complexity and search
• Forcing in Finite Structures
• scientific article; zbMATH DE number 806742 (Why is no real title available?)
• Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs
• Subspace-invariant \(\mathrm{AC}^0\) formulas
• Uniformly generated submodules of permutation modules over fields of characteristic 0.

This page was built for publication: The independence of the modulo \(p\) counting principles

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