## Current Trends in Theoretical Computer Science: The Challenge of the New Century, Volume 1This book is based on columns and tutorials published in the Bulletin of the European Association for Theoretical Computer Science (EATCS) during the period 2000-2003. It presents many of the most active current research lines in theoretical computer science. The list of contributors includes many of the well-known researchers in theoretical computer science. Most of the articles are reader-friendly and do not presuppose much knowledge of the area in question. Therefore, the book constitutes very suitable supplementary reading material for various courses and seminars in computer science. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

CHAPTER 1 | 3 |

Open Problems in the Theory of Scheduling | 19 |

1993 1998 | 39 |

Drmota and W Szpankowski | 63 |

Algorithm Engineering | 83 |

PRIMES e P Without Assumptions by J Díaz | 105 |

Selfish Task Allocation by E Koutsoupias | 111 |

CHAPTER 2 | 121 |

A Primer to Property | 229 |

TimeSpace Lower Bounds for NPComplete Problems | 265 |

DISTRIBUTED COMPUTING | 293 |

NATURAL COMPUTING | 451 |

An Overview of Conjunctive Grammars | 545 |

567 | |

GSMs and Contexts | 581 |

Language Generating by Means of Membrane Systems | 599 |

The Division Breakthroughs by E Allender | 147 |

A Brief Overview by V Kabanets | 165 |

Recent Developments in Explicit Constructions of Extractors | 189 |

New Results New Problems | 613 |

About the Editors | 661 |

### Other editions - View all

### Common terms and phrases

analysis of algorithms applications approximation algorithm artificial chemistry asymptotic balancing network Boolean circuit Boolean function codes combinatorial consider constant construct D.E. Knuth Dagstuhl defined denote derandomization deterministic distribution Drmota efficient evolution strategies example extractor Flajolet Foundations of Computer gate given graph G H-coloring implementations input instance integer Lemma linear list-decodable lower bounds makespan Mathematics matrix mechanism Mellin transform method min-entropy molecules Nash equilibrium nodes NP-complete number of queries O(log on-line open problems operations optimal output parameters performance polynomial price of anarchy probabilistic probability Proc Proceedings processors Prodinger proof protocol proved pseudo-random quantum circuit quantum computation Quicksort random bits scheduling seed length sequence simulation solution strategy strategyproof string structures Symposium on Theory Szpankowski tasks testable testing Theorem Theory of Computing tion uniform users vector vertex vertices Wigderson worst-case