Time: Tuesday, 7 January 2020, 11:30am
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building
Abstract:
Simulink/Stateflow® is the de-facto tool for design of Cyber-physical Systems (CPS). CPS include hybrid systems, where a discrete controller guides a continuous plant. Hybrid systems are characterised by their continuous time dynamics with sudden dis- continuities, caused by level/zero crossings. State ow can graphically capture hybrid phenomenon, making it popular with control engineers. However, State ow is unable to correctly and efficiently simulate complex hybrid systems, especially those characterised by even number of level crossings. In this work we first propose a new formal model for hybrid systems called Quantized State Hybrid Input Output Automaton (QSHIOA). QSHIOA is used to give a deterministic semantics to State ow in addition to efficiently handling even number of level crossing detections. In the proposed compositional semantics, a network of State ow charts can be compiled into a network of QSHIOAs. Benchmark results show that in the median case, the proposed stateflow execution technique, via QSHIOA, is 84% faster than using the best variable-step size solvers in Simulink/Stateflow®.
Speaker's Profile:
Avinash Malik is a Senior lecturer at the University of Auckland, New Zealand. His main research interest lies in programming language semantics, non-linear control, and biomedical systems. He has worked at organizations such as INRIA in France, Trinity College Dublin, IBM research Ireland, and IBM Watson on design and compilation of programming languages. He holds B.E. and PhD degrees, in Electrical Engineering, from the University of Auckland.
Organization:
University of Auckland
Host:
Prof. R. K. Shyamasundar
User:
Department Calendar
Time:
11:00am
Send Reminder:
Yes - 119 hours 30 minutes before start
Description:
Speaker: Prof. Anindya De
Time: Wednesday, 08 January 2020, 11:00am
Venue: Department of Computer Science and Engineering, Room No. 109, 01st Floor, New CSE/CC Building
Abstract:
A Boolean function f on the n-dimensional hypercube is said to be a k-junta if it is dependent only on some k coordinates of the input. These functions have been widely studied in the context of PCPs, learning theory and property testing. In particular, a flagship result in property testing is that k-juntas can be tested with \tilde{O}(k) queries -- i.e., there is an algorithm which when given a black box to f, makes only \tilde{O}(k) queries and decides between the following two cases:
1. f is a k-junta.
2. f is at least 0.01 far from every k-junta g in Hamming distance.
Surprisingly, the query complexity is completely independent of the ambient dimension n. In this work, we achieve the same qualitative guarantee for the noise tolerant version of this problem. In particular, we give a 2^k query algorithm to distinguish between the following two cases.
1. f is 0.48-close to some k-junta.
2. f is at least 0.49 far from every k-junta.
The algorithm and its proof of correctness are simple and modular employing some classical tools like “random restrictions” with elementary properties of the noise operator on the cube.
Joint work with Elchanan Mossel and Joe Neeman.
Speaker Profile:
Dr. Anindya De is an Assistant Professor in the Dept. of Computer and Information Science at University of Pennsylvania. More details about him are available at https://www.seas.upenn.edu/~anindyad/.
Organization:
University of Pennsylvania
Host:
Prof. Nutan Limaye
User:
Department Calendar
Time:
2:00pm
Send Reminder:
Yes - 182 hours 51 minutes before start
Description:
Speaker: Kiran Shiragur
Time: Wednesday, 08 January 2020, 2:00pm
Venue: CC 109
Abstract:
Symmetric properties of distributions arise in multiple settings. For each of these, separate estimators and analysis techniques have been developed. Recently, Orlitsky et al showed that a single estimator that maximizes profile maximum likelihood (PML) is sample competitive for all symmetric properties. Further, they showed that even a 2^{n^{1-delta}}-approximate maximizer of the PML objective can serve as such a universal plug-in estimator. (Here n is the size of the sample). Unfortunately, no polynomial time computable PML estimator with such an approximation guarantee was known. We provide the first such estimator and show how to compute it in time nearly linear in n. The PML objective is related to the permanent of a certain Vandermonde matrix. A surprising connection between the convex relaxation we introduce and the Bethe free energy approximation originating in statistical physics leads to new bounds on the Bethe permanent of non-negative matrices.
This is in joint work with Moses Charikar and Aaron Sidford
Speaker Profile:
Kiran Shiragur is a PhD student at Stanford university. His area of research is operations research and theoretical computer science.