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)