Lics

IEEE Symposium on Logic in Computer Science

LICS Home - LICS Awards - LICS Newsletters - LICS Archive - LICS Organization - Logic-Related Conferences - Links

Nineteenth Annual IEEE Symposium on

Logic in Computer Science (LICS 2004)

Invited Paper: Feasible Proofs and Computations: Partnership and Fusion (at LICS 2004)

Authors: Alexander A. Razborov

Abstract

A computation or a proof is called feasible if it obeys prescribed bounds on the resources consumed during its execution. It turns out that when restricted to this world of feasibility, proofs and computations become extremely tightly interrelated, sometimes even indistinguishable. Moreover, many of these rich relations, underlying concepts, techniques etc. look very different from their "classical" counterparts, or simply do not have any. This talk is intended as a very informal and popular (highly biased as well) attempt to illustrate these fascinating connections by several related developments in the modern complexity theory.

BibTeX

  @InProceedings{Razborov-FeasibleProofsandCo,
    author = 	 {Alexander A. Razborov},
    title = 	 {Feasible Proofs and Computations: Partnership and Fusion},
    booktitle =  {Proceedings of the Nineteenth Annual IEEE Symposium on Logic in Computer Science (LICS 2004)},
    year =	 {2004},
    month =	 {July}, 
    pages =      {134--138},
    location =   {Turku, Finland}, 
    note =       {Invited Talk},
    publisher =	 {IEEE Computer Society Press}
  }
   

Last modified: 2018-06-2121:59
Andrzej Murawski