Seminars

View all Seminars  |  Download ICal for this event

On the smallest antichain that generates an ideal of given size

Series: CSA Faculty Colloquium

Speaker: Sunil Chandran L,Professor, Computer Science and Automation Department,Indian Institute of Science,Bangalore- 560012,India.

Date/Time: Jun 07 16:00:00

Location: CSA Lecture Hall (Room No. 112, Ground Floor)

Abstract:
Ideals (also known as downsets or monotone decreasing families or abstract simplicial complexes) are fundamental objects which are central to the study of set systems and have been very well studied. Let the smallest antichain, which generates an ideal of size $n$ be $alpha(n)$. While a $log{n}$ upper bound is easy, no non-trivial improvement for this bound is known in spite of its importance in computer science. In this work, we give a constructive proof that,
<br>
begin{itemize}
<br> item for every $ngeq 3$, $alpha(n)leq 20sqrt{log{n}}loglog{n}$ <br>
item there exists infinitely many $nin mathbb{N}$ for which $ alpha(n)geq log_{2}(lceil 0.5log_{2}n rceil))$. <br>
end{itemize}<br>
<br>
<br>
Our results have surprising and immediate implications to the area of model counting. More specifically, our constructions improve the state-of-the-art techniques for weighted model counting, which have applications in probabilistic reasoning, network reliability estimation, statistical physics, program synthesis and system verification.

Speaker Bio:
Dr. L. Sunil Chandran is a professor in the department of Computer Science and Automation in Indian Institute of Science, Bangalore. He received his Ph.D from Indian Institute of Science, Bangalore and was a post doctoral fellow in Max-Planck Institute for Informatik, Saarbruecken, Germany. His area of research is graph theory, combinatorics and graph algorithms. He is a fellow of Indian National Science Academy (INSA) and Indian National Academy of Engineering (INAE)

Host Faculty: Prof. Sathish Govindarajan