Directions to CSI

Documentation and Help


HPC Systems



Training and Tutorials

User Accounts



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 CNS-0958379,
CNS-0855217 and
ACI 1126113

NSF Logo


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 Erdos-Hajnal 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.


The celebrated Erdos-Hajnal 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 H-free n-vertex 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 well-organized substructure. In a truly random graph the largest clique/stable set/transitive set is of only logarithmic size. The Conjecture says that the non-randomness 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 good-quality 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 non-parametric 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 Erdos-Hajnal Conjecture for all tournaments on at most five vertices and to use the probabilistic method to give the best known upper bounds on the so-called Erdos-Hajnal 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.



Parallel Programming and Optimization with Intel® Xeon Phi™ Coprocessor

May 5 and May 6, 2015, 9:00AM to 4:30PM
The Graduate Center, 365 5th Avenue, New York, NY 10016

Intel Corp. is providing 2 separate one-day courses on parallel programming and optimization.

The first course, to be held on Tuesday, May 5th, is a one-day lecture on programming models for parallel computing (seating for 50 people). This course serves as an introduction to parallel programming as well as best practices for Intel’s multicore and many-core architectures and software development tools. The following topics will be covered:

- Intel Xeon Phi architecture and future technologies
- Programming models: native, offload, heterogeneous clustering
- Parallel frameworks: automatic verification, OpenMP, MPI
- Optimization methods: general, scalar math, vectorization, multithreading, memory access, communication and special topics.

The second course, to be held on Wednesday, May 6th, for advanced students, includes hands-on exercise course (limited to 16 attendees).

Separate registration is required for each day; seats are limited

To Register for Tuesday, May 5th lecture -------- New York City CDT 101: May 5

To Register for Wednesday, May 6th, hands-on exercise course -------- New York City CDT 102: May 6