Seminars: Basic Studies in Computing Science

Title: Program Obfuscation: A Fascinating Research Line in Cryptography
Speaker: Dr. Ning Ding (SJTU)
Time: 9:00am, Friday Nov 18
Place: Room 3-318
Abstract: In recent years, cryptography community has focused on a fascinating research line of obfuscating programs. Loosely speaking, program obfuscation is to look for a way to write programs in an incomprehensible way, while still preserving the functionalities of the programs. Any adversary can only use the functionalities of the original programs, but cannot learn anything more than this, i.e. cannot reverse-engineering nor understand them. In this talk, I will first demonstrate the idea in defining the notion of program obfuscation and present some different but related definitions for it. Then I will outline the incredible applications of obfuscation in cryptography (if there are). Lastly, I will survey some known positive and negative results in this area.

Title: On the Distributed Evaluation of Logical Properties of Graphs
Speaker: Prof. Stéphane Grumbach (INRIA-LIAMA)
Time: 10:30am, Friday May 14
Place: Room 3-318
Abstract: Programming networks is a tedious task. High level abstractions have been proposed to facilitate programming and increase its reliability. In this talk I will consider the use of logical formalisms to express properties of graphs which form the topology of communication networks. A node can for instance fire a logical query to obtain a route to some other node, or construct a spanning tree. We consider first order logic and monadic second order logic, which has been widely studied for its nice expressive power over graphs, and show that both these logics admit rather efficient and scalable distributed evaluation over some classes of bounded tree width graphs, with a bounded number of messages sent through each link of the network during the computation.
Our results follow from fundamental properties of these logics, including the locality of first-order logic, and the linear time bound on their evaluation over classes of bounded tree width graphs.

Title: Duality and Computational Models
Speaker: Prabhu Manyem (Shanghai University)
Time: 1:00pm, Friday May 14
Place: Room 3-318
Abstract: In this talk, we will show a method by which optimization problems can be solved by a single call to a "decision" Turing machine, as opposed to multiple calls using a classical binary search setting. We will use concepts from optimization duality and descriptive complexity (which is based on second order Logic).

Title: The existence of optimal algorithms for TAUT and its consequences
Speaker: Dr. Yijia Chen (SJTU)
Time: 1:00pm, Wednesday May 5
Place: Room 3-318
Abstract: In this talk, I will explain what the optimal algorithms for TAUT are and their connections to descriptive complexity and parameterized complexity. In particular I will show that TAUT has an almost optimal algorithm if and only if a logic introduced by Blass and Gurevich captures PTIME.
Moreover, I will discuss some preliminary results relating the optimal algorithms to cryptography and set theory.
This is joint work with Joerg Flum and Moritz Mueller.