© 2001-2018 Московский физико-технический институт
(государственный университет)
Workshop on graphs, networks, and their applications, May 14 - 16, Moscow, 2018
The workshop will take place at the Moscow Institute of Physics and Technology from the 14th till the 16th of May 2018.
The aim of the workshop is to bring together specialists in graph theory, complex networks, random graphs and models. The Moscow Institute of Physics and Technology and, in particular, the Phystech-School of Applied Mathematics and Computer Science, will become a platform for the discussion of various subjects in the area including real industrial applications. Among the industrial partners of the workshop, Microsoft Research, Yandex, Sberbank, Huawei.
Key-note speakers include:
- Jennifer Chayes (Microsoft Research)
- Christian Borgs (Microsoft Research)
- Alexander Kostochka (University of Illinois at Urbana-Champaign)
- Ravi Kumar (Google) tentatively
- Michael Krivelevich (Tel Aviv University)
- Benjamin Sudakov (ETH, Swiss)
- Andrzej Dudek (Western Michigan University)
- Jozsef Balogh (University of Illinois at Urbana-Champaign)
- Nelly Litvak (Twente University)
- Bogumil Kaminski (Warsaw School of Economics)
- Pawel Pralat (Ryerson University)
- Panos Pardalos (University of Florida, Higher School of Economics)
Organizing Committee:
-
Andrei M. Raigorodskii (MIPT, Yandex, Russia)
-
Jennifer Chayes (Microsoft Research, USA)
-
Christian Borgs (Microsoft Research, USA)
-
Mikhail Bilenko (Yandex, Russia)
-
Liudmila Prokhorenkova (MIPT, Yandex, Russia)
-
Gleb Gusev (MIPT, Yandex, Russia)
-
Pawel Prałat (Ryerson University, Fields Institute, Canada)
Registration
Abstracts
A number of contributed talks will be hosted by the workshop. Please register and tell us whether you want to speak and/or publish an abstract. The deadline for abstract submission is 15.03.2018. A decision will be made by 15.03.2018 for those who have registered by 20.02.2018 and by 31.03.2018 for the others.
Please note that if you need a visa and even do not suppose to give a talk, you should register as soon as possible. Of course in most cases, there will be enough time, even if you register in the beginning of April. However, in some cases, Russian authorities may spend up to one month to issue an invitation letter. Then it will take a week to deliver it (we will do it by DHL, but let's be careful as well). Finally, it will take a week for your embassy of Russia to issue your visa. So you should plan accurately your time. Please also note that it is better to book in advance a day of your visit to your embassy of Russia. Anyway we will do our best to help you, so feel free to contact us and ask any questions! We are looking forward to meeting you in Russia.
We are planning to have on Tuesday an afternoon "industrial session", wh ere we will invite both our speakers and our industrial partners to discuss together possible collaborations.
Schedule:
Monday, May 14, 2018 (Biopharmaceutical cluster №107)
Plenary talk
09:00 - 09:50 - Christian Borgs "Unbounded Graphons as Limits of Sparse Graphs"
10:00 - 10:50 - Jennifer Chayes "Graphons for Modeling and Estimating Sparse Graphs"
11:00 - 11:30 - Coffee break
Contributed talks
11:30 - 11:50 - Ludmila Tsiovkina "Vertex-Transitive Antipodal Distance-Regular Graphs Of Diameter Three With A Primitive Almost Simple Antipodal Group"
Please note that if you need a visa and even do not suppose to give a talk, you should register as soon as possible. Of course in most cases, there will be enough time, even if you register in the beginning of April. However, in some cases, Russian authorities may spend up to one month to issue an invitation letter. Then it will take a week to deliver it (we will do it by DHL, but let's be careful as well). Finally, it will take a week for your embassy of Russia to issue your visa. So you should plan accurately your time. Please also note that it is better to book in advance a day of your visit to your embassy of Russia. Anyway we will do our best to help you, so feel free to contact us and ask any questions! We are looking forward to meeting you in Russia.
We are planning to have on Tuesday an afternoon "industrial session", wh ere we will invite both our speakers and our industrial partners to discuss together possible collaborations.
Schedule:
Monday, May 14, 2018 (Biopharmaceutical cluster №107)
Plenary talk
09:00 - 09:50 - Christian Borgs "Unbounded Graphons as Limits of Sparse Graphs"
10:00 - 10:50 - Jennifer Chayes "Graphons for Modeling and Estimating Sparse Graphs"
11:00 - 11:30 - Coffee break
Contributed talks
11:30 - 11:50 - Ludmila Tsiovkina "Vertex-Transitive Antipodal Distance-Regular Graphs Of Diameter Three With A Primitive Almost Simple Antipodal Group"
11:55 - 12:15 - Danila Cherkashin "Coloring General Kneser Graphs Via High-Discrepancy Hypergraphs"
12:20 - 12:40 - Maksim Zhukovskii "Maximum Sets of Common Neighbors in the Binomial Random Graph"
12:45 - 13:05 - Matthew Bernard "Lim it Topology for Dimer Algebra Random R-Trees" Presentation
13:10 - 13:30 - Zilin Jiang "Largest Eigenvalues of Graphs, Local and Global"
13:30 - 15:00 - Lunch break
Plenary talk
15:00 - 15:50 - Pawel Pralat "K-regular Subgraphs Near the k-core Threshold of a Random Graph" Presentation
13:30 - 15:00 - Lunch break
Plenary talk
15:00 - 15:50 - Pawel Pralat "K-regular Subgraphs Near the k-core Threshold of a Random Graph" Presentation
16:00 - 16:50 - Benjamin Sudakov "Asymptotic in Bond Percolation on Expanders"
16:50 - 17:20 - Coffee break
Contributed talks
17:20 - 17:40 - Dmitri Taletskii "Two Results on Trees with Extremal Number of Independent Sets" Presentation
17:45 - 18:05 - Dmitry Sirotkin "A Way for Graph Reduction for the Independent Set Problem and Its Application" Presentation
18:10 - 18:30 - Dmitriy Malyshev "Boundary and Minimal Hard Classes for Algorithmic Graph Problems" Presentation
18:35 - 18:55 - Darina Dvinskikh "Stochastic Distributed Computation of Wasserstein Barycenter" Presentation
19:00 - 19:30 - Meruza Kubentayeva "Searching Stochastic Equilibria in Transport Networks by Universal Primal-dual Method" Presentation
19:30 - Welcome party
Tuesday, May 15, 2018 (Biopharmaceutical cluster №107)
Plenary talk
09:00 - 09:50 - Panos Pardalos "Cliques of Maximum and Minimum Centrality in Information and Social Networks" Presentation
10:00 - 10:50 - Nelly Litvak "Local Properties of PageRank and Graph Limits" Presentation
11:00 - 11:30 - Coffee break
Plenary talk
11:30 - 12:20 - Jozsef Balogh "On Further Application of The Container Method" Presentation
12:30 - 13:40 - Bogumil Kaminski "Parallel Execution of Schedules with Random Dependency Graph" Presentation
13:40 - 15:00 - Lunch break
Contributed talks
15:00 - 15:20 - Liudmila Prokhorenkova "Community Detection Through Likelihood Optimization: in Search of a Sound Model" Presentation
15:25 - 15:45 - Maxim Panov "Consistent Estimation of Mixed Memberships with Successive Projections" Presentation
15:50 - 16:10 - Mikhail Isaev "The Sandwich Conjecture of Random Regular Graphs and More" Presentation
16:15 - 16:35 - Anna Taranenko "Multidimensional Analogues of the Birkhoff and the König–Hall Theorems for Polyplexes" Presentation
16:35 - 17:00 - Coffee break
17:00 - Industrial session vs. free time / excursions
Liudmila Prokhorenkova (Yandex)
CatBoost: unbiased boosting with categorical features
Video
Presentation
I will discuss the key algorithmic techniques behind CatBoost, a state-of-the-art open-source gradient boosting toolkit. Their combination leads to CatBoost outperforming other publicly available boosting implementations in terms of quality on a variety of datasets. Two critical algorithmic advances introduced in CatBoost are the implementation of ordered boosting, a permutation-driven alternative to the classic algorithm, and an innovative algorithm for processing categorical features. Both techniques were created to fight a prediction shiftcaused by a special kind of target leakage present in all currently existing implementations of gradient boosting algorithms. In this paper, we provide a detailed analysis of this problem and demonstrate that proposed algorithms solve it effectively, leading to excellent empirical results.
Dmitry Shmelkin (Huawei)
Some graph optimization and cross-layer network challenges of Huawei carrier business
Video
20:00 - Conference dinner
Wednesday, May 16, 2018 (Biopharmaceutical cluster №107)
Plenary talk
09:00 - 09:50 - Andrzej Dudek "Minimizing the Number of 5-cycles in Graphs with Given Edge-Density" Presentation
16:35 - 17:00 - Coffee break
17:00 - Industrial session vs. free time / excursions
Liudmila Prokhorenkova (Yandex)
CatBoost: unbiased boosting with categorical features
Video
Presentation
I will discuss the key algorithmic techniques behind CatBoost, a state-of-the-art open-source gradient boosting toolkit. Their combination leads to CatBoost outperforming other publicly available boosting implementations in terms of quality on a variety of datasets. Two critical algorithmic advances introduced in CatBoost are the implementation of ordered boosting, a permutation-driven alternative to the classic algorithm, and an innovative algorithm for processing categorical features. Both techniques were created to fight a prediction shiftcaused by a special kind of target leakage present in all currently existing implementations of gradient boosting algorithms. In this paper, we provide a detailed analysis of this problem and demonstrate that proposed algorithms solve it effectively, leading to excellent empirical results.
Dmitry Shmelkin (Huawei)
Some graph optimization and cross-layer network challenges of Huawei carrier business
Video
In our report we mention just two topics of numerous Huawei research agenda. In the first, we will show that the Channel Decoder efficiency requires some graph search engine, which, in the case of even average modulation (QAM16 and above), leads to an unaffordable complexity. To reduce this complexity by a reliable algorithm is a challenge.
The second topic introduces the challenge of Wireless Network in serving the modern high performance applications, like Video-On-Demand services with high resolution. To make these services successful, a new SAND standard has been recently proposed. This standard establishes a safe communication between application, mobile device, and wireless network. Deployment of this standard will need a mutual understanding between IT companies, network operators, mobile device producers, and telecom equipment vendors like Huawei.
Ruslan Morozov (Sberbank)
Next Best Action model in Сorporate business
Video
Presentation
Building the Next Best Action system in the corporate business - features, artifacts and network business model.
Angelia Nedich
Recent trends in Distributed Optimization on Graphs
Video
Presentation
20:00 - Conference dinner
Wednesday, May 16, 2018 (Biopharmaceutical cluster №107)
Plenary talk
09:00 - 09:50 - Andrzej Dudek "Minimizing the Number of 5-cycles in Graphs with Given Edge-Density" Presentation
10:00 - 10:50 - Michael Krivelevich "Finding and Using Expanders in Locally Sparse Graphs" Presentation
11:00 - 11:30 - Coffee break
Contributed talks
11:30 - 11:50 - Przemyslaw Szufel "Decision Tree Analysis with SilverDecisions.pl" Presentation
11:55 - 12:15 - Nikita Polianskii "On the Metric Dimension of Cartesian Powers of a Graph" Presentation
12:20 - 12:40 - Andrey Leonidov "Static and Dynamic Equilibria in Binary Choice Games on Graphs" Presentation
12:45 - 13:05 - Oleg Prokopyev "Finding Critical Links for Closeness Centrality" Presentation
13:10 - 13:30 - Nikita Zhivotovskiy "Concentration of the Spectral Norm of Erdős-Rényi Random Graphs" Presentation
13:30 - 15:00 - Lunch break
Plenary talk
15:00 - 15:50 - Alexander Kostochka "Features of DP-coloring of Graphs and Multigraphs" Presentation
16:00 - 16:50 - Ravi Kumar "Random Walks and Network Properties" Presentation
16:50 - 17:20 - Coffee break
Contributed talks
17:20 - 17:40 - Alexander Veremyev "The Maximum Induced Path Problem: Integer Programming Techniques for Finding Exact Solutions" Presentation
16:50 - 17:20 - Coffee break
Contributed talks
17:20 - 17:40 - Alexander Veremyev "The Maximum Induced Path Problem: Integer Programming Techniques for Finding Exact Solutions" Presentation
17:45 - 18:05 - Wilhelmus van der Hoorn "Local Clustering in Random Hyperbolic Geometric Graphs" Presentation
18:10 - 18:30 - Dmitri Karpov "On the Reconstruction of Graphs of Connectivity 2" Presentation
18:35 - 18:55 - Clara Stegehuis "Optimal Subgraph Structures in Scale-Free Networks" Presentation
Accomodation
The workshop will be followed by the 15th Workshop on Algorithms and Models for the Web Graph and by The 8th International Conference on Network Analysis.
