University of Cambridge > Talks.cam > Logic and Semantics Seminar (Computer Laboratory) > Cyclic Implicit Complexity

  Browse A-Z

Log in

University Account External (via Google)

🔐 Log In

Information on

Subscribing to talksdetails Finding a talkdetails Adding a talkdetails Disseminating talksdetails Help and Documentationdetails

ℹī¸ Information

Cyclic Implicit Complexity

Download to your calendar using vCal

  • UserAnupam Das, University of Birmingham
  • ClockFriday 11 March 2022, 14:00-15:00
  • HouseFW26.

If you have a question about this talk, please contact Jamie Vicary .

THIS TALK WILL BE IN SS03 , NOT FW26

Circular (or cyclic) proofs have received increasing attention in recent years, and have been proposed as an alternative setting for studying (co)inductive reasoning. In particular, now several type systems based on circular reasoning have been proposed. However, little is known about the complexity theoretic aspects of circular proofs, which exhibit sophisticated loop structures atypical of more common ‘recursion schemes’. We attempt to bridge the gap between circular proofs and implicit computational complexity. Namely we introduce a circular proof system based on Bellantoni and Cook’s famous safe-normal function algebra, and we identify suitable proof theoretical constraints to characterise the polynomial-time and elementary computable functions.

This talk is part of the Logic and Semantics Seminar (Computer Laboratory) series.

This talk is included in these lists:

Note that ex-directory lists are not shown.

Other lists

Graphene CDT Advanced Technology Lectures From discovery science to industrial applications Wolfson Lecture Theatre, Dept. of Chemistry & Zoom

Other talks

title abstract tba Title TBC Title to be confirmed Afternoon Break Machine Learning for Spectral Geometry and Vice Versa Group Presentation 3
 

Š 2006-2025 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity