Computer Science семинар (осень 2010)

Общая информация
Семестросень 2010
Дата начала22.08.2010
Количество пар7
Язык курсарусский
Лекции Подсказка: слайды, видеозапись и другие материалы лекции доступны со страницы лекции, попасть на которую можно, нажав на её название.

1. Model Fitting and Fast Energy Minimization with Label Cost (Ю. Бойков, The University of Western Ontario)
(22.08.2010 - 11:15 - 12:50)

Model Fitting and Fast Energy Minimization with Label Cost Abstract: The $ \alpha $-expansion algorithm has had a significant impact in computer vision due to its generality, effectiveness, and speed. Thus far it can only minimize energies that involve unary, pairwise, and specialized higher-order terms. We show how to extend α-expansion so that it can simultaneously optimize "label costs" as well. An energy with label costs can penalize a solution based on the set of labels that appear in it. The simplest special case is to penalize the number of labels in the solution. Our energy is quite general, and we prove optimality bounds for our algorithm. A natural application of label costs is multi-model fitting, which we discuss in detail. We demonstrate many applications in vision: homography detection, motion segmentation, and unsupervised image segmentation. Our C++/MATLAB implementation is publicly available.
2. Approximate Scene Geometry From a Single View through Learning and Optimization (О. Векслер, The University of Western Ontario)
(22.08.2010 - 12:50 - 13:50)

In the last decade, graph-cut optimization has been popular for a variety of pixel labeling problems. Typically graph-cut methods are used to incorporate a smoothness prior on a labeling. Recently several methods incorporated ordering constraints on labels for the application of object segmentation. An example of an ordering constraint is prohibiting a pixel with a "car wheel" label to be above a pixel with a "car roof" label. We observe that the commonly used graph-cut based expansion is more likely to get stuck in a local minimum when ordering constraints are used. For certain models with ordering constraints, we develop new graph-cut moves which we call order-preserving moves. Order-preserving moves act on all labels, unlike expansion. Although the global minimum is still not guaranteed, optimization with order-preserving moves performs significantly better than expansion. We evaluate orderpreserving moves for the geometric class scene labeling (introduced by Hoiem et al.) where the goal is to assign each pixel a label such as "sky", "ground", etc., so ordering constraints arise naturally. In addition, we use orderpreserving moves for certain simple shape priors in graphcut segmentation, which is a novel contribution in itself.
3. SAT and Satisfiability Modulo Theories (R. Bruttomesso, University of Lugano)
(18.09.2010 - 17:20 - 18:55)

Satisfiability Modulo Theories (SMT) is the problem of deciding a quantifier-free formula modulo a background theory T. State-of-the-art SMT-Solvers are based on the DPLL(T) model, which efficiently combines a DPLL SAT-Solver, used to handle "disjucntive" choices, and a Theory Solver, a decision procedure for T, used to solve "conjunctions" of constraints. In this lecture we review the DPLL approach to SAT and extend it to DPLL(T) approach. Also we examine some useful theories, commonly used in the formal analysis of software, by sketching the main ideas behind the algorithms used to solve them.
4. OpenSMT (R. Bruttomesso, University of Lugano)
(18.09.2010 - 19:05 - 20:40)

In this lecture we describe OpenSMT, an incremental, efficient, extensible and open-source SMT-Solver. OpenSMT has been specifically designed to be easily extended with new theory-solvers, in order to be accessible for non-experts for the development of customized algorithms. We sketch the solver's architecture and interface, and we discuss its distinguishing features w.r.t. state-of-the-art SMT-Solvers.
5. Математическая модель социальных взаимодействий (А. Савватеев, ЦЭМИ РАН)
(24.10.2010 - 11:15 - 12:50)
6. Genome Rearrangements: from Biological Problems to Combinatorial Algorithms (Pavel Pevzner, University of California at San Diego, USA)
(09.12.2010 - 18:30 - 20:55)

Recent breakthroughs in the next-generation DNA sequencing fueled the genomics studies and revealed that some classical biological theories may be incomplete or even incorrect. I describe three controversial and hotly debated topics: Whole Genome Duplications, Random Breakage Model of Chromosome Evolution, and Mammalian Evolution, and three related challenging algorithmic problems: Genome Halving Problem, Breakpoint Re-Use Problem, and Ancestral Genome Reconstruction Problem. I further describe the "Multi-Break Rearrangements" framework that simplified analysis of these biological problems, led to efficient algorithmic solutions, and provided new evolutionary insights.

Second part of the presentation:
7. Two-Party Differential Privacy and Deterministic Extraction from Santha-Vazirani Sources (Г. Ярославцев, Pennsylvania State University)
(19.12.2010 - 17:20 - 18:55)

The talk presents recent results (from a paper at FOCS 2010) on "differential privacy" in a distributed setting: two parties holding sensitive data would like to analyze the union of their data sets while preserving the privacy of the individuals whose data they hold.

The paper gives almost tight bounds on the accuracy of such analysis for the Hamming distance function. These bounds show the contrast between information theoretic and computational differential privacy in the two-party setting and also between the two-party and the client-server setting. The proof technique introduces a connection between differential privacy and deterministic extraction from independent Santha-Vazirani sources.

The talk is mostly based on the paper "The Limits of Two-Party Differential Privacy" by Andrew McGregor, Ilya Mironov, Toniann Pitassi, Omer Reingold, Kunal Talwar and Salil Vadhan (

Basic background knowledge of information theory and probability theory can be useful.
Ваша оценка: Пусто Средняя: 4 (4 голосов)
Share |
Лекция Павла Певзнера
Павел Певзнер
Алексей Владимирович Савватеев
Алексей Владимирович Савватеев
Павел Певзнер