Generative Adversarial Symmetry Discovery
Jianke Yang, Robin Walters, et al.
ICML 2023
Consider an arithmetic expression of lengthninvolving only the operations {+,×} and non-negative constants. We prove lower bounds on the depth of any binary computation tree over the same sets of operations and constants that computes such an expression. We exhibit a family of arithmetic expressions that requires computation trees of depth at least 1.5log2n-O(1), thus proving a conjecture of S. R. Kosaraju (1986,in"Proc. of the 18th ACM Symp. on Theory Computing," pp. 231-239). In contrast, Kosaraju showed how to compute such expressions with computation trees of depth 2log2n+O(1). © 1999 Academic Press.
Jianke Yang, Robin Walters, et al.
ICML 2023
Guo-Jun Qi, Charu Aggarwal, et al.
IEEE TPAMI
James Lee Hafner
Journal of Number Theory
George Markowsky
J. Math. Anal. Appl.