Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

DOI10.1007/11672142_55MaRDI QIDQ5449840zbMATH OpenOpenAlexFDO

Authors Alexander D. Healy, Emanuele Viola

Publication date 19 March 2008

Published in STACS 2006 (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/11672142_55

Mathematics Subject Classification ID

Polynomials over finite fields (11T06) Number-theoretic algorithms; complexity (11Y16) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On complexity and depth of Boolean circuits for multiplication and inversion over finite fields of characteristic 2
• Depth-3 arithmetic circuits over fields of characteristic zero
• scientific article; zbMATH DE number 5504474
• On the depth of logic circuits for operations in the fields \(\text{GF}(2^n)\)
• Mathematical Foundations of Computer Science 2003
• On finite field arithmetic in characteristic 2
• A new representation of elements of finite fields GF(2/sup m/) yielding small complexity arithmetic circuits
• On design of circuits of logarithmic depth for inversion in finite fields
• Publication:4893147

Cited in

(18)

• Perfect secure computation in two rounds
• Local expanders
• Dynamic complexity of expansion
• Efficient sample extractors for juntas with applications
• Circuit complexity of powering in fields of odd characteristic
• Some results on uniform arithmetic circuit complexity
• On "A new representation of elements of finite fields GF(2/sup m/) yielding small complexity arithmetic circuits"
• Quantum hardness of learning shallow classical circuits
• Worst-Case to Average-Case Reductions for Subclasses of P
• Perfect secure computation in two rounds
• On the complexity of powering in finite fields
• On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
• SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption
• Dynamic complexity of reachability: how many changes can we handle?
• Randomness extractors in AC^0 and NC^1: optimal up to constant factors
• Nondeterministic quasi-polynomial time is average-case hard for \textsf{ACC} circuits
• Feasibility of primality in bounded arithmetic
• Polynomial-time pseudodeterministic construction of primes

This page was built for publication: Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two

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