147 research outputs found
On Circuit Complexity Classes and Iterated Matrix Multiplication
No full textIn this thesis, we study small, yet important, circuit complexity classes within NC1, such as ACC0 and TC0. We also investigate the power of a closely related problem called Iterated Matrix Multiplication and its implications in low levels of algebraic complexity theory. More concretely, • We show that extremely modest-sounding lower bounds for certain problems can lead to non-trivial derandomization results. – If the word problem over S5 requires constant-depth threshold circuits of size n1+ for some > 0, then any language accepted by uniform polynomial-size probabilis-tic threshold circuits can be solved in subexponential time (and more strongly, can be accepted by a uniform family of deterministic constant-depth threshold circuits of subexponential size.) – If there are no constant-depth arithmetic circuits of size n1+ for the problem of multiplying a sequence of n 3-by-3 matrices, then for every constant d, black-box identity testing for depth-d arithmetic circuits with bounded individual degree can be performed in subexponential time (and even by a uniform family of deterministic constant-depth AC circuits of subexponential size). ii • ACCm circuits are circuits consisting of unbounded fan-in AND, OR and MODm gates and unary NOT gates, where m is a fixed integer. We show that there exists a language in non-deterministic exponential time which can not be computed by any non-uniform family of ACCm circuits of quasi-polynomial size and o(log log n) depth, where m is an arbitrarily chosen constant. • We show that there are families of polynomials having small depth-two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clari-fies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several settings
On the Power of Algebraic Branching Programs of Width Two
No full textWe show that there are families of polynomials having small depth two arithmetic circuits that cannot be expressed by algebraic branching programs of width two. This clarifies the complexity of the problem of computing the product of a sequence of two-by-two matrices, which arises in several settings.Peer reviewe
Unsolved Problems in Special and General Relativity
Get PDFThis book includes 21 papers written by 23 authors and co-authors: Hua Di, Li Zifeng, Li Wen-Xiu, Shi Yong-Cheng, Xu Jianmin, Dong Jingfeng, Duan Zhongxiao, Fu Yuhua, Guo Kaizhe, Guo Chongwu, Guo Ying-Huan, Guo Zhen-Hua, Hu Chang-Wei, Jiang Chun-Xuan, Liu Taixiang, Tu Runsheng, Wu Fengming, Yang Shijia, Cao Shenglin, Leo G. Sapogin, V. A. Dzhanibekov, Yu. A. Ryabov, and Florentin Smarandache.
The editors hope that all these papers will contribute to the advance of scholarly research on several aspects of Special and General Relativity. This book is suitable for students and scholars interested in studies of physics
Taming the densification challenge in next generation wireless LANs: An investigation into the use of dynamic sensitivity control
No full text
- …
