assignment at the preliminary meeting (Vorbesprechung) or via EMail to Christian Schindelhauer
Thursday, October 16th, 11:15 F2.211
(8-12 pages) will be announced
will be announced
Theoretically, quantum computers can solve problems too complex for classical computers.
While it is known that a quantum algorithm based on comparisons alone cannot outperform classical sorting algorithms by more than a constant factor in time complexity, this is wrong in a space bounded setting. For sequential computers the time-space tradeoff for sorting is well known to be T S = Ω(n2) it turns out that for quantum coputers this tradeoff is only T S = Ω(n3/2) .
Kolmogorov-complexity measures the compressibility of words. A random
choice of a word maximizes the Kolmogorov-complexity. Thus,
Kolmogorov-complexity also measures the entropy, i.e. the randomness,
of words. This complexity measure has been used as a powerfull tool in
computational complexity.
Quantum computation differs a lot from classical computation. So finding
an appropriate defintion for quantum computers is a challenging task.
A state of the art survey of the man who found the first PTAS for Euclidean TSP, invented PCP, and ...
Boolean satisfiability of CNF-formulas with at at most two literals per clause, i.e. 2-SAT, can be tested in linear time. Surprisingly, the maximzation problem, i.e. satisfy as many clauses as possible, is computationally hard. This paper improves on the upper time bound of this optimization problem.
For the first time a natural problem can be proven to be non approximable by a polylogarithmic factor. Specifically the directed-steiner-tree problem, is not approximable within log2-ε.
What does computability mean when it comes to geometric algorithms? Can one really decide whether a point lies inside, outside or on the line of a circle?
The problem of Byzantine agreement refers originally to three generals
commanding armies planning to attack a town. If at least two of them
attack, then they win. If only one attacks the war is lost. Now one
general is cheating (a special problem of Byzantinge politics). He
will not attack and even more dangereous he trying to sabotage any
plans of the other generals who do not know which general can be
trusted.
E.g. General A plans to attack next morning and tells
this B an C using mesengers. General C (cheater) says to A that he
won't attack, and tells B that he will. B now hears "attack" and
"don't attack". If B asks A and C about this both will tell that the
other is a cheater (and C will tell A also that B is a cheater). What
can be done?
Private computation allows computers of network to compute something such that all input information is kept secret and only the output of the function is known. E.g. a group of workers want to computer the sum of all their salaries without exhibiting each one's income.
Protocols for this problems are known for two decades, allowing even fault-tolerance using some randomness. This paper deals with the tradeoff between this resources.
Prove a fact without revealing the fact itself. In this award-winning Phd thesis every detail of the proof is reveal, yet the proved facts are yet kept secretly (Holistic!)
Cook "invented" NP-completeness. In this survey article he shows for which instances NP-problems are hard (of course, only if NP is not eqal to P.)
Usually, one uses pattern matching methods for identifying genes. This papers describes how Markov chains can be used for the identification of genes in microbial genomes.
More topics are available on request.
This seminar will be organized as a two-day seminar at a location to be announced (possibly, not necessarily off campus). For more information please contact Christian Schindelhauer.