Computer Science – Computational Complexity
Scientific paper
2010-07-12
Computer Science
Computational Complexity
This is my Master's Thesis written in 2005
Scientific paper
The first section starts with the basic definitions following mainly the notations of the book written by E. Kushilevitz and N. Nisan. At the end of the first section I examine tree-balancing. In the second section I summarize the well-known lower bound methods and prove the exact complexity of certain functions. In the first part of the third section I introduce the random complexity and prove the basic lemmas about it. In the second part I prove a better lower bound for the complexity of all random functions. In the third part I introduce and compare several upper bounds for the complexity of the identity function. In the fourth section I examine the well-known Direct-sum conjecture. I introduce a different model of computation then prove that it is the same as the original one up to a constant factor. This new model is used to bound the Amortized Time Complexity of a function by the number of the leaves of its protocol-tree. After this I examine the Direct-sum problem in case of Partial Information and in the Random case. In the last section I introduce the well-known hierarchy classes, the reducibility and the completeness of series of functions. Then I define the class PSPACE and Oracles in the communication complexity model and prove some basic claims about them.
Pálvölgyi Dömötör
No associations
LandOfFree
Communication Complexity does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with Communication Complexity, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Communication Complexity will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-695644