dimacs logo color

Events

Event Calendar

« Previous Month

August 2026

Next Month »
Sun Mon Tue Wed Thu Fri Sat
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

Seminar Details

Some Fun Theorems in Computational Complexity Theory

  • Start Date: July 6, 2006
  • Event Start Time: 12:00 PM
  • Event End Time: 1:00 PM
  • Organizers: Christine Agnese
  • Seminar Series: REU Seminar
  • Presenter(s): Eric Allender - Rutgers University
  • Event Location: DIMACS Seminar room
  • Abstract: Computational complexity theory tries to show that certain problems are hard to compute. However, does this even make sense? Can the notion of being "hard to compute" be made mathematically precise? There are some surprising difficulties that need to be overcome, in order to obtain a meaningful concept of computational complexity; many intuitive notions (such as the idea of an "optimal algorithm" for a given problem) have to be abandoned in the general case. This talk will describe some of the main triumphs of the field of computational complexity theory, as well as discussing some of the limitations that are inherent in any theory of computational complexity.