A Note on the Complexity of Comparing Succinctly Represented Integers, with an Application to Maximum Probability Parsing

DOI10.1145/2601327zbMath1321.68309arXiv1304.5429OpenAlexW2168359059MaRDI QIDQ2943574

Kousha Etessami, Mihalis Yannakakis, Alistair Stewart

Publication date: 3 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1304.5429

zbMATH Keywords

logarithmic formsarithmetic circuitsstochastic context-free grammarsABC conjectureprobabilistic parsingLang-Waldschmidt conjecturesuccinct representation of numbers

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Number-theoretic algorithms; complexity (11Y16) Grammars and rewriting systems (68Q42)

Related Items

On the Order of Power Series and the Sum of Square Roots Problem, Root separation for trinomials

Cites Work

• A generalization of Dijkstra's algorithm
• An explicit lower bound for a homogeneous rational linear form in the logarithms of algebraic numbers. II
• Logarithmic forms and group varieties.
• Factor Refinement
• On the Complexity of Numerical Analysis
• Biological Sequence Analysis
• Factoring into coprimes in essentially linear time
• Minorations de Combinaisons Linéaires de Logarithmes de Nombres Algébriques
• Polynomial time algorithms for multi-type branching processesand stochastic context-free grammars
• Derandomizing polynomial identity tests means proving circuit lower bounds
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item