Dear all, The talk below is cancelled. Sorry for the inconvenient. Regards, Fabrizio ---------- Forwarded message ---------- From: Fabrizio Grandoni <fabrizio(a)idsia.ch&gt; Date: Wed, May 2, 2018 at 12:54 PM Subject: Fwd: PIDSIA Seminar by Przemyslaw Uznanski To: IDSIA Talks <talks(a)idsia.ch&gt; Speaker: Przemyslaw Uznanski, ETH Zurich Title: A Framework for Searching in Graphs in the Presence of Errors Abstract: We consider two types of searching models, where the goal is to design an adaptive algorithm that locates an unknown vertex in a graph by repeatedly performing queries. In the vertex-query model, each query points to a vertex v and the response either admits that v is the target or provides a neighbor of von a shortest path from v to the target. This model has been introduced for trees by Onak and Parys [FOCS 2006] and by Emamjomeh-Zadeh et al. [STOC 2016] for arbitrary graphs. In the edge-query model, each query chooses an edge and the response reveals which endpoint of the edge is closer to the target, breaking ties arbitrarily. Our goal is to analyze solutions to these problems assuming that some responses may be erroneous. We develop a scheme for tackling such noisy models with the following line of arguments: For each of the two models, we analyze a generic strategy that assumes a fixed number of lies and give a precise bound for its length via an amortized analysis. From this, we derive bounds for both a linearly bounded error rate, where the number of errors in T queries is bounded by r*T for some r<1/2, and a probabilistic model in which each response is incorrect with some probability p<1/2. The bounds for adversarial case turn out to be strong enough for non-adversarial scenarios as well. We obtain thus a much simpler strategy performing fewer vertex-queries than one by Emamjomeh-Zadeh et al. For edge-queries, not studied before for general graphs, we obtain bounds that are tight up to logΔ factors in all error models. Applying our graph-theoretic results to the setting of edge-queries for paths, we obtain a number of improvements over existing bounds for searching in a sorted array in the presence of errors, including an exponential improvement for the prefix-bounded model in unbounded domains. Bio: Przemyslaw Uznanski received a PhD from INRIA Bordeaux in 2013. He is a postdoc at ETH Zurich since 2015. He works on distributed computing, biological algorithms, graph algorithms and text processing (with emphasis on algebraic methods in algorithms). When: Friday 11th of May 2018, 12:00-13:00 Location: Manno, Galleria 1, 2nd floor, room G1-204 Registration: Pizza (or alternative food) and drinks will be offered at the end of the talk. If you plan to attend, please register in a timely fashion at the following link so that we will have no shortage of food: https://doodle.com/poll/cvwfze59xayg2rkk