Spelling suggestions: "subject:"computational complexity"" "subject:"computational komplexity""
1 |
Construction and computational complexity of pooling designs /Liu, Zhen. January 2006 (has links)
Thesis (Ph. D.)--University of Texas at Dallas, 2006. / Includes vita. Includes bibliographical references (leaves 95-99).
|
2 |
Time-space tradeoffs for nonuniform computation /Vee, Erik. January 2004 (has links)
Thesis (Ph. D.)--University of Washington, 2004. / Vita. Includes bibliographical references (p. 206-213).
|
3 |
Communication complexity /Kimmel, Peter G. January 1997 (has links)
Thesis (Ph. D.)--University of Chicago, Dept. of Computer Science, August 1997. / Includes bibliographical references. Also available on the Internet.
|
4 |
Some results in communication complexity.January 2010 (has links)
Mak, Yan Kei. / Thesis (M.Phil.)--Chinese University of Hong Kong, 2010. / Includes bibliographical references (leaves 59-63). / Abstracts in English and Chinese. / Chapter 1 --- Introduction --- p.6 / Chapter 1.1 --- Historical background --- p.6 / Chapter 1.2 --- Why study communication complexity? --- p.7 / Chapter 1.3 --- Main ideas and results --- p.8 / Chapter 1.4 --- Recent development --- p.12 / Chapter 1.5 --- Structure of the thesis --- p.12 / Chapter 2 --- Deterministic Communication Complexity --- p.13 / Chapter 2.1 --- Definitions --- p.13 / Chapter 2.2 --- Tiling lower bound --- p.16 / Chapter 2.3 --- Fooling set lower bound --- p.21 / Chapter 2.4 --- Rank lower bound --- p.24 / Chapter 2.5 --- Comparison of the bounds --- p.27 / Chapter 3 --- Nondeterministic Communication Complexity --- p.29 / Chapter 3.1 --- Definitions --- p.29 / Chapter 3.2 --- "Gaps between N0(f), N1(f) and D(f)" --- p.31 / Chapter 3.3 --- Aho-Ullman-Yannakakis Theorem --- p.33 / Chapter 4 --- Randomized Communication Complexity --- p.38 / Chapter 4.1 --- Preliminaries --- p.38 / Chapter 4.2 --- Definitions --- p.39 / Chapter 4.3 --- Error reduction --- p.41 / Chapter 4.4 --- Exponential gap with D(f) --- p.42 / Chapter 4.5 --- The public coin model --- p.44 / Chapter 4.6 --- Distributional complexity --- p.46 / Chapter 5 --- Communication Complexity Classes --- p.51 / Chapter 5.1 --- Basic classes --- p.51 / Chapter 5.2 --- Polynomial-time hierarchy --- p.52 / Chapter 5.3 --- Reducibility and completeness --- p.53 / Chapter 6 --- Further topics --- p.56 / Chapter 6.1 --- Quantum communication complexity --- p.56 / Chapter 6.2 --- More techniques for bounds --- p.57 / Chapter 6.3 --- Complexity of communication complexity --- p.57 / Bibliography --- p.59
|
5 |
Randomness and completeness in computational complexity /Melkebeek, Dieter van January 1999 (has links)
Thesis (Ph. D.)--University of Chicago, Dept. of Computer Science, June 1999. / Includes bibliographical references. Also available on the Internet.
|
6 |
Constructions, Lower Bounds, and New Directions in Cryptography and Computational ComplexityPapakonstantinou, Periklis 01 September 2010 (has links)
In the first part of the thesis we show black-box separations in public and private-key cryptography. Our main result answers in the negative the question of whether we can base Identity Based Encryption (IBE) on Trapdoor Permutations. Furthermore, we make progress towards the black-box separation of IBE from the Decisional Diffie-Hellman assumption. We also show the necessity of adaptivity when querying one-way permutations to construct pseudorandom generators a' la Goldreich-Levin; an issue related to streaming models for cryptography.
In the second part we introduce streaming techniques in understanding randomness in efficient computation, proving lower bounds for efficiently computable problems, and in computing cryptographic primitives.
We observe [Coo71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP,BPP an so on. By parametrizing on the number of passes over the random tape
we provide a technical perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize
BPNC (a class believed to be much lower than P \subseteq BPP). We also obtain a number
of results for variants of the main model, regarding e.g. the fooling power of Nisan's pseudorandom generator (PRG) [N92]
for the derandomization of BPNC^1, and the
relation of parametrized access to NP-witnesses with width-parametrizations of SAT.
A substantial contribution regards a streaming approach to lower bounds
for problems in the NC-hierarchy (and above).
We apply Communication Complexity to show
a streaming lower bound for a model with an unbounded (free-to-access) pushdown storage.
In particular, we obtain a $n^{\Omega(1)}$ lower bound simultaneously in the space and in the number of passes over the input, for a variant of inner product. This is the first lower bound for machines that correspond to poly-size circuits, can do Parity, Barrington's language, and decide problems in P-NC assuming EXP \neq PSPACE.
Finally, we initiate the study of log-space streaming computation of cryptographic primitives. We observe that the work on Cryptography in NC^0 [AIK08] yields
a non-black-box construction of a one-way function computable in an O(log n)-space bounded streaming model.Also, we show that relying on this work is in some sense necessary.
|
7 |
Constructions, Lower Bounds, and New Directions in Cryptography and Computational ComplexityPapakonstantinou, Periklis 01 September 2010 (has links)
In the first part of the thesis we show black-box separations in public and private-key cryptography. Our main result answers in the negative the question of whether we can base Identity Based Encryption (IBE) on Trapdoor Permutations. Furthermore, we make progress towards the black-box separation of IBE from the Decisional Diffie-Hellman assumption. We also show the necessity of adaptivity when querying one-way permutations to construct pseudorandom generators a' la Goldreich-Levin; an issue related to streaming models for cryptography.
In the second part we introduce streaming techniques in understanding randomness in efficient computation, proving lower bounds for efficiently computable problems, and in computing cryptographic primitives.
We observe [Coo71] that logarithmic space-bounded Turing Machines, equipped with an unbounded stack, henceforth called Stack Machines, together with an external random tape of polynomial length characterize RP,BPP an so on. By parametrizing on the number of passes over the random tape
we provide a technical perspective bringing together Streaming, Derandomization, and older works in Stack Machines. Our technical developments relate this new model with previous works in derandomization. For example, we show that to derandomize parts of BPP it is in some sense sufficient to derandomize
BPNC (a class believed to be much lower than P \subseteq BPP). We also obtain a number
of results for variants of the main model, regarding e.g. the fooling power of Nisan's pseudorandom generator (PRG) [N92]
for the derandomization of BPNC^1, and the
relation of parametrized access to NP-witnesses with width-parametrizations of SAT.
A substantial contribution regards a streaming approach to lower bounds
for problems in the NC-hierarchy (and above).
We apply Communication Complexity to show
a streaming lower bound for a model with an unbounded (free-to-access) pushdown storage.
In particular, we obtain a $n^{\Omega(1)}$ lower bound simultaneously in the space and in the number of passes over the input, for a variant of inner product. This is the first lower bound for machines that correspond to poly-size circuits, can do Parity, Barrington's language, and decide problems in P-NC assuming EXP \neq PSPACE.
Finally, we initiate the study of log-space streaming computation of cryptographic primitives. We observe that the work on Cryptography in NC^0 [AIK08] yields
a non-black-box construction of a one-way function computable in an O(log n)-space bounded streaming model.Also, we show that relying on this work is in some sense necessary.
|
8 |
Towards a proportional sampling strategy according to path complexity a simulation study /Yip, Wang. January 2000 (has links)
Thesis (M. Phil.)--University of Hong Kong, 2001. / Includes bibliographical references (leaves 55-56).
|
9 |
Average-case complexity theory and polynomial-time reductionsPavan, A. January 2001 (has links)
Thesis (Ph. D.)--State University of New York at Buffalo, 2001. / "August 2001." Includes bibliographical references (p. 80-87). Also available in print.
|
10 |
Efficient evolution of neural networks through complexificationStanley, Kenneth Owen 28 August 2008 (has links)
Not available / text
|
Page generated in 0.0935 seconds