Loading...
Please wait, while we are loading the content...
Similar Documents
2.1 Approximability Theory 2.2 Complexity Theory 2.3 Cryptography
| Content Provider | Semantic Scholar |
|---|---|
| Author | Ausiello Crescenzi Gambosi Kann, M. Spaccamela, Protasi Håstad Impagliazzo, Levin |
| Copyright Year | 1999 |
| Abstract | The results of TCS research at Nada, KTH will be described in three pages, and we select five publications. We have chosen publications describing work with a high degree of student involvement, reflecting the use of TFR funding. With the given page limit, most details are omitted. References to selected papers below are numbered. The research has both been directed to positive results (construction of approximation algorithms) and negative results (non-approximability of problems). There have been a few more negative results than positive results in our results. During the last years the main tool used for proving positive approximation results has been semi-definite programming, a technique first used for approximation in 1994 by Goemans and Williamson. We have developed and applied variants of this technique in several papers, e.g. The main technique for finding and improving negative results during the last years has been interactive proofs, i.e. the possibility to express complexity classes such as NP using interactive proof systems with one or two provers. This is one of the most interesting and startling development in the whole area of theoretical computer science. Negative results can be found either by reductions using known proof systems (see e.g. have written a chapter about hardness of approximation in Annotated Bibliographies in Combinatorial Optimization. The best upper and lower bounds of approximability for hundreds of NP-complete optimization problems have been collected by Crescenzi and Kann during the whole period of the project. This collection is available on the web and is updated twice a year. The problem list is also part of a very recent book The general area in which we have worked is that of establishing lower bounds for natural functions in restricted computational models. Two models of computation where this program has been especially successful are small-depth circuits and monotone circuits. The great steps in both models were taken in the 1980'ies but developments during the last decade has increased our understanding considerably. Our main results in the area of monotone complexity are the symmetric approximation method introduced by Berg and Ulfberg [1] and the lower bounds for the depth of monotone circuits computing con-nectivity by Goldmann and Håstad (1994, 1998). The former very much simplifies the rather complicated combinatorial arguments that were previously used for proving lower bounds for monotone circuits. For small-depth circuits a number of results were established using similar methods. Cai, Chen and Håstad (1998) studies … |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.nada.kth.se/theory/tfrutv99/tcsresults.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
