Please select:

• PhD-Theses,
• Master-/Diploma-Theses

Click here to see the instructions.

PhD-Theses:

---

Guang Yang:

• Cryptography and Randomness Extraction in the Multi-Stream Model
  Tsinghua University, Beijing 2015

David Gajser:

• Verifying Time Complexity of Turing Machines
  University of Ljubljana, Ljubljana 2015

Hao Song:

• Space-Bounded Communication Complexity
  Tsinghua University, Beijing 2014

Thomas Weir Watson:

• The Computational Complexity of Randomness
  University of California, Berkeley 2013

Sebastian Müller:

• On the Power of Weak Extensions of V⁰
  Charles University, Prague 2012

Shaddin Dughmi:

• Randomization and computation in strategic settings
  Stanford University, August 2011

Abuzer Yakaryilmaz:

• Classical and quantum computation with small space bounds
  Bogazici University, Istanbul, January 2011

Mahdi Cheraghchi Bashi Astaneh:

• Applications of Derandomization Theory in Coding
  School of Computer and Communication Sciences, EPFL, Lausanne, Switzerland, July 2010

Jayalal Sarma M.N.:

• Complexity Theoretic Aspects of Rank, Rigidity and Circuit Evaluation
  Institute of Mathematical Sciences, Chennai, India, February 2009

Stefano Cavagnetto:

• Propositional Proof Complexity and Rewriting
  Charles University in Prague Faculty of Mathematics and Physics, 2008

Phuong Nguyen:

• Bounded Reverse Mathematics
  Graduate Department of Computer Science, University of Toronto, 2008

Alexander Hertel:

• Applications of Games to Propositional Proof Complexity
  Department of Computer Science, University of Toronto, May 2008

Jakob Nordström:

• Short Proofs May Be Spacious: Understanding Space in Resolution
  School of Computer Science and Communication, Royal Institute of Technology (KTH), May 2008

Ryan Williams:

• Algorithms and Resource Requirements for Fundamental Problems
  Carnegie Mellon University, August 2007

Neeraj Kayal:

• Derandomizing some number-theoretic and algebraic algorithms
  Indian Institute of Technology, Kanpur, India, May 2007

Olaf Beyersdorff:

• Disjoint NP-Pairs and Propositional Proof Systems
  Humboldt-Universität zu Berllin, Germany, June 2006

Emanuele Viola :

• The Complexity of Hardness Amplification and Derandomization
  Havard University, Cambridge, Massachusetts, May 2006

Alan Skelley :

• Theories and Proof Systems for PSPACE and the EXP-Time Hierarchy
  University of Toronto, 2006

Hubert Ming Chen:

• The Computational Complexity of Quantified Constraint Satisfaction
  Cornell University, August 2004.

Morioka, Tsuyoshi:

• Logical Approaches to the Complexity of Search Problems: Proof Complexity, Quantified Propositional Calculus, and Bounded Arithmetic
  University of Toronto, 2005.

Jerabek, Emil:

• Weak Pigeonhole Principle, and Randomized Computation
  Charles University, Prague, 2005.

Aaronson, Scott:

• Limits on Efficient Computation in the Physical World
  University of California, Berkeley, 2004.

Kolokolova, Antonina:

• Systems of bounded arithmetic from descriptive complexity
  University of Toronto, October 2004.

Hanika, Jiri:

• Search Problems and Bounded Arithmetic
  Charles University, Prague, 2004.

Esteban, Juan Luis:

• Complexity measures for Resolution
  Universitat Politècnica de Catalunya, Barcelona, 2003.

Thapen, Neil:

• The Weak Pigeonhole Principle in Models of Bounded Arithmetic
  University of Oxford, United Kingdom, 2002.

Kalnishkan, Yuri:

• The Aggregating Algorithm and Predictive Complexity
  Royal Holloway, University of London, United Kingdom, 2002.

Sack, Harald:

• Improving the Power of Ordered Binary Decision Diagrams by Introducing Parity-Nodes
  Universität Trier, 2002.

Soltys, Michael:

• The Complexity of Derivations of Matrix Identities
  Department of Mathematics, University of Toronto, Toronto, Canada, 2001.

Pitt, Francois:

• A Quantifier-Free String Theory for $ALOGTIME$ Reasoning.
  University of Toronto, Department of Computer Science, 2000

Kosub, Sven:

• Complexity and Partitions
  Bayerische Julius-Maximilians-Universität Würzburg, 2000

Ulfberg, Stafan:

• On Lower Bounds for Circuits and Selection
  Royal Institute of Technology, Stockholm, Sweden, 1999

Reingold, Omer:

• Pseudo-Random Synthesizers, Functions and Permutations
  The Weizmann Institute of Science, Rehovot, Israel, 1999

Vinodchandran N. V.:

• Counting Complexity and Computational Group Theory
  Institute of Mathematical Sciences, Chennai, 1999

Harald Hempel:

• Boolean Hierarchies - On Collapse Properties and Query Order
  Institut für Informatik, Friedrich-Schiller-Universität Jena, 1998

Berthold Ruf:

• Computing and Learning with Spiking Neurons - Theory and Simulations
  Technische Universität Graz, 1998.

Thorsten Theobald:

• Transformation Techniques for Decision Diagrams in Computer-Aided Design
  Universität Trier, 1997

Luca Trevisan:

• Reductions and (Non-)Approximability
  University of Rome "La Sapienza", 1997.

Tomoyuki Yamakami:

• Average Case Computational Complexity Theory
  Department of Computer Science, University of Toronto, 1997

Amnon Ta-Shma:

• Refining Randomness
  Hebrew University, 1996.

Yongge Wang:

• Randomness and Complexity
  Universität Heidelberg, 1996

Richard Beigel:

• Query-limited Reducibilities
  Stanford University, 1995

Anna Gal:

• Combinatorial Methods in Boolean Function Complexity
  University of Chicago, 1995

Stephen J. Ponzio:

• Restricted Branching Programs and Hardware Verification
  Massachusetts Institute of Technology, 1995.

Bernd Borchert:

• Predicate Classes, Promise Classes, and the Acceptance Power of Regular Language
  Universität Heidelberg, 1994

Elvira Mayordomo:

• Contributions to the Study of Resource-Bounded Measure
  Universitat Politecnica de Catalunya, 1994.

Back to document top.

Master/Diploma Theses

---

Ondřej Ježil:

• Pseudofinite Structures and Limits
  Charles University in Prague, Faculty of Mathematics and Physics, Prague, 2022

Mykyta Narusevych:

• Models of Bounded Arithmetic
  Charles University in Prague, Faculty of Mathematics and Physics, Prague, 2022

Bruno P. Cavalar:

• Sunflower theorems in monotone circuit complexity
  Universidade de São Paulo, 2020

Ondřej Ježil:

• Spectrum problem
  Charles University in Prague, Faculty of Mathematics and Physics, Prague, 2020

Jan Pich:

• Hard tautologies
  Charles University in Prague, Faculty of Mathematics and Physics, Prague, 2011

Yoav Tzur:

• Notions of Weak Pseudorandomness and $GF(2^n)$-Polynomials
  Weizmann Institute of Scienece in Rehovot, Israel, 2009

Ondrej Mikle:

• Strong Proof System
  Charles University in Prague, Faculty of Mathematics and Physics, Prague, 2007

Marc Thurley:

• Tractability and Intractability of Parameterized Counting Problems
  Humboldt Universität zu Berlin, Germany, 2006

Pavel Sanda:

• Implicit propositional proofs
  Department of Applied Mathematics, Charles University in Prague, Czech Republic, May 2006

Cheraghchi, Mahdi:

• Locally Testable Codes
  École Polytechnique Fédérale de Lausanne, Switzerland, 2005

Zivny, Stanislav:

• Properties of oracle classes that collapse or separate complexity classes
  Vrije Universiteit in Amsterdam, 2005

Hernich, AndrÉ:

• Combining Self-Reducibility with Partial Information Algorithms
  Technische Universität Berlin, 2005

Periklis A. Papakonstantinou:

• Hierarchies and Complexity Results for Priority Algorithms
  University of Toronto, 2004

Mark Braverman:

• Computational Complexity of Euclidean Sets: Hyperbolic Julia Sets are Poly-Time Computable
  University of Toronto, 2004

Phuong Nguyen:

• VTC^0: A Second-Order Theory For TC^0
  University of Toronto, 2004

Han Henzl:

• Weak Formal Systems
  Universita Karlova v Praze, 2003

Robert Spalek:

• Quantum Circuits with Unbounded Fan-Out
  Faculty of Sciences, Vrije Universiteit Amsterdam, The Netherlands, 2002
• Space Complexity of Quantum Computation
  Charles University, Prague, Czech Republic, 2002

Alan Skelley:

• Relating the PSPACE Reasoning Power of Boolean Programs and Quantified Boolean Formulas
  University of Toronto, Canada, 2000

Till Tantau:

• Combinatorial Representations of Partial Information Classes and their Truth-Table Closures
  Technische Universität Berlin, 1999

Shai Gutner:

• Choice numbers of graphs
  Tel-Aviv University, 1992

Back to document top.

---

ISSN 1433-8092 | Imprint