{"id":7360,"date":"2021-06-02T12:29:16","date_gmt":"2021-06-02T04:29:16","guid":{"rendered":"https:\/\/www.zlaire.net\/events\/previous\/?p=7360"},"modified":"2021-06-06T21:18:02","modified_gmt":"2021-06-06T13:18:02","slug":"anuj-dawar-the-limits-of-symmetric-computation","status":"publish","type":"post","link":"https:\/\/www.zlaire.net\/events\/previous\/2021\/06\/anuj-dawar-the-limits-of-symmetric-computation\/","title":{"rendered":"Anuj Dawar: The Limits of Symmetric Computation"},"content":{"rendered":"<p><strong>Date:<\/strong>&nbsp;21st June, 2021 (16:30-18:30)<\/p>\n<p><strong>Speaker:<\/strong> Anuj Dawar (Cambridge University)<\/p>\n<p><strong>Title:<\/strong> The Limits of Symmetric Computation<br \/>\n<strong>Abstract:<\/strong> The most famous open problem in theoretical computer science, known as&nbsp;the P vs. NP problem challenges us to prove that for some natural&nbsp;search problems, no efficient algorithm is possible. At the moment,&nbsp;we have no idea how to prove such a statement. In order to make&nbsp;meaningful progress, we can restrict the class of algorithms we&nbsp;consider and show that, within these restrictions, no efficient&nbsp;algorithm exists. In this talk, I consider a natural restriction to&nbsp;symmetric algorithms. I explain how symmetries arise naturally in&nbsp;computational problems and why algorithms that respect these&nbsp;symmetries have inherent limitations. Many of our most powerful&nbsp;algorithmic techniques are symmetry-preserving, while others are not.&nbsp;Exploring these limits offers a rich research agenda combining logic,&nbsp;algebra and combinatorics with algorithms.<\/p>\n<p><strong>Platform: <\/strong>Zoom<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Date:&nbsp;21st June, 2021 (16:30-18:30) Speaker: Anuj Dawar (Cambridge University) Title: The Limits of Symmetric Computation Abstract: The most famous open problem in theoretical computer science, known as&nbsp;the P vs. NP problem challenges us to prove that for some natural&nbsp;search problems, <span class=\"excerpt-dots\">&hellip;<\/span> <a class=\"more-link\" href=\"https:\/\/www.zlaire.net\/events\/previous\/2021\/06\/anuj-dawar-the-limits-of-symmetric-computation\/\"><span class=\"more-msg\">Continue reading &rarr;<\/span><\/a><\/p>\n","protected":false},"author":13,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"ngg_post_thumbnail":0,"footnotes":""},"categories":[1],"tags":[],"class_list":["post-7360","post","type-post","status-publish","format-standard","hentry","category-invited-talks"],"_links":{"self":[{"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/posts\/7360","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/users\/13"}],"replies":[{"embeddable":true,"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/comments?post=7360"}],"version-history":[{"count":4,"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/posts\/7360\/revisions"}],"predecessor-version":[{"id":7371,"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/posts\/7360\/revisions\/7371"}],"wp:attachment":[{"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/media?parent=7360"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/categories?post=7360"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.zlaire.net\/events\/previous\/wp-json\/wp\/v2\/tags?post=7360"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}