Circuit and decision tree complexity of some number theoretic problems

DOI10.1006/inco.2000.3017zbMath1007.68074OpenAlexW2058182228MaRDI QIDQ1854439

Anna Bernasconi, Carsten Damm, Igor E. Shparlinski

Publication date: 14 January 2003

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/ff2a6c96f869ce2991feaded89a83b00b41fa60c

Mathematics Subject Classification ID

Number-theoretic algorithms; complexity (11Y16) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

Subset sum ``cubes and the complexity of primality testing ⋮ Bounds on the Fourier coefficients of the weighted sum function ⋮ Exact learning of multitrees and almost-trees using path queries ⋮ Unnamed Item ⋮ Communication complexity of some number theoretic functions

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The average sensitivity of bounded-depth circuits
• Number theoretic methods in cryptography. Complexity lower bounds
• Exponential lower bounds for depth 3 arithmetic circuits in algebras of functions over finite fields.
• On polynomial approximation of the discrete logarithm and the Diffie-Hellman mapping.
• The average sensitivity of square-freeness
• Fourier analysis for probabilistic communication complexity
• Constant depth circuits, Fourier transform, and learnability
• Improved Upper and Lower Time Bounds for Parallel Random Access Machines without Simultaneous Writes
• Parity, circuits, and the polynomial-time hierarchy
• The least square-free number in an arithmetic progression.
• On the Average Sensitivity of Testing Square-Free Numbers
• Feasible Time-Optimal Algorithms for Boolean Functions on Exclusive-Write Parallel Random-Access Machines
• A lower bound for primality

This page was built for publication: Circuit and decision tree complexity of some number theoretic problems