165 citations · 531 across the 35 of their papers we have counts for
7 papers · 1 filter
Lifting query complexity to time-space complexity for two-way finite automata
Shenggen Zheng, Yaqiao Li, Minghua Pan +2
Time-space tradeoff has been studied in a variety of models, such as Turing machines, branching programs, and finite automata, etc. While communication complexity as a technique ha…
Rethinking NPN Classification from Face and Point Characteristics of Boolean Functions
Jiaxi Zhang, Shenggen Zheng, Liwei Ni +2
NPN classification is an essential problem in the design and verification of digital circuits. Most existing works explored variable symmetries and cofactor signatures to develop t…
Enhanced Fast Boolean Matching based on Sensitivity Signatures Pruning
Jiaxi Zhang, Liwei Ni, Shenggen Zheng +4
Boolean matching is significant to digital integrated circuits design. An exhaustive method for Boolean matching is computationally expensive even for functions with only a few var…
From Quantum Query Complexity to State Complexity
Shenggen Zheng, Daowen Qiu
State complexity of quantum finite automata is one of the interesting topics in studying the power of quantum finite automata. It is therefore of importance to develop general meth…
Exact quantum algorithms have advantage for almost all Boolean functions
Andris Ambainis, Jozef Gruska, Shenggen Zheng
It has been proved that almost all -bit Boolean functions have exact classical query complexity . However, the situation seemed to be very different when we deal with exact q…
Communication complexity of promise problems and their applications to finite automata
Jozef Gruska, Daowen Qiu, Shenggen Zheng
Equality and disjointness are two of the most studied problems in communication complexity. They have been studied for both classical and also quantum communication and for various…
Power of the interactive proof systems with verifiers modeled by semi-quantum two-way finite automata
Shenggen Zheng, Daowen Qiu, Jozef Gruska
In this paper we explore the power of AM for the case that verifiers are {\em two-way finite automata with quantum and classical states} (2QCFA)--introduced by Ambainis and Watrous…