- 27. PIS Prof. Monika Henzinger: Finding the global minimum cut: Flows beat PageRank
- LECTURE ANNOTATION:
In this talk we will survey the history and the state of the art of algorithms for finding minimum cuts in graphs, including some new developments. We will focus on global minimum cuts, which is the minimum of s-t cuts over all pairs of vertices s and t. It is well-known that the value of a minimum s-t cut in a graph equals the value of the maximum flow from s to t and the standard algorithm for computing a minimum s-t cut still uses a maximum flow computation. Using that approach, however, leads to a quite inefficient algorithm for computing the global minimum cut, requiring n flow computations, where n is the number of vertices of the graph.
Indeed until recently the fastest algorithm for global minimum cut in unweighted graphs was not based on flow computation but was using multiple PageRank computations in combination with various graph-theoretic arguments. We will explain how to replace the PageRank computation by a multi-source, multi-sink flow computation that results in the fastest known algorithm for global minimum cut in unweighted graphs. This is a joint work with Satish Rao and Di Wang.
Monika Henzinger is a full professor at the University of Vienna, Austria, heading the research group of Theory and Applications of Algorithms. She received her PhD in 1993 from Princeton University under the supervision of Robert Tarjan and then joined the Computer Science Department at Cornell University. Later she worked at the Systems Research Center of DEC, at Google as the Director of Research and at EPFL Lausanne, heading the Laboratory of Theory and Applications of Algorithms. In 2013 she was awarded a Dr.h.c. degree from the Technical University of Dortmund, Germany. Monika Henzinger is a fellow of the ACM and of the EATCS, she has received an ERC Advanced Grant, a European Young Investigator Award, an NSF CAREER Award, and a Top 25 Women on the Web Award. She has published over 100 scientific articles and is the co-inventor of over 80 patents.
ABOUT THE PRAGUE COMPUTER SCIENCE SEMINAR:
The seminar will take place on the 4th Thursday of each month at 4:00pm (except June, July, August and December) alternately in the buildings of Faculty of Electrical Engineering, Czech Technical University, Karlovo nám. 13, Praha 2 and Faculty of Mathematics and Physics, Charles University, Malostranské nám. 25, Praha 1.
Its program will consist of a one-hour lecture followed by a discussion. The lecture should be based on an (internationally) exceptional or remarkable achievement of the lecturer, presented in a way which is comprehensible and interesting to a broad computer science community. The lectures will be in English.
The seminar framework was laid out by the preparatory committee consisting of Michal Chytil (Czech Academy of Sciences, Computer Science Institute), Pavel Kordík (Czech Tech. Univ., Faculty of Information Technologies), Jan Kybic (Czech Tech. Univ., Faculty of Electrical Engineering), Michal Pěchouček Czech Tech. Univ., Faculty of Electrical Engineering), Jiří Sgall (Charles University, Faculty of Mathematics and Physics), Vojtěch Svátek (University of Economics, Faculty of Informatics and Statistics), Michal Šorel (Czech Academy of Sciences,Institute of Information Theory and Automation), and Filip Železný (Czech Tech. Univ., Faculty of Electrical Engineering)
The idea to organize this seminar emerged in discussions of the representatives of several research institutes on how to avoid the undesired fragmentation of the Czech computer science community.
- Film Club - Toni Erdmann
- Drama / Comedy
Germany / Austria / Romania, 2016, 162 min
Original version / Czech subtitles
Director: Maren Ade
Writer: Maren Ade
Cinematography: Patrick Orth
Stars: Peter Simonischek, Sandra Hüller, Lucy Russell,...
Winfried doesn't see much of his working daughter Ines. He pays her a surprise visit in Bucharest, where she's busy as a corporate strategist. The geographical change doesn't help them to see more eye to eye. Practical joker Winfried annoys his daughter with corny pranks and jabs at her routine lifestyle of meetings and paperwork. Father and daughter reach an impasse, and Winfried agrees to go home to Germany. Enter Toni Erdmann: Winfried's flashy alter ego. Disguised in a tacky suit, weird wig and fake teeth, Toni barges into Ines' work circle, claiming to be her CEO's life coach. As Toni, Winfried doesn't hold back, and Ines meets the challenge. The harder they push, the closer they become. In all the madness, Ines begins to see that her eccentric father deserves a place in her life.
- PhD Thesis defense (Ing. Dominik Štorek)
- PhD Thesis defense "Source Localization by Virtual Acoustic Reality: Differential Head-Related Transfer Function as a One-Channel Positioning Method", Ing. Dominik Štorek, field of study Acoustics, Ph.D. Programme Electrical Engineering and Information Technology.
- PhD Thesis defense (Ing. David Černý)
- PhD Thesis defense "Algorithms for Analysis of Nonlinear High-Frequency Circuits", Ing. David Černý, field of study Radioelectronics, Ph.D. Programme Electrical Engineering and Information Technology.
- Artificial Intelligence Goes All-In: Computers Playing Poker
- Lecture by prof. Michael Bowling, head of Computer Poker Research Group at University of Alberta.
Artificial intelligence has seen several breakthroughs in recent years, with games such as checkers, chess, and go often serving as milestones of progress. Poker is another game entirely, with players having their own asymmetric information about what's happening in the game. In this talk, I'll describe a decade long research program to build AI that can cope with the hallmarks of poker — deception, bluffing, and manipulating what other players know. This research has culminated in two landmark results: Cepheus playing a perfect game of limit poker, and most recently DeepStack (in a collaboration with Czech researchers) beating poker pros at the game of no-limit poker. These two computer programs take very different approaches, and shed light on what is required to play a game at an expert-level and what is required to play it perfectly.
About professor Michael Bowling:
-World-famous expert on AI and reinforcement learning
-Led many outstanding computer poker results:
-Polaris, beating pros in heads-up limit poker
-Cepheus, playing optimally heads-up limit poker
-DeepStack, beating pros in heads-up no-limit
-Two publications on poker in prestigious Science
-Proposed Atari games as a benchmark for AI
-Won one of the first RoboCup challenges
- PhD Thesis defense (Ing. Radoslav Sokol)
- PhD Thesis defense "Methods for balancing electricity generation from renewables on the electricity markets", Ing. Radoslav Sokol, field of study Business Management and Economics, Ph.D. Programme Electrical Engineering and Information Technology.
- Track on Middleware and Enterprise Application Software (MEAS)
- The objective of MEAS track is to provide researchers and software architects the opportunity to present their observations, experiences and research in the area of production-level enterprise applications. The aim of integrate academic research and industry level research, introduce the best practices, state of the art and mostly production level experience impacting the development, design, maintenance, scalability and other software quality attributes.
Paper submission due September 15, '16
Students can participate in Student Research Competition (SRC) http://www.sigapp.org/sac/sac2017/
03.04.2017 - 07.04.2017
- PhD Thesis defense (Mgr. Martin Blažek)
- PhD Thesis defense "Algorithms for Image Processing of Crowded Fields in Astronomy", Mgr. Martin Blažek, field of study Radioelectronics, Ph.D. Programme Electrical Engineering and Information Technology.
- PhD Thesis defense (Ing. Jiří Vecka)
- PhD Thesis defense "Modelling of impacts of CO2 auctions on the district heating sector", Ing. Jiří Vecka, field of study Business Management and Economics, Ph.D. Programme Electrical Engineering and Information Technology
- PhD Thesis defense (Ing. Jan Bartošek)
- PhD Thesis defense "Prosody Utilization in Continuous Speech Recognition", Ing. Jan Bartošek, field of study Electrical Engineering Theory, Ph.D. Programme Electrical Engineering and Information Technology.
- PhD Thesis defense (Ing. Michal Borský)
- PhD Thesis defense "Robust recognition of strongly distorted speech", Ing. Michal Borský,field of study Electrical Engineering Theory, Ph.D. Programme Electrical Engineering and Information Technology.
- PhD Thesis defense (Ing. Tomáš Lukeš)
- PhD Thesis defense "Super-resolution microscopy live cell imaging and image analysis", Ing. Tomáš Lukeš, field of study Radioelectronics, Ph.D. Programme Electrical Engineering and Information Technology.
- Eric Gruson: IP protection for Software
- Eric Gruson is SW IP expert of Cabinet Plasseraud European Patent & Trademark Attorneys
The lecture is going to provide an insight into the European and US patent practice to help understand possibilities of a proper IP protection around SW applications.