Select a calendar:
Filter July Events by Event Type:
SUNMONTUEWEDTHUFRISAT
Events for July 27, 2009
-
Meet USC: Admission Presentation, Campus Tour, & Engineering Talk
Mon, Jul 27, 2009
Viterbi School of Engineering Undergraduate Admission
Workshops & Infosessions
This half day program is designed for prospective freshmen and family members. Meet USC includes an information session on the University and the Admission process; a student led walking tour of campus and a meeting with us in the Viterbi School. Meet USC is designed to answer all of your questions about USC, the application process and financial aid.Reservations are required for Meet USC. This program occurs twice, once at 9:00 a.m. and again at 1:00 p.m. Please visit http://www.usc.edu/admission/undergraduate/visit/meet_usc.html to check availability and make an appointment. Be sure to list an Engineering major as your "intended major" on the webform!
Location: USC Admission Center
Audiences: Prospective Freshmen and Family Members - RESERVATIONS REQUIRED
Contact: Viterbi Admission
-
How to Explore a Fast-Changing World (Cover Time of a Simple Random Walk on Evolving Graphs)
Mon, Jul 27, 2009 @ 11:00 AM - 12:00 AM
Ming Hsieh Department of Electrical and Computer Engineering
Conferences, Lectures, & Seminars
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
with fixed underlying vertex set, 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 connected 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 a simple
random walk on connected dynamic graphs to be exponential. We 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: Michal Kouck´y and Zvi LotkerBio:
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 now 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.
Host: Bhaskar KrishnamachariLocation: Hughes Aircraft Electrical Engineering Center (EEB) - 248
Audiences: Everyone Is Invited
Contact: Rahul Jain
