Random Walks 2008
Ben-Gurion University
Discussing and Exploring Random Walks


Abstracts and Bios


The Cover Time of Random Walks
Uriel Feige, Weizmann

Abstract:
The cover time of a random walk on a finite graph is the expected number of steps taken until all vertices are visited. This talk will survey some of the known bounds on the cover time and some of the techniques that are used in order to establish these bounds. The techniques include connections with electrical resistance, the use of minimum weight spanning trees, and the use of probabilistic arguments. The known bounds refer to the maximum and minimum possible cover time on general graphs (expressed as a function of the number of vertices in the graph), as well as on special families of graphs such as trees and regular graphs. The question of designing an efficient deterministic algorithm that on any given graph produces an accurate estimate of the cover time is still open.

Bio:
Uriel Feige is a Professor in the Department of Computer Science and Applied Mathematics at the Weizmann Institute, recently returning to Weizmann after spending three years in Microsoft Research. His main research interest is that of coping with NP-hard problems, including design of approximation algorithms, proving hardness of approximation results, and rigorous analysis of heuristics. For work in these areas he received (jointly with others) the Godel Prize in 2001 and the SIAM Outstanding Paper Prize in 2005.


Random Walk Methods in Search Engine Measurements
Ziv Bar-Yossef, Technion

Abstract:
Can we use the public user interface of a search engine to estimate the number of pages in its internal index? Can we measure externally the freshness of the documents cached by a search engine? Solutions to questions of this sort are important for the development of objective and reliable benchmarks for search engines.
The vast size of the data indexed by modern search engines together with the restricted access to the data make the above measurement tasks very difficult. In this talk I will survey several recent algorithms that exploit random walks on appropriately defined graphs to perform reliable and efficient search engine measurements. These algorithms rely on Monte Carlo statistical simulation techniques, like Importance Sampling and the Metropolis-Hastings algorithm.
Joint work with Maxim Gurevich (Technion)

Bio:
Ziv Bar-Yossef is a research scientist at Google Haifa and a faculty member (on leave) at the Technion's Department of Electrical Engineering. Ziv holds BSc (Computer Science and Mathematics) and MSc (Computer Science) from the Hebrew University and PhD (Computer Science) from the University of California at Berkeley. Prior to joining the Technion, Ziv was a research staff member at the IBM Almaden Research Center. Ziv's research interests are in web search and data mining, database, and theoretical computer science. Ziv is a co-recipient of the 2006 WWW Best Paper Award. He is serving on the steering committee of the ACM Conference on Web Search and Data Mining (WSDM).


Eigenvectors of Random Graphs and What They Tell Us
Nati Linial, Hebrew University of Jerusalem

Abstract:
Eigenvalues of random graphs have received considerable attention in recent years. We currently know quite a lot about the extremal properties of eigenvalues as well as about their typical behavior. Much of the interest in eigenvalues of graphs stems from their important role in the theory of expander graphs. Not so much is known, though, about the corresponding eigenfunctions. Extremal problems as well as the study of the typical behavior of eigenfunctions are of considerable theoretical and practical interest. In this talk I will present some recent results found jointly with Y. Dekel and J. Lee concerning the nodal regions of eigenfunctions in random graphs. I will also mention some of the interesting open problems that come up in this fascinating area of research.

Bio:
Prof Nati Linial completed his undergraduate studies in Mathematics at the Technion, PhD in Mathematics from the Hebrew University 1978, with Micha Perles in the field of graph theory. Today, in the School of Computer Science and Engineering at The Hebrew University of Jerusalem, he works mostly at the boundary between Mathematics and Computer Science. Prof Linial gets the most excitement in research when he manages to introduce deep mathematical ideas into Computer Science, for example tools of harmonic analysis to analyze Boolean functions, methods from Banach Space theory and metric spaces. Ideas from these fields have been used to develop new approximation algorithms and new approaches to the analysis of large data sets. Under his more applied hat, he also work in bioinformatics.


On Non-Backtracking Random Walks
Sasha Sodin, Tel-Aviv University

Abstract:
We will discuss the non-backtracking random walk on a d-regular graph, in particular, its spectral analysis and the maximal number of visits to a vertex. The results indicate that the non-backtracking walk may behave better than the usual one in problems related to reduction of randomness.
Joint work with Noga Alon (TAU), Itai Benjamini (Weizmann), and Eyal Lubetzky (TAU)

Bio:
Sasha Sodin is a PhD student at Tel-Aviv University where he completed his MSc in 2005. Sasha is currently working on Asymptotic Geometric Analysis and related topics under the supervision of Prof. Vitali Milman.


Pseudorandom Walks: Looking Random in the Long Run or All the Way
Omer Reingold, Weizmann

Abstract:
TBA

Bio:
Omer Reingold is a professor of Computer Science at the Weizmann Institute of Science. His research is mainly in Computational Complexity and Foundations of Cryptography. Omer completed his undergraduate studies in Tel-Aviv University and got his PhD at the Weizmann Institute. During the years 1999-2004, he was a member of AT&T Labs, and a visiting member of the Institute for Advanced Study at Princeton.


How to Explore a Fast-Changing World
Chen Avin, Ben-Gurion University

Abstract:
Motivated by real world networks and use of algorithms based on random walks on these networks we study the simple random walks on dynamic undirected graphs, i.e., graphs which are modified by inserting or deleting edges at every step of the walk. We are interested in the expected time needed to visit all the vertices of such a dynamic graph, the cover time, under the assumption that the graph is being modified by an oblivious adversary. It is well known that on static undirected graphs the cover time is polynomial in the size of the graph, on the contrary and somewhat counter-intuitively, we show that there are adversary strategies which force the expected cover time of dynamic graphs to be exponential, and relate this result to the cover time of static directed graphs. In addition we provide a simple strategy, the lazy random walk, that guarantees polynomial cover time regardless of the changes made by the adversary.
Joint work with Zvi Lotker (BGU) and Michal Koucky (Academy of Sciences of Czech Republic).

Bio:
Dr Chen Avin received the B.Sc. degree in Communication Systems Engineering from Ben-Gurion University, Israel, in 2000. He received the M.S. and Ph.D. degrees in Computer Science from the University of California, Los Angeles (UCLA) in 2003 and 2006 respectively. He is a Lecturer in the Department of Communication Systems Engineering at the Ben-Gurion University since October 2006. His current research interests are: Graphs and Networks Algorithms, Sensor Networks, Random Graphs, Complex Systems and Random Walks.


Spanners: Distributed Spanning Expanders
Nir Tzachar, Ben-Gurion University

Abstract:
We consider self-stabilizing and self-organizing distributed construction of a spanner that forms an expander. Namely, our constructions are extremely local, robust and dynamic, including a distributed local algorithm which reduces the number of edges of a given expander by any constant fraction. Furthuremore, as our algorithm is porbabilistic, we provide a distributed algorithm based on random walks to validate and monitor the resulting construction.
Joint work with Shlomi Dolev (BGU).

Bio:
Nir Tzachar is a PhD student at Ben-Gurion University. Nir's research interests lie in the fields of distributed computing, self-stabilization and designing local solutions to distributed problems—namely, provide self-organizing algorithms. Nir is also fascinated by the connection between probability theory and distributed applications.

March 26, 2008