{"678545":{"#nid":"678545","#data":{"type":"event","title":"PhD Defense by Shuo Ding","body":[{"value":"\u003Cp\u003E\u003Cstrong\u003ETitle:\u003C\/strong\u003E\u0026nbsp;Witness Functions in Program Analysis and Complexity Theory\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EDate:\u003C\/strong\u003E\u0026nbsp;Tuesday, December 3, 2024\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ETime:\u003C\/strong\u003E\u0026nbsp;12:30 PM - 2:30 PM (Eastern Time)\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ELocation (in-person):\u003C\/strong\u003E\u0026nbsp;Klaus 1202\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ELocation (virtual):\u003C\/strong\u003E \u003Ca href=\u0022https:\/\/gatech.zoom.us\/j\/7018521505?pwd=jNYOdyOpgwfe3px8plpgbkgS0Rdajf.1\u0022\u003Ehttps:\/\/gatech.zoom.us\/j\/7018521505?pwd=jNYOdyOpgwfe3px8plpgbkgS0Rdajf.1\u003C\/a\u003E\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003EShuo Ding\u003C\/p\u003E\u003Cp\u003ESchool of Computer Science\u003C\/p\u003E\u003Cp\u003EGeorgia Tech\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003ECommittee\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EDr. Qirun Zhang (Advisor) - School of Computer Science, Georgia Tech\u003C\/p\u003E\u003Cp\u003EDr. Suguman Bansal - School of Computer Science, Georgia Tech\u003C\/p\u003E\u003Cp\u003EDr. Vijay Ganesh - School of Computer Science, Georgia Tech\u003C\/p\u003E\u003Cp\u003EDr. Jens Palsberg - Computer Science Department, UCLA\u003C\/p\u003E\u003Cp\u003EDr. Vivek Sarkar - School of Computer Science, Georgia Tech\u003C\/p\u003E\u003Cp\u003E\u0026nbsp;\u003C\/p\u003E\u003Cp\u003E\u003Cstrong\u003EAbstract\u003C\/strong\u003E\u003C\/p\u003E\u003Cp\u003EProving impossibility results is one of the main themes of program analysis theory and computability\/complexity theory. For example, we can prove a program analysis problem is undecidable, meaning that there does not exist an algorithm to precisely solve the problem. As another example, we can prove a problem does not belong to a complexity class, meaning that every correct algorithm for the problem must exceed the given resource restriction. In general, given a class C of computational problems and a specific computational problem P not in C, a witness function maps every candidate Q in C to an input on which P and Q are different.\u003C\/p\u003E\u003Cp\u003EWe investigate the computational properties of such witness functions and discuss their implications. In program analysis theory, we prove that a large class of undecidable program analysis problems have computable witness functions, including every semantic property described in Rice\u0027s theorem. This implies the existence of computable functions mapping a program analyzer to a more precise program analyzer. Through two real program analysis tasks (1) CFL-reachability based program analysis for Java and LLVM-IR and (2) template constraint analysis for C++, we demonstrate that computable witness functions provide guarantees on the progress of developing more and more precise program analysis techniques. In complexity theory, we prove that witness functions for major complexity classes are closely related to reductions, and use the time\/space hierarchy theorem as an example to discuss further implications in complexity class separation proofs.\u003C\/p\u003E","summary":"","format":"limited_html"}],"field_subtitle":"","field_summary":[{"value":"\u003Cp\u003EWitness Functions in Program Analysis and Complexity Theory\u003C\/p\u003E","format":"limited_html"}],"field_summary_sentence":[{"value":"Witness Functions in Program Analysis and Complexity Theory"}],"uid":"27707","created_gmt":"2024-11-19 21:02:59","changed_gmt":"2024-11-19 21:03:35","author":"Tatianna Richardson","boilerplate_text":"","field_publication":"","field_article_url":"","field_event_time":{"event_time_start":"2024-12-03T12:30:00-05:00","event_time_end":"2024-12-03T14:30:17-05:00","event_time_end_last":"2024-12-03T14:30:17-05:00","gmt_time_start":"2024-12-03 17:30:00","gmt_time_end":"2024-12-03 19:30:17","gmt_time_end_last":"2024-12-03 19:30:17","rrule":null,"timezone":"America\/New_York"},"location":"Klaus 1202","extras":[],"groups":[{"id":"221981","name":"Graduate Studies"}],"categories":[],"keywords":[{"id":"100811","name":"Phd Defense"}],"core_research_areas":[],"news_room_topics":[],"event_categories":[{"id":"1788","name":"Other\/Miscellaneous"}],"invited_audience":[{"id":"78771","name":"Public"}],"affiliations":[],"classification":[],"areas_of_expertise":[],"news_and_recent_appearances":[],"phone":[],"contact":[],"email":[],"slides":[],"orientation":[],"userdata":""}}}