A medley for computational complexity: With applications of information theory, learning theory, and Ketan Mulmuley's parametric complexity technique

Authors	B.S. Loff Barreto
Supervisors	H. Buhrman
Award date	21-01-2014
Number of pages	98
Organisations	Interfacultary Research - Institute for Logic, Language and Computation (ILLC)
Document type	PhD thesis
Note	The information in this dissertation is free; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 2 of the License, or (at your option) any later version. This work is distributed in the hope that it will be useful, but without any warranty; without even the implied warranty of fitness for any particular purpose. See the GNU General Public License for more details. Research conducted at: Universiteit van Amsterdam
Language	English
Downloads	Thesis Front cover Title pages Acknowledgments Abstract Samenvatting Contents Introduction for a general audience 1: Power from the set of random strings 2: Reductions to sparse sets 3: Hardness results for Knapsack problems 4: Towards a reverse Newman's theorem in information complexity Bibliography Summary
Permalink to this page

Back

UvA-DARE