Circuit principles and weak pigeonhole variants

DOI10.1016/J.TCS.2007.04.017MaRDI QIDQ2383589zbMATH OpenOpenAlexFDO

Authors Norman Danner, Chris Pollett

Publication date 19 September 2007

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.tcs.2007.04.017

zbMATH Keywords

Bounded arithmeticcircuit lower boundscryptographypigeonhole principleRSA

Mathematics Subject Classification ID

Data encryption (aspects in computer science) (68P25)

Recommendations

• The weak pigeonhole principle for function classes inS12
• On the weak pigeonhole principle
• A model-theoretic characterization of the weak pigeonhole principle
• On Independence of Variants of the Weak Pigeonhole Principle
• Resolution lower bounds for the weak pigeonhole principle

Cites work

• A model-theoretic characterization of the weak pigeonhole principle
• A new proof of the weak pigeonhole principle
• An Application of Boolean Complexity to Separation Problems in Bounded Arithmetic
• Bounded arithmetic and the polynomial hierarchy
• Circuit-size lower bounds and non-reducibility to sparse sets
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• Herbrandizing search problems in Bounded Arithmetic
• How easy is local search?
• scientific article; zbMATH DE number 440485 (Why is no real title available?)
• scientific article; zbMATH DE number 4145897 (Why is no real title available?)
• scientific article; zbMATH DE number 3912375 (Why is no real title available?)
• scientific article; zbMATH DE number 4066875 (Why is no real title available?)
• scientific article; zbMATH DE number 65749 (Why is no real title available?)
• scientific article; zbMATH DE number 806753 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 227056 (Why is no real title available?)
• On truth-table reducibility to SAT
• Provability of the pigeonhole principle and the existence of infinitely many primes
• Quantified propositional calculi and fragments of bounded arithmetic
• Some consequences of cryptographical conjectures for \(S_2^1\) and EF
• Structure and definability in general bounded arithmetic theories
• The complexity of the pigeonhole principle
• The relative efficiency of propositional proof systems
• What are the \(\forall \Sigma_ 1^ b\)-consequences of \(T_ 2^ 1\) and \(T_ 2^ 2\)?

Cited in

(7)

• A model-theoretic characterization of the weak pigeonhole principle
• Dual weak pigeonhole principle, Boolean complexity, and derandomization
• The weak pigeonhole principle for function classes inS12
• Formulas versus Circuits for Small Distance Connectivity
• Alternation in simple devices
• On Independence of Variants of the Weak Pigeonhole Principle
• scientific article; zbMATH DE number 2247430 (Why is no real title available?)

This page was built for publication: Circuit principles and weak pigeonhole variants

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