Home
Mission
Directions to CSI
Documentation
and Help
Facilities
HPC Systems
Research
Software
Training and Tutorials
User Accounts
Register for a Workshop
PREVIOUS WORKSHOPS
Data Intensive Computing
Advanced Computational Methods
Accelerators in High Performance Computing and Computational Science
UPCOMING WORKSHOPS
The CUNY HPCC is
operated by
the College of
Staten Island
and funded, in part, by
grants
from the City of
New York, State
of New
York, CUNY Research
Foundation, and National
Science Foundation
Grants CNS0958379,
CNS0855217 and
ACI 1126113

UPCOMING WORKSHOPS
Seminar on Machine Learning and Graphs, by Dr. Krzysztof Choromanski, Google Research Laboratory, New York, NY
Dr. Krzysztof Choromanski, Google Research Laboratory with give a seminar titled:
"The ErdosHajnal Conjecture and Combinatorial Clustering with Forbidden Patterns"
RESCHEDULED FOR: 2:30 PM on Tuesday, March 31, 2015, Lecture Hall, Building 1P, College of Staten Island.
This seminar is open to all CUNY faculty and students.
Abstract:
The celebrated ErdosHajnal Conjecture is one of the most important open problems in modern Ramsey graph theory. In its undirected version it states that for every undirected graph H there exists ϵ(H)>0 such that every Hfree nvertex graph contains a clique or a stable set of order at least n^ϵ(H). In the equivalent directed version undirected graphs are replaced by tournaments and cliques/stable sets by transitive subtournaments. Thus the Conjecture predicts that (quite surprisingly) a strictly local property of not having a forbidden pattern implies a global property of containing a large wellorganized substructure. In a truly random graph the largest clique/stable set/transitive set is of only logarithmic size. The Conjecture says that the nonrandomness of graphs defined by forbidden patterns can be measured by the polynomial size of the induced clique/stable set in the undirected setting or transitive subtournament in the directed setting. In this talk I will describe the most recent results regarding the Conjecture. Furthermore I will show an intriguing connection between the Conjecture and the clustering problem. It turns out that the algorithmic tools used in the most recent proofs regarding special variants of the Conjecture can be very helpful to obtain goodquality graph clustering in both undirected and directed setting. They also help to identify communities in the social network graphs.
Short bio:
Krzysztof Choromanski is a member of Google Research Group in New York. He works in different areas of machine learning and graph theory. Among his interests are: online nonparametric clustering, ranking algorithms, structural graph theory of networks defined by forbidden induced subgraphs, random graph theory, differential privacy. He was the first to prove the ErdosHajnal Conjecture for all tournaments on at most five vertices and to use the probabilistic method to give the best known upper bounds on the socalled ErdosHajnal coefficients of prime graphs. He was a member of the team of researchers who gave a complete characteristic of the tournaments satisfying the Conjecture in the strongest  linear sense. Together with Maria Chudnovsky and Paul Seymour he gave a complete structural theorem of tournaments satisfying the Conjecture in the pseudolinear sense and, as a consequence, proved that tournaments with this weird property exist. Krzysztof did his Ph.D in 2013 at Columbia University under the supervision of Professor Maria Chudnovsky (his Ph.D thesis was about the structural properties of graphs defined by forbidden patterns). He plays piano and is an avid salsa dancer.
After the seminar, Dr. Choromanski will give a short piano recital.
https://www.youtube.com/watch?v=Pvbhh2VBiys&spfreload=10 
