On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
From MaRDI portal
Publication:6048002
DOI10.3233/com-220407OpenAlexW4324138261MaRDI QIDQ6048002
Samir Datta, Rameshwar Pratap, Eric W. Allender, Nikhil Balaji
Publication date: 13 September 2023
Published in: Computability (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.3233/com-220407
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Interpolation in Valiant's theory
- Root finding with threshold circuits
- Powering requires threshold depth 3
- Computing partial information out of intractable: powers of algebraic numbers as an example
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- One-way functions and circuit complexity
- Computational complexity of real functions
- Regular languages in \(NC\)
- A problem that is easier to solve on the unit-cost algebraic RAM
- Threshold circuits of small majority-depth
- Nondeterministic \(NC^1\) computation
- Bits and relative order from residues, space efficiently
- On \(\text{TC}^0,\text{AC}^0\), and arithmetic circuits
- Transcendental numbers. With a foreword by W. Dale Brownawell. Transl. from the Russian by Neal Koblitz
- Optimal lower bounds on the depth of polynomial-size threshold circuits for some arithmetic functions
- Uniform constant-depth threshold circuits for division and iterated multiplication.
- On the complexity of algebraic numbers
- The Kolmogorov complexity of random reals
- On logarithmic-space computable real numbers
- The irrationality measure of \(\pi\) is at most 7.103205334137\dots
- The complexity of two problems on arithmetic circuits
- A note on some languages in uniform \(ACC^ 0\)
- On the complexity of algebraic numbers. I: Expansions in integer bases
- People, Problems, and Proofs
- Hartmanis-Stearns Conjecture on Real Time and Transcendence
- Computing Bits of Algebraic Numbers
- Low-Depth Uniform Threshold Circuits and the Bit-Complexity of Straight Line Programs
- On the Sum of Square Roots of Polynomials and Related Problems
- On the Complexity of Nash Equilibria and Other Fixed Points
- On the rapid computation of various polylogarithmic constants
- On the definitions of some complexity classes of real numbers
- PP is as Hard as the Polynomial-Time Hierarchy
- On the Complexity of Numerical Analysis
- Log Depth Circuits for Division and Related Problems
- On Threshold Circuits and Polynomial Computation
- On Optimal Depth Threshold Circuits for Multiplication and Related Problems
- Simulating Threshold Circuits by Majority Circuits
- Automatic Sequences
- Threshold Circuits for Iterated Matrix Product and Powering
- On the Complexity of Linear Arithmetic with Divisibility
- On the computational complexity of algebraic numbers: the Hartmanis–Stearns problem revisited
- Handbook of Computability and Complexity in Analysis
- Circuit Lower Bounds for Nondeterministic Quasi-polytime from a New Easy Witness Lemma
- On the Positivity Problem for Simple Linear Recurrence Sequences,
- Every 2-random real is Kolmogorov random
- Computational Complexity
- On the Computational Complexity of Algorithms
- Positivity Problems for Low-Order Linear Recurrence Sequences
- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two
- The orbit problem in higher dimensions
- Randomness, relativization and Turing degrees
- On Computable Numbers, with an Application to the Entscheidungsproblem
- Rational approximations to algebraic numbers
- A lower bound for primality
This page was built for publication: On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1
