### Chris Schwiegelshohn: On the Local Structure of Stable Clustering Instances

As an optimization problem, clustering exhibits a striking
phenomenon: It is generally regarded as easy in practice, while theory
classifies it among the computationally intractable problems. To address
this dichotomy, research has identified a number of conditions a data set
must satisfy for a clustering to be (1) easily computable and (2)
meaningful.
In this talk we show that all previously proposed notions of struturedness
of a data set are fundamentally local properties, i.e. the global optimum
is in well defined sense close to a local optimum. As a corollary, this
implies that the Local Search heuristic has strong performance guarantees
for both the tasks of recovering the underlying optimal clustering and
obtaining a clustering of small cost.*Room 222 - Galleria 1 @12:00*

### Silvio Lattanzi: Consistent k-Clustering

The study of online algorithms and competitive analysis provide a
solid foundation for studying the quality of irrevocable decision
making when the data arrives in an online manner. While in some
scenarios the decisions are indeed irrevocable, there are many
practical situations when changing a previous decision is not
impossible, but simply expensive.
In this work we formalize this notion and introduce the consistent
k-clustering problem. With points arriving online, the goal is to
maintain a constant approximate solution, while minimizing the number
of reclusterings necessary. We prove a lower bound, showing that Ω(k
log n) changes are necessary in the worst case, for a wide range of
objective functions. On the positive side, we give an algorithm that
needs only O(k^2 log^4 n) changes to maintain a constant competitive
solution. This is an exponential improvement on the naive solution of
reclustering at every time step. Finally, we show experimentally that
our approach performs much better than the theoretical bound, with the
number of changes growing approximately as O(log n).
Joint work with Sergei Vassilvitskii.*Manno, Galleria 1, 2nd floor, room G1-204 @12:00 *

### Manuela Fischer: The Locality of Maximal Matching

Many systems in the world are vast networks consisting of autonomous
nodes that communicate with each other in order to jointly solve a
task. One common feature of these complex networks is that due to
their size it is impossible for an individual node to have a global
view. Instead, nodes have to base their decisions on local information
about nearby nodes only. Despite this intrinsic locality, the network
as a whole is supposed to arrive at a global solution. Understanding
capabilities and limitations of such local algorithms is the key
challenge of distributed graph algorithms. The LOCAL model---the
standard synchronous message-passing model of distributed computing
introduced by Linial in 1987---is designed to abstract the pure
concept of locality.
In this talk, we discuss the maximal matching problem in the LOCAL
model. In particular, we introduce a new rounding technique that leads
to a deterministic O(log^2 Delta log n)-round algorithm on any n-node
graph with maximum degree Delta. This is the first improvement in
almost 20 years over the celebrated O(log^4 n)-round algorithm by
Hanckowiak, Karonski, and Panconesi.*Galleria 1 - 2nd floor, room G1-204*

### PIDSIA Seminar by Cristina Rottondi: Future Optical Network Design And Management Assisted by Machine Learning

Recently, machine learning methods have started to enter the field of photonics, ranging from quantum mechanics, nanophotonics, optical communication and optical networks.
Though machine learning offers many powerful techniques, linking it to optical communication may not be trivial, due to the inherent peculiarities of optical technologies.
In this talk, we will discuss open challenges and benefits that machine learning methods can bring to optical communications, especially in the field of optical networks design and management.*Galleria 1, 2nd floor, room G1-204*

### PIDSIA Seminar by Mauro Scanagatta: Advancements in Bayesian network structure learning

A Bayesian network (BN) is a versatile and well-known probabilistic graphical model with applications in a variety of fields.
Their graphical nature makes BNs excellent models for representing the complex probabilistic relationships existing in many real problems ranging from bioinformatics to law, from image processing to economic risk analysis.
In this talk, we will present the difficult task of learning their dependency graph, also known as their structure, from data. *Manno, Galleria 1, 2nd floor, room G1-204 @12:00 *

### Corrado Monti: Semantic networks: applications and modelling

Semantic networks are one of the most valuable tools in today's NLP. They power the intelligence behind conversational interfaces, help search engines answer queries, and are one the most used ways to represent the knowledge present in natural language. In this talk, I will present some of my work related to them.
Firstly, we will see an example of a simple use case for semantic networks within opinion mining. I will show how we used them to build a model able to detect political disaffection in Twitter messages in Italian language. Semantic networks here helped, e.g., in distinguishing general political disaffection from a sentiment against a specific political party. We applied this model to 35 millions tweets, and – in order to validate the quality of the generated time-series – we compared our results to opinion surveys.
Secondly, I will illustrate a theoretical model for semantic networks. In a semantic network, each node is usually tagged with different categories. How does the presence or absence of such categories interplay with the network link structure? I will present a model that is able to describe complex interactions between categories and links, while at the same time being simple enough to derive scalable algorithms. Finally, I will show a practical application for this model on semantic networks, presenting an algorithm to mine surprising links.*Manno, Galleria 1, room G1-204 *

### Danupon Nanongkai: Distributed Shortest Paths, Exactly

This talk concerns the problem of quickly computing distances and
shortest paths on distributed networks (the CONGEST model). There have
been many developments for this problem in the last few years,
resulting in tight approximation schemes. This left widely open
whether exact algorithms can perform equally well. In this talk, we
will discuss some recent progress in answering this question. The talk
will focus on surveying the state of the art, and will discuss some
recent algorithms in details as time permits.
Based on joint work with Chien-Chung Huang and Thatchaphol Saranurak
(FOCS 2017) and with Sebastian Krinninger (work in progress).*Manno, Galleria 1, 2nd floor, room G1-204 @12:00 *

### Matteo Macchini: Intuitive Control Interfaces for Mobile Robots based on Body Motion

This talk will present the current state and the proposed next efforts in the field of natural human-robot interfaces for mobile robotic systems based on body motion. The intuitive mapping system is data-driven from the user's body motion when they are asked to naturally move as they were in control of the machine performing a predefined set of manoeuvres . Previous studies demonstrated that this kind of interface presents a steeper learning curve in terms of teleoperation performance with respect to a classic remote controller. Further developments of the interface will consist in a personalised mapping, adapted ad-hoc on the user, the introduction of a machine learning-based nonlinear regressor to increase the decoding power of the gestural interface, an online adaptation paradigm and a shared control system finalised to the optimisation of estimated trajectories.*IDSIA Meeting Room - Galleria 1 - 11:00 am*

### Vani K: Idea plagiarism detection using syntax-semantic concept extractions

Plagiarism is increasingly becoming a major issue in the academic and educational domains. Automated and effective plagiarism detection systems are direly required to curtail this information breach, especially in tackling idea plagiarism. The proposed approach is aimed to detect such plagiarism cases, where the idea of a third party is adopted and presented intelligently so that at the surface level, plagiarism cannot be unmasked. The work aims to explore syntax-semantic concept extractions with genetic algorithm in detecting cases of idea plagiarism. The work mainly focuses on idea plagiarism where the source ideas are plagiarized and represented in a summarized form. Plagiarism detection is employed at both the document and passage levels by exploiting the document concepts at various structural levels. Initially, the idea embedded within the given source document is captured using sentence level concept extraction with genetic algorithm. Document level detection is facilitated with word-level concepts where syntactic information is extracted and the non-plagiarized documents are pruned. A combined similarity metric that utilizes the semantic level concept extraction is then employed for passage level detection. The proposed approach is tested on PAN 2014 plagiarism corpus for summary obfuscation data, which represents a challenging case of idea plagiarism. The results obtained are found to exhibit significant improvement over the compared systems and hence reflects the potency of the proposed syntax-semantic based concept extractions in detecting idea plagiarism.*IDSIA Meeting Room Galleria 1 @9:30*

### PIDSIA Seminar by Alessandro Facchini: Why logicians at IDSIA

In an attempt to explain what Logic (and a logic) is, in this talk, thorough a brief glimpse into the history of the concerned discipline (spanning from Chrysippus of Soli and Aristotle to Gödel and Turing, and beyond), I will provide an overview of some of its fundamental concepts and results underpinning the connections with researches at the Institute. In guise of conclusion, I will present ongoing works related to statistical relational languages and imprecise probabilities.*IDSIA, Room G1-204 - Galleria 1 - 12:00-13:00*