Computer Science

Computer Science Seminar: Dr. Tuncay Tekle from Stonybrook University


Computer Science Seminar: Dr. Tuncay Tekle from Stonybrook University
When: Tuesday, April 18th at 3:10pm
Where: 1131 Kemper Hall
Title: Efficient Algorithms with Precise Complexity Guarantees via Queries in Datalog and Extensions
Abstract:
Many complex analysis problems can be most clearly and easily specified as logic rules and queries, where rules specify how given facts can be combined to infer new facts, and queries select facts of interest to the analysis problem at hand. However, it has been extremely challenging to obtain efficient implementations from logic rules and understand their time and space complexities, particularly for answering queries without inferring all facts.
Datalog is a logic language capturing an important class of rules for applications in databases, program analysis, security, semantic web, natural language processing, machine learning, and many other areas. We have characterized the complexity of a well-known query-answering engine and developed novel methods for efficiently answering queries in Datalog and its extensions with precise time and space complexities. We used the methods to solve important problems in different areas, including answering graph queries in many applications, pointer analysis, and context-free grammar parsing. Our results match known optimal algorithms, or in many cases provide a lower complexity than the best one previously known. Current and future work is focused on answering more advanced queries to obtain efficient algorithms for machine learning, natural language processing, and distributed computation.
Bio:
Tuncay Tekle obtained his PhD  from Stony Brook University in 2010 working on efficient implementation of logic queries with time and space complexity guarantees under the supervision of Annie Liu. Upon graduation, he joined LogicBlox, a company at the frontier of the use of logic programming and design and implementation of a modern smart database for applications in retail, manufacturing and distribution, and financial services. Since 2014, he is an independent consultant developing software for data intensive applications for large retailers in the US, and teaches at the Data Analytics master’s program at Sabanci University in Istanbul. Since 2016, he has been a visiting assistant professor at Stony Brook University. His interests include high-level programming languages and efficient implementations, algorithm design and generation of efficient algorithms from specifications, query optimization and complexity analysis.

Location
1131 Kemper Hall

Loading Map....
border