Selected Research Achievements by Yongge Wang

Models for secure communication and computation
Supported by: Interest
In order to design a secure system, we need to know what kind of attacks we are facing and what kind of models are suitable for the system. We have some results in this area.
- Y.Desmedt and Y.Wang: Maximum Flows and Critical Vertices in AND/OR Graphs COCOON '02 2002, pages 238-248. Lecture Notes in Computer Science 2387, Springer-Verlag. (pdf, 202K)
- Y.Wang, Y.Desmedt, and M.Burmester: Models for dependable computation with multiple inputs and some hardness results. Fundamenta Informaticae, 42(1):61--73, 2000. (pdf, 251K)
- Y.Desmedt, M.Burmester, and Y.Wang: Using approximation hardness to achieve dependable computation. In: Proc. of RANDOM 98, pages 172-186. Lecture Notes in Computer Science 1518, Springer Verlag. (postscript, 82K)
Secure communication in public networks
Supported by: Interest
In order for Alice and Bob to achieve unconditionally secure communication, they need to share a secret! If Alice and Bob have never meet each other, how could they share this first secret? Our following results solve this problem partially.
- Y.Desmedt and Y.Wang: Perfectly Secure Message Transmission Revisited. EuroCrypt'02 2002, pages 502-517. Lecture Notes in Computer Science 2332, Springer-Verlag. (pdf, 259K)
- Y.Wang and Y.Desmedt: Secure communication in multicast channels. Journal of Cryptology 14(2):121--135, 2001. (pdf, 264K)
- Y.Desmedt and Y.Wang: Efficient Zero-knowledge proofs for some practical graph problems. Proceedings of Third Conference on Security in Communication Networks, Lecture Notes in Computer Science 2576, pages 296--308 (pdf, 150K)
Critical analysis of the use of redundancy to achieve survivability in the presence of malicious attacks
Supported by: DARPA contract F30602-97-1-0205
From the research on communication security one learns that, although redundancy has been utilized to achieve reliability, if the errors are caused maliciously the use of redundancy does not necessarily work. The goal is to adapt the lessons from the research on communication security to study when redundancy can and cannot be used to achieve survivability. The results of this project could be found in the separate page: DARPA contract F30602-97-1-0205 (UNCC) or DARPA contract F30602-97-1-0205 (FSU)

Computational complexity and computability theory
Supported by: Heidelberg University (Germany) and Auckland University (New Zealand)
Random sequences were first introduced by von Mises in 1919 as a foundation for probability theory. von Mises thought that random sequences were a type of disordered sequences (stochastic approach). Ville constructed a counter example in 1939 to show that von Mises approach is not a good choice. Later, a complete different approach (entropy based) to the definition of random sequences was proposed by Kolmogorov and Chaitin independently, and was further developed by Levin, Schnorr and others (more introduction here). Finally, Martin-Loef (then a student of Kolmogorov) developed a third approach (typicalness based) to the definition of random sequences in 1966. In 1970s, Schnorr tried to give a uniform approach to the definition of random sequences using martingales. Later, Lutz introduced these concepts to the computational complexity theory. A long open question in this area had been the following one: were recursive martingale based random sequences the same as effective non-constructivity based random sequences? van Lambalgen (1987) and Jack Lutz (1992) have conjectured that they are different. Indeed, this problem had been open since Schnorr's work in 1971. van Lambalgen and Lutz re-examined this problem due to its increasing importance in the complexity theory at that time. Many researchers in this area had tried to solve this problem without success. Using a novel construction, I showed that these two concepts are indeed different in 1995. The result was included in my Phd thesis and the following publications:
- Y.Wang: Randomness and Complexity. 1996. (pdf, 971K)
- Y.Wang: A separation of two randomness concepts. Information Processing Letters, 69(3):115--118, 1999.(pdf, 154K)
- Y.Wang: Resource bounded randomness and computational complexity. Theoretical Computer Science 237(1-2):33--55, 2000. (pdf, 164K)
Chaitin called the halting probability of a universal self-delimiting Turing machine the W number. W number is the most complicated computable number since it is random. When working with Chaitin in IBM Watson research, Solovay defined the concept of W-like number. Roughly speaking, a real number is W-like if its approximation dominates the approximation of all other computable real numbers. Solovay showed that Chaitin's W number is W-like. When I worked with Professor Chris Calude in Auckalnd University (New Zealand), I showed that indeed, each W-like number is a W number. Then I conjectured several possibility for computable real numbers. Professor Slaman from UC Berkeley has answered all these conjectures affirmatively in their paper. My results have appeared in the following paper:
- C.Calude, P.Hertling, B.Khoussainov, and Y.Wang: Recursively enumerable reals and Chaitin's W numbers. Theoretical Computer Science 255:125--149, 2001. (pdf, 200K)
I have many other important contributions to the area of computability and complexity theory. Compared to the above two important results, however, my other results are not widely cited yet. For a complete list of my results, it is referred to my publications. In the following, we list a few representatives.
- K.Ambos-Spies, E.Mayordomo, Y.Wang, and X. Zheng: Resource bounded balanced genericity, stochasticity and weak randomness. In: Proc. 13rd STACS, pages 63-74. Lecture Notes in Computer Science 1046, 1996. (pdf, 185K)
- Y.Wang: The law of the iterated logarithm for p-random sequences. In: Proc. 11th IEEE Conference on Computational Complexity (CCC), pages 180-189. IEEE Computer Society Press, 1996. (pdf, 212K)
- Y.Wang: NP-hard sets are superterse unless NP is small. Information Processing Letters 61(1):1-6, 1997. (pdf, 153K)
- P.Hertling and Y.Wang: Invariance properties of random sequences. Journal of Universal Computer Science, 3(11):1241-1449, 1997. (pdf, 163K)
- Y.Wang: Randomness, stochasticity, and approximations. Theory of Computing Systems (formerly: Mathematical Systems Theory) 32:517--529, 1999. (pdf , 77K)
- Y.Wang: Category, measure, and polynomial time approximations. SIAM Journal on Computing, 28(2):394-408, 1999. (pdf, 253K)
- W.Merkle and Y.Wang: Separations by random oracles and almost-classes for generalized reducibilities. Mathematical Logic Quarterly 47(2):249--269, 2001. (pdf, 301K)
- Y.Wang: The algebraic structure of the isomorphic types of tally polynomial time sets. Archive for Mathematical Logic 41(3): 215--244, 2002. (pdf, 301K)