ON THE CIRCUIT-SIZE OF INVERSES

DOI10.1142/S0129054111009124zbMath1234.68128OpenAlexW2963467514MaRDI QIDQ3224957

Jean-Camille Birget

Publication date: 13 March 2012

Published in: International Journal of Foundations of Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1142/s0129054111009124

zbMATH Keywords

computational complexityone-way functionscircuit size

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Semigroups and one-way functions

Cites Work

• Unnamed Item
• Tight lower bounds on the ambiguity of strong, total, associative, one-way functions
• Enforcing and defying associativity, commutativity, totality, and strong noninvertibility for worst-case one-way functions
• One way functions and pseudorandom generators
• Creating strong, total, commutative, associative one-way functions from any one-way function in complexity theory
• Inverting onto functions.
• Characterizing the existence of one-way permutations
• On characterizing the existence of partial one-way permutations
• One-way permutations and self-witnessing languages
• Does the polynomial hierarchy collapse if onto functions are invertible?
• If P \(\neq\) NP then some strongly noninvertible functions are invertible
• THE ${\mathcal R}$- AND ${\mathcal L}$-ORDERS OF THE THOMPSON–HIGMAN MONOID M_{k, 1} AND THEIR COMPLEXITY
• Complexity Measures for Public-Key Cryptosystems
• Foundations of Cryptography
• On Regular Rings

This page was built for publication: ON THE CIRCUIT-SIZE OF INVERSES