• 【萍乡天气】最新萍乡今天天气,实时提供萍乡气温、空气质量、24小时天气预报、生活指数查询 2019-04-19
  • 古力娜扎穿小西装化身清纯学生妹 热情拥抱粉丝 2019-04-19
  • 中欧班列让开放之路越走越宽 2019-04-13
  • “电商定制”价廉未必物美 成为“低价劣质”代名词 2019-04-13
  • 菜鸟世界杯送出50吨包裹-热门标签-华商网数码 2019-04-12
  • 曾祖父、曾祖母、祖父、祖母、父亲、母亲、重孙。一家7人,如果两家联姻,两家共十四人,请问:“看着就想笑”你那15人是咋算出来的? 2019-04-12
  • 权威解读!养老保险基金 中央怎么调剂? 2019-04-10
  • 欢乐“粽”情过端午 尽情放“粽”嗨起来 2019-04-05
  • 南昌重拳整治酒驾毒驾 2019-04-04
  • 德国:网上发布不当言论最高可获刑5年 2019-04-04
  • 哭泣的是鸿茅药酒,受伤的是中华医药!(原创首发) 2019-04-01
  • 不动产登记全国联网 名下多少套房一查就知道 2019-04-01
  • 重庆市南川区:社区“法律诊所”推进普法依法治理 2019-03-29
  • 国家税务总局天津市税务局正式对外挂牌 2019-03-29
  • 新华保险荆州中支助力首届荆楚文化旅游节开幕 2019-03-24
  • [08-16] The Limits of Symmetric Computation

    文章来源:  |  发布时间:2018-08-15  |  【打印】 【关闭

      

    全程打闲一年100万 www.edria.net Title: The Limits of Symmetric Computation

    Speaker: Professor Anuj Dawar, University of Cambridge, UK

    Time: 10:00 am, August 16th (Thursday), 2018.

    Venue: Lecture room (Room 334), Building 5, Software Park, Chinese Academy of Sciences

    Abstract:

      Lower bounds for many NP-hard problems have been proved for restricted circuit models. In this talk I introduce a restriction to symmetric circuits, which captures a natural property of algorithms that respect symmetries of their input. I show that lower bounds on such circuits can be derived from inexpressibility results in logic studied in finite model theory. Combining this with the rich expressive power of these logics, allows us to derive lower bounds for strong approximation methods based on semi-definite programming. Exploring the limits of symmetric computation offers a rich research vista bringing together logic, algebra and combinatorics with algorithms.

    Biography:

      Anuj Dawar is the Professor of Logic and Algorithms at the University of Cambridge, where he has been a member of the faculty since January 1999.

      His research and teaching interests focus on theoretical computer science. He is especially interested in understanding the limits of algorithmic methods in solving hard problems and developing a suite of logical and combinatorial methods for this study. His recent work has focused on developing a theory of symmetric computation.

      He obtained a Bachelor's degree from the Indian Institute of Technology, Delhi, a Master's degree from the University of Delaware and a PhD from the University of Pennsylvania in 1993. He worked as a post-doctoral researcher and a lecturer at Swansea University before moving to Cambridge in 1999. He has held visiting positions at Indiana University, Bloomington (USA), at INRIA and the University of Bordeaux (France) and at RWTH, Aachen (Germany). He served from 2013-17 as president of the European Association for Computer Science Logic. He is a Fellow of the Alan Turing Institute in London.

  • 【萍乡天气】最新萍乡今天天气,实时提供萍乡气温、空气质量、24小时天气预报、生活指数查询 2019-04-19
  • 古力娜扎穿小西装化身清纯学生妹 热情拥抱粉丝 2019-04-19
  • 中欧班列让开放之路越走越宽 2019-04-13
  • “电商定制”价廉未必物美 成为“低价劣质”代名词 2019-04-13
  • 菜鸟世界杯送出50吨包裹-热门标签-华商网数码 2019-04-12
  • 曾祖父、曾祖母、祖父、祖母、父亲、母亲、重孙。一家7人,如果两家联姻,两家共十四人,请问:“看着就想笑”你那15人是咋算出来的? 2019-04-12
  • 权威解读!养老保险基金 中央怎么调剂? 2019-04-10
  • 欢乐“粽”情过端午 尽情放“粽”嗨起来 2019-04-05
  • 南昌重拳整治酒驾毒驾 2019-04-04
  • 德国:网上发布不当言论最高可获刑5年 2019-04-04
  • 哭泣的是鸿茅药酒,受伤的是中华医药!(原创首发) 2019-04-01
  • 不动产登记全国联网 名下多少套房一查就知道 2019-04-01
  • 重庆市南川区:社区“法律诊所”推进普法依法治理 2019-03-29
  • 国家税务总局天津市税务局正式对外挂牌 2019-03-29
  • 新华保险荆州中支助力首届荆楚文化旅游节开幕 2019-03-24