all by date all by type workshops courses colloquium seminars lunches
Wednesday, 04.16.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Capacity Approximations for Gaussian Relay Networks
Ayfer Ozgur , Stanford University
In this talk, I will overview the recent approximation approach to the capacity of Gaussian relay networks. Here, the capacity of the network is bounded within a gap that is independent of the channel configurations and the SNR. We will discuss the new insights brought by this approximation approach as well as its major limitations. The most important limitation of the existing approximation results is that the gap to capacity grows linearly in the number of nodes, making the approximation useless for networks even of moderate size...more >
Wednesday, 04.23.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Load Balancing in Large Graphs
Venkat Anantharam , UC Berkeley
We consider load balancing on a large graph. Each edge has a unit of load that it wishes to distribute between its nodes in the most balanced way. For infinite graphs the corresponding load balancing problem exhibits nonuniqueness, related with role of boundary conditions in statistical mechanical models. Nevertheless, we are able to extend the notion of balanced loads from large finite graphs to their local weak limits, using the concept of unimodularity...more >
Friday, 04.11.14, 11 a.m - 12 p.m., Jacobs Hall, Room 4309
Time-to-Digital Converters for Digitizing Biology
Christopher Salthouse, University of Massachusetts, Amherst
In the fifty years since the invention of CMOS circuits, an army of scientists and engineers have worked to increase their complexity and speed while decreasing their size and power consumption to drive the computer revolution. In doing so, they developed a technology that is also well suited for a variety of other applications including the topic of this talk “Digitizing Biology...more >
Wednesday, 04.09.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Using Posets into Coding Theory
Marcelo Firer, Universidade Estadua de Campinas, Brazil
Partial ordered on finite sets are used to define position-sensitive metrics over F_{q}ⁿ. We will make a very introductory presentation of those metrics and explain the apparent paradox that determining the packing radius may become absolutely intractable (even in 1 dimensional cases), while syndrome decoding may become a really affordable problem, becoming even a linear map...more >
Wednesday, 04.02.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Modulation and Coding Techniques for Enhancing Flash Memory Endurance
Eyal En Gad, Caltech
Motivation: Current flash memory technology supports a relatively small number of write-erase cycles. This technology is effective for consumer devices (smartphones and cameras) where the number of write-erase cycles is small, however, it is not economical for enterprise storage systems that require a large number of lifetime writes. I will present two approaches for alleviating this problem...more >
Tuesday, 03.25.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Coverage and Percolation in Random Geometric Graphs
Amites Sarkar, Western Washington University
Place a billion black points and a million red points uniformly at random in a large disc D. Now grow a disc about each black point until it hits the nearest red point. What is the expected proportion of D that is covered by the small discs? What is the probability that D is entirely covered? These questions were inspired by the issue of security in wireless  networks; the black points represent nodes of the network, and the red points represent  eavesdroppers...more >
Wednesday, 03.12.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Cooperative Schemes for Real-Time Applications on Mobile Devices
Athina Markopoulou , UC Irvine
This talk gives an overview of our work on design and implementation of cooperative schemes, with network coding, for real-time applications on mobile devices. First, we consider video streaming: a group of mobile devices, within proximity of each other, are interested in watching the same video at the same time. The common practice today is that each device uses its own wireless connection to stream the video independently from the server, and typically the downlink bandwidth becomes the bottleneck...more >
Thursday, 03.06.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 3004
Control over finite capacity channels: the role of data losses, delays and SNR limitations
Luca Schenato, University of Padova, Italy
In this talk we will discuss the problem of feedback control design in the present of a finite capacity communication channel, which gives rise to tightly coupled limitations in terms of quantization errors, decoding/computational delays and erasure probability affecting the closed loop control performance. After providing an overview of the most notable results available in the literature, we will restrict the analysis in the context of LQG control subject to SNR limitations, packet loss, and delay and derive their impact on optimal design for the controller parameters...more >
Wednesday, 02.26.14, 3:00 PM - 4:00 PM, Atkinson Hall, Room 4004
Towards Clinically Viable Neural Prosthetic Systems
Vikah Gilja, UCSD
Brain-machine interfaces (BMIs) translate neural activity into control signals for guiding prosthetic devices, such as computer cursors and robotic limbs, offering disabled patients greater interaction with the world. BMIs have recently demonstrated considerable promise in proof-of-concept animal experiments and in human clinical trials. However, a number of challenges for successful clinical translation remain, including system performance and robustness across time and behavioral contexts...more >
Wednesday, 02.19.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Brownian Motion Through Invertible Matrices in High Dimension
Todd Kemp, UCSD
Friday, 02.07.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Non-Asymptotic Analyses on Problems with Markovian Memory
Shun Watanabe , University of Tokushima
Non-asymptotic (or finite blocklength) analysis is becoming an important topic in information theory recently, and many non-asymptotic bounds have been obtained so far for the memoryless case. For problems with Markovian memory, the existing bounds are not useful in the sense that they are not efficiently computable. In this talk, we consider the source coding problem with side-information and the random number generation problem with side-information...more >
Wednesday, 02.05.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
Distributed Game Theoretic Optimization and Management of Multi-Channel ALOHA Networks
Kobi Cohen, UC Davis
We consider the problem of distributed rate maximization in multi-channel ALOHA networks. We mainly focus on networks containing a large number of users that transmit typically over a low number of channels.

First, we consider the problem of constrained distributed rate maximization, where user rates are subject to total transmission probability constraints...more >
Wednesday, 01.29.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004
ITLinQ: A New Approach for Spectrum Sharing in Device-to Device Communication Systems
Salman Avestimehr, University of Southern California
We consider the problem of spectrum sharing in device-to-device communication systems. We define a new concept of information-theoretic independent sets (ITIS), which indicates the sets of users for which simultaneous communication and treating the interference from each other as noise is information-theoretically optimal (to within a constant gap)...more >
Wednesday, 01.22.14, 3PM - 4PM, Atkinson Hall (Calit2) 4004
Designing Optimal Resource Sharing in the Long Run
Mihaela van der Schaar, Electrical Engineering, UCLA
Designing Optimal Resource Sharing in the Long Run
Wednesday, 01.15.14, 3PM - 4PM, Atkinson Hall (Calit2) 4004
Catching Up Faster by Switching Sooner: Improved Data Compression and Statistical Inference with Nested Models
Peter Grünwald, CWI Amsterdam & Leiden University
Catching Up Faster by Switching Sooner: Improved Data Compression and Statistical Inference with Nested Models
Wednesday, 12.11.13, 11 a.m - 12 p.m., Jacobs Hall, Room 6504
On Cooperative Radio Resource Allocation techniques based on Game Theory
Ephi Zehavi, Bar Ilan University
On Cooperative Radio Resource Allocation techniques based on Game Theory
Monday, 11.18.13, 3PM - 4PM, Atkinson Hall (Calit2) 4004
Cognitive Access Policies under a Primary ARQ process via Forward-Backward Interference Cancellation
Michele Zorzi, Department of Information Engineering, University of Padova
Cognitive Access Policies under a Primary ARQ process via Forward-Backward Interference Cancellation
Friday, 11.15.13, 3PM - 4PM, Atkinson Hall (Calit2) 4004
VIP: A Framework for Joint Dynamic Forwarding and Caching in Named Data Networks
Edmund Yeh, Electrical and Computer Engineering, Northeastern University
VIP: A Framework for Joint Dynamic Forwarding and Caching in Named Data Networks
Wednesday, 11.13.13, 3PM - 4PM, Jacobs Hall, Room 4309
Resource Sharing in Stochastic Networks
Ruth J. Williams, Dept. of Mathematics, UCSD
Resource Sharing in Stochastic Networks
Tuesday, 11.05.13, 3PM - 4PM, Jacobs Hall, Room 4309
Raef Bassily, Dept. of Computer Science & Engineering, Penn State University
Wednesday, 10.30.13, 3PM, Jacobs Hall, Room 4309
Frames and Spherical Codes: where Slepian meets Fourier and Galois
Babak Hassibi, Department of Electrical Engineering, CALTECH
Babak Hassibi
Wednesday, 10.23.13, 3PM, Jacobs Hall, Room 4309
Compression for Similarity Queries
Tsachy Weissman, Dept. of Electrical Engineering, Stanford University
Compression for Similarity Queries
Wednesday, 10.09.13, 3PM - 4PM, Jacobs Hall, Booker Conference Room 2512
Selfish routing: networks, games, and individual choice
Professor Ilze Ziedins, University of Auckland
Selfish routing: networks, games, and individual choice
Friday, 09.20.13, 10AM - 11AM, Jacobs Hall, Booker Conference Room 2512
Integer-forcing for channels, sources and ADCs
Or Ordentlich, Tel Aviv University
Integer-forcing for channels, sources and ADCs
Tuesday, 07.16.13, 11 a.m - 12 p.m., Jacobs Hall, Room 2512 (Booker Conference Room)
Asymptotics of the invariant measure in mean-field model with jumps
Rajesh Sundaresan, Indian Institute of Science, Bangalore
Asymptotics of the invariant measure in mean-field model with jumps
Thursday, 06.06.13, 11 a.m - 12 p.m., Jacobs Hall, Room 2512 (Booker Conference Room)
Efficient Two-Way Relaying Schemes for Amplify and Forward Relays with Multiple Antennas
Martin Haardt, Ilmenau University of Technology, Germany
Efficient Two-Way Relaying Schemes for Amplify and Forward Relays with Multiple Antennas
Wednesday, 05.22.13, 10 AM - 11 AM, Jacobs Hall, Room 2512 (Booker Conference Room)
Topological Interference Management
Syed Ali Jafar , UC Irvine
W..more >
Monday, 05.13.13, 2:00pm - 3:00pm, Jacobs Hall, Booker Room 2512
Networked Information Processing: New Compression, Processing and Control Paradigms for Networks
Emrah Akyol, UC Santa Barbara
Networked Information Processing: New Compression, Processing and Control Paradigms for Networks
Tuesday, 04.09.13, 11:00am - 12:00pm, Calit2, Atkinson Hall, Room 4004
Variable-Length Coding with Feedback: Finite-Length Analysis and Optimization
Tsung-Yi Chen, UCLA
This talk will show that the performance gap between these methods and the optimized variable-length coding scheme can be significant without a careful treatment in system design.
Tuesday, 03.12.13, 11:00am - 12:00pm, Jacobs Hall, Room 2512, Henry G. Booker Conference Suite
From Likelihood Filtering to Quantum Probabilities
Hans-Andrea Loeliger, ETH Zurich
From Likelihood Filtering to Quantum Probabilities
Friday, 02.01.13, 3:30pm - 4:30pm, Jacobs Hall, Room 2512, Henry G. Booker Conference Suite
Integration of Sensing, Communication, and Navigation in Mobile Networks
Yasamin Mostofi, University of California, Santa Barbara
In this talk, I develop a foundation for the integration of sensing, communication and navigation in mobile networks.
Thursday, 01.10.13, 4:00pm - 5:00pm, AP&M Building, Room 6402
Near-Optimal Quantization and Encoding for Oversampled Signals
Rayan Saab, Duke University
A good A/D scheme allows for accurate reconstruction of the original object from its quantized samples. In this talk we investigate the reconstruction error as a function of the bit-rate, of Sigma-Delta quantization, a class of quantization algorithms used in the oversampled regime.
Wednesday, 11.28.12, 2:00pm - 3:00pm, Jacobs Hall, Room 4309
Two Network Problems and Their Application to Streaming Codes
Tracey Ho, Caltech
We consider two established network-related problems, whose complete solutions are open. The first is a resource allocation problem that can be posed in a distributed storage context as follows. The problem is to store a unit size data object on a set of storage nodes such that the total amount of storage used does not exceed a given budget, and the probability of successful recovery is maximized under a given probabilistic model for node failure/accessibility. The second is network error correction coding for reliable communication over networks where arbitrary errors can occur on an unknown subset of links. We describe how some of our recent results on these two problems can be combined to design and analyze erasure correction coding for online streaming under probabilistic packet erasures.
Monday, 11.19.12, 11 AM - 12 PM, Atkinson Hall, Room 4004
The Art of Gambling in a Team: Multi-player multi-armed bandits
Rahul Jain, University of Southern California
Multi-Armed bandits are an elegant model of learning in an unknown and uncertain environment. Such models are relevant in many scenarios, and of late have received increased attention recently due to various problems of distributed control that have arisen in wireless networks, pricing models on the internet, etc. We consider a non-Bayesian multi-armed bandit setting proposed by Lai & Robbins in mid-80s...more >
Thursday, 11.15.12, 10 a.m  - 11 a.m, Applied Physics & Mathematics Building (AP&M), Room 6402
A toy limit order book
Elena Yudovina, University of Michigan
I consider a Markov process inspired by a toy model of a limit order book. "Bid" and "ask" orders arrive in time; the prices are iid uniform on [0,1]. (I'll discuss some extensions.) When a match is possible (bid > ask), the highest bid and lowest ask leave the system. This process turns out to have surprising dynamics, with three limiting behaviours occurring with probability one...more >
Thursday, 11.08.12, 2:00 PM - 3:00 PM, Jacobs Hall, Room 2512 (Booker Conference Room)
Modeling Random Access in Underwater Acoustic Networks
Paolo Casari, University of Padova, Italy
T..more >
Friday, 11.02.12, Atkinson Hall
CWC Seminar

If you would like to attend, please register by Wednesday 10/31

Morning presentations
8:30 Continental breakfast
9:00 Welcome
9:05 Content-centric message forwarding in ad-hoc networks, Rene Cruz, UCSD
9:33 Ultra-low-power radios for miniaturized wireless systems, Patrick Mercier, UCSD
10:01 Cloud mobile media: opportunities and challenges, Sujit Dey, UCSD
10:29 Break
10:44 Qualcomm Research: Radios and a whole lot more, Charles Bergan, Qualcomm
11:12 Real-time communication over unreliable wireless channels, P...more >
Thursday, 11.01.12, 2pm - 3pm, Calit2 Atkinson Hall 4004
Lossy Compression for BigData: First Steps
Dr. Thomas Courtade, Stanford University
Two key challenges in fitting BigData problems into a lossy compression framework are (i) the selection of an appropriate distortion measure, and (ii) characterizing the performance of distributed systems. Inspired by real systems, like web search, which return a list of likely data entries indexed by likelihood, we study the "logarithmic loss" distortion function in a multiterminal setting,
thus addressing both challenges. In particular, we characterize the rate-distortion region for two (generally open) multiterminal source coding problems when distortion is measured under logarithmic loss. In addition to the main results, I'll discuss applications to machine learning, estimation, and combinatorics.
Friday, 10.26.12, 2:00pm, Jacobs Hall, Room 4309
Towards Computational Sensing through large number of Networked Sensors
Prof. Lin Zhang, Dept. of Electronic Engineering, Tsinghua University
Today, Internet users and networked sensors generate hundreds of gigabytes of data every minute, yet people are still feeling lost in an ocean of data, sometimes being starved of knowledge. In this talk, I will try to convince the audience, by sharing some experimental results in the systems the we developed and deployed in the past few years, that a surprisingly better understanding of the reality could be attained by performing state-of-art algorithms over large volume of data collected through networked sensors...more >
Thursday, 10.25.12, 3:00 PM - 4:00 PM, Jacobs Hall, Room 2512 (Booker Conference Room)
Three Open Problems in Network Communication
Michael Langberg, The Open University of Israel
In this talk I will discuss three natural open questions in the context of multi-source/ multi-terminal network communication via network coding. (a) What is the maximum loss in communication rate experienced from removing a single unit capacity edge from a given network? (b) What is the maximum loss in rate when insisting on zero error communication as opposed to vanishing decoding error? (c) What is the maximum loss in rate when comparing the communication of source information that is ``almost' independent to that of independent source information?

Recent results including intriguing connections between the three questions will be presented...more >
Thursday, 10.04.12, 10 a.m  - 11 a.m, Applied Physics & Mathematics Building (AP&M), Room 6402
Queue-Size Scaling in Switched Networks
Devavrat Shah , MIT, visiting Stanford University
We consider a switched (queueing) network in which there are
constraints on which queues may be served simultaneously; such
networks have been used to effectively model input-queued switches,
wireless networks and more recently data-centers. The scheduling
policy for such a network specifies which queues to serve at any point
in time, based on the current state or past history of the system...more >
Tuesday, 08.14.12, 11:00 am - 12:00 pm, Jacobs Hall, Room 4309
Long Range Dependent Markov Models
Barlas Oguz, Ph.D., University of California, Berkeley
We discuss countable state Markov chains as a flexible class of models for long range dependent sources. We state sufficient conditions under which an instantaneous function of a long range dependent Markov chain has the same Hurst index as the underlying chain. We discuss several applications of the theorem in the fields of information theory, queuing networks, and finance.

Friday, 06.15.12, 11:00am - 12:00pm, Atkinson Hall (Calit2), Room 4004
ITA Seminar: On q-ary Antipodal Matchings and Applications
Dr. Gadiel Seroussi, HP Laboratories
We define a q-ary antipodal matching to be a perfect matching in the bipartite graph with vertices corresponding to words of length m over the integer alphabet Q={0,1,...,q-1} wherein the left and right vertices are those with respective component sums greater and smaller than m(q-1)/2, and wherein two
vertices are connected by an edge if one of the corresponding words dominates the other. We present two different constructions of efficiently computable q-ary antipodal matchings. We then show how such matchings can be used for encoding arbitrary data into n x n arrays over the alphabet Q all of whose row and column sums are at most n(q-1)/2. Such encoders might be useful for mitigating parasitic currents in a next generation memory technology based on crossbar arrays of resistive devices.

(Joint work with Erik Ordentlich and Ronny Roth.)

Wednesday, 05.23.12, 11 AM - 12 PM, Atkinson Hall, Room 4004
Error Correcting Codes for Distributed Control
Ravi Teja Sukhavasi , Caltech
Coding and information theory, the joint pillars upon which the telecommunications revolution has thrived, deal with how to reliably transmit information over unreliable channels. This is done by gathering large blocks of data and encoding them into larger blocks of data before transmitting, thereby achieving reliability at the expense of encoding/decoding delay...more >
Monday, 04.30.12, 3:00 pm - 4:00 pm, Jacobs Hall, Room 2512, Henry G. Booker Conference Suite
On Source-Channel Communication in Networks
Jun Chen, McMaster University
This talk is divided into two parts. In the first part of this talk, I
will present several results on the optimality and approximate
optimality of the source-channel separation architecture for lossy
source coding in general networks. These results are shown without
explicitly characterizing the achievable joint source-channel coding
distortion region or the achievable separation-based coding distortion
region. The second part of this talk is devoted to the problem of
sending two correlated vector Gaussian sources over a
bandwidth-matched two-user scalar Gaussian broadcast channel, where
each receiver wishes to reconstruct its target source under a
covariance distortion constraint. I will present a lower bound on the
optimal tradeoff between the transmit power and the achievable
reconstruction distortion pair. The derivation of this lower bound is
based on a new bounding technique which involves the introduction of
appropriate remote sources. Furthermore, it is shown that this lower
bound is achievable by a class of hybrid schemes for the special case
where the weak receiver wishes to reconstruct a scalar source under
the mean squared error distortion constraint. This talk is based on
joint work with Lin Song, Chao Tian, Suhas Diggavi, and Shlomo Shamai.
Tuesday, 02.14.12, 10:30 a.m - 11:30 a.m, Jacobs Hall, Room 2512 (Booker Conference Room)
Compressive Depth Acquisition Cameras: Principles and Demonstrations
Vivek Goyal, MIT
LIDAR systems and time-of-flight cameras use time elapsed from
transmitting a pulse and receiving a reflected response, along with
scanning by the illumination source or a 2D sensor array, to acquire
depth maps. We introduce depth map acquisition with high spatial and
range resolution using a single, omnidirectional, time-resolved
photodetector and no scanning components. This opens up
possibilities for 3D sensing in compact and mobile devices.

Spatial resolution in our framework is rooted in patterned
illumination or patterned reception. In contrast to compressive
photography, the information of interest -- scene depths -- is
nonlinearly mixed in the measured data. The depth map construction
uses parametric signal modeling to achieve fine depth resolution and
to essentially linearize the inverse problem from which spatial
resolution is recovered. We have demonstrated depth map
reconstruction for both near and medium-range scenes, with and
without the presence of a partially-transmissive occluder.

Our compressive depth acquisition camera (CoDAC) framework is an
example of broader research themes of exploiting time resolution in
optical imaging and identifying and exploiting structure in inverse
Monday, 01.30.12, 3:00 PM - 4:00 PM, Jacobs Hall, Room 2512 (Booker Conference Room)
Algorithmic Phase Transitions
Dimitris Achlioptas, UC Santa Cruz
Constraint Satisfaction Problems are the common abstraction of numerous real-life settings, ranging from air-traffic design to protein folding. The ubiquity of CSPs presses forward a fundamental question: why is finding solutions to certain CSP instances exceptionally hard while often for, seemingly similar, instances it is quite easy? To study this phenomenon in a principled way we consider probability distributions over CSP instances formed by adding constraints one-by-one, uniformly and independently...more >
Friday, 01.27.12, 11 AM - 12 PM, Atkinson Hall, room 4004
Load balancing for dynamically scalable web services
Web services have traditionally benefited from efficient load balancing. With multi-tenancy and the need for dynamic scalability in the cloud environment, existing hardware load balancers are expensive, difficult to scale and difficult to divide among users. Software load balancers are cost-efficient, scalable and divisible, but lack efficient load balancing algorithms...more >
Wednesday, 01.25.12, 11 AM - 12 PM, Room 2512, Jacobs Hall (Booker Conference Room)
An Exploration of Sparse Projections: Networks, Signals and Genetics
Soheil Feizi, Graduate Student, MIT
Using sparse projections can provide benefits in signal representation, reconstruction, and computation in different areas. For applications where signal sources are distributed across a noisy network, managing sparsity, whether naturally occurring or introduced, can be used to reconstruct/compute source signals in a computationally effective way. We introduce a joint source-channel-network coding scheme, which uses compressive sensing principles. Since there is no separation of channel, source and network coding, joint techniques are natural and this one allows for an integrated way to deal with these different aspects together. For applications such as cloud computing and functional compression, where computation, rather than reconstruction only, over a network is important, we introduce a sparse network design technique based on functional information flows. We conclude by presenting some applications of sparse representation in biological systems. In monitoring, our new techniques can considerably lower energy use in body area networks, even when compared to traditional compressive sensing. In motif discovery, we illustrate the effectiveness of our information-theoretically inspired techniques.
Wednesday, 11.02.11, 11 AM - 12 PM, Jacobs Hall, Room 2512 (Booker Conference Room)
New Channels for Underwater Acoustic Communication: The Particle Velocity Channels
Ali Abdi, PhD, Associate Professor, NJIT, Newark
The scalar component of the acoustic field, i.e., the pressure channel, has been extensively used for underwater acoustic communication. In recent years, vector components of the acoustic field, such as the three components of acoustic particle velocity, are suggested in our group for underwater communication. Consequently, one can use vector sensors for underwater communication. The small size of vector sensor arrays is an advantage, compared to pressure sensor arrays commonly used in underwater acoustic communication. This is because velocity channels can be measured at a single point in space. So, each vector sensor serves as a multichannel device. This is particularly useful for compact underwater platforms, such as autonomous underwater vehicles (AUVs). Our research efforts have focused on two closely-related problems: channel modeling and transceiver design. Channel modeling research aims at characterization of those aspects of acoustic particle velocity channels such as channel correlations, delay and Doppler spreads, etc., which determine the communication system performance. Transceiver design addresses optimal use of vector sensors and particle velocity for data modulation and demodulation, equalization, etc. (work supported by NSF).
Friday, 10.14.11, 11 AM - 12 PM, Jacobs Hall, room 4309
Sampling Online Social Networks
Athina Markopoulou, UC Irvine
Online Social Networks (OSNs) have recently emerged as a new Internet killer-application and are of interest to a range of communities, ranging from computer science and engineering to social sciences. OSNs are widely studied today based on samples collected through measurement of publicly available information. In this talk, I will give an overview of our recent work on sampling online social networks...more >
Friday, 07.22.11, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Room 6504
Wireless Channel Uncertainty in Relay-Assisted Communication and Distributed Detection Systems
Azadeh Vosoughi , University of Rochester
One of the main challenges in wireless communications is coping with channel uncertainty. Dealing with this uncertainty, and the limitations it imposes, is tightly related to the specific system and its application. In this talk, we consider two systems, namely a wireless bi-directional relay-assisted communication system and a wireless distributed detection system...more >
Tuesday, 05.24.11, 1:30 - 2:30 pm, CMRR Auditorium
Information-theoretic and algorithmic applications of quantum conditional mutual information
Jon Yard, Los Alamos National Laboratory
Conditional mutual information I(A;B|C) plays an important role throughout information theory. It is at least as important in quantum information, where the richer nature of quantum states presents new challenges and at the same time, offers the possibility for wider applicability in physics and the theory of computation. In this talk, which assumes no prior knowledge of quantum mechanics, I will present joint work (arXiv:1010...more >
Monday, 05.09.11, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512
Modeling and Characterization of Large-Scale Wi-Fi Traffic in Public Hot-Spots
Dr. Amitabha Ghosh, Princeton University
Server side measurements from several Wi-Fi hotspots deployed in nationwide network over different types of venues from small coffee shops to large enterprises are used to highlight differences in traffic volumes and patterns. We develop a common modeling framework for the number of simultaneously present customers. Our approach has many novel elements: (a) We combine statistical clustering with Poisson regression from Generalized Linear Models to fit a non-stationary Poisson process to the arrival counts and demonstrate its remarkable accuracy; (b) We model the heavy tailed distribution of connection durations through fitting a Phase Type distribution to its logarithm so that not only the tail but also the overall distribution is well matched; (c) We obtain the distribution of the number of simultaneously present customers from an M_t/G/1 queuing model using a novel regenerative argument that is transparent and avoids the customarily made assumption of the queue starting empty at an infinite past; (d) Most importantly, we validate our models by comparison of their predictions and confidence intervals against test data that is not used in fitting the models...more >
Wednesday, 04.13.11, 11:00 a.m. - 12:00 p.m. , Jacobs Hall, Booker Conference Room, 2512
On channel polarization and polar codes
Eren Sasoglu, Ecole Polytechnique Fédérale de Lausanne, Switzerland
Arikan's polar codes achieve the symmetric capacity of binary-input memoryless channels at low encoding and decoding complexity. Early work on polar codes has shown that their underlying principle, i.e., polarization, is not restricted to binary-input channels. We discuss polarization for non-binary channels and sources, and for multiple-access channels...more >
Wednesday, 04.06.11, 11:00 a.m. - 12:00 p.m. , Jacobs Hall, Booker Conference Room, 2512
Finite-Constellation Capacity of the Gaussian Channel
Yihong Wu, Princeton University
Denote by C_m(snr) the Gaussian channel capacity with signal-to-noise ratio snr and input cardinality m. We show that as m grows, C_m(snr) approaches C(snr) = 1/2 log(1 + snr) exponentially fast. Lower and upper bounds on the exponent are given as functions of snr. We propose a family of input constellations based on the roots of the Hermite polynomials that achieves exponential convergence, while quantization-based schemes are shown to achieve only polynomial convergence...more >
Friday, 04.01.11, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512
Data transmission: non-asymptotic fundamental limits
Yury Polyanskiy, Princeton University
Noise is an inalienable property of all communication systems appearing in nature. Such noise acts against the very purpose of communication, namely the delivery of data to its destination with minimal possible distortion. This creates a problem that has been addressed by various disciplines over the past century. In particular, information theory studies the question of the maximum possible rate achievable by an ideal system under certain assumptions regarding the noise generation and structural design constraints...more >
Wednesday, 03.30.11, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512
Network Interference Management via Interference Alignment
Viveck Cadambe, UC Irvine
Interference alignment has recently emerged as an effective technique to manage interference - the principal bottleneck of rates in wireless communication systems. In this talk, I will explore the principles and applications of the technique of interference alignment.

The canonical model to study interference is the wireless interference network which has K mutually interfering users sharing for the same spectrum...more >
Friday, 01.07.11, 12:00PM - 1:00PM, Atkinson Hall 3004
Utility Optimal Scheduling in Networks: Small Delay and No Underflow
Longbo Huang, USC
The recently developed Lyapunov optimization technique (commonly known as Backpressure / Max-Weight) is a powerful tool for solving a large class of stochastic network optimization problems. In this talk, we extend the theory in two directions:  (i) We prove that dramatically improved delay is achievable with a simple Last-In-First Out (LIFO)-Backpressure rule, (ii) We generalize to "processing networks" where processing actions combine commodities of different queues to produce outputs, which involves a challenging "no underflow" constraint.

In the first part of the talk, we show that the LIFO-Backpressure algorithm can achieve utility within epsilon of optimality (for any epsilon>0), with O([log(1/epsilon)]^2) average delay.  This dramatically improves upon the previous O(1/epsilon) delay bounds, and results in 95-98% delay reduction in practical implementations.  Remarkably, LIFO-Backpressure achieves...
Wednesday, 11.03.10, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512
Network Science for Wireless Communication: Information Dissemination, Mobility, and Resilience
Edmund Yeh, Yale University
Over the past decade, there has been a concerted effort to develop a
network science for studying physical, biological, social, and
information networks within a common framework. Of particular
interest is the understanding of connectivity, information dynamics,
and robustness in large-scale networks with spatial location and
mobility. In this talk, we discuss a number of recent results from
the application of network science ideas to mobile wireless
communication...more >
Wednesday, 08.11.10, 2:00 PM - 3:00 PM, Jacobs Hall, Booker Conference Room, 2512
Variable-Length Markov Modeling of Training Data Yields Optimal Universal Classification of Finite-Length Individual Test Sequences
Jacob Ziv, Technion - Israel Institute of Technology
Consider a classifier that observes an individual training sequence X and a test sequence Y of length N, over a finite alphabet. The classifier’s task is to decide whether the test sequence has the same features as those captured by the training sequence (which may be longer than N).

It is assumed that the degree of similarity is measured in terms of the empirical average length of typical substrings (“patches”) that identically (or almost identically) appear in both sequences...more >
Friday, 07.30.10, 11:00 a.m. - 12:00 p.m., Atkinson Hall (CALIT2), room 4004
Decomposing permutations by cost-constrained transpositions
Olgica Milenkovic, University of Illinois at Urbana-Champaign
We address the problem of finding the minimum decomposition of a permutation in terms of transpositions with non-uniform cost. Our investigation is motivated by three different applications. The first application pertains to sorting of genomic sequences, while the second application is related to a generalization of the notion of a chemical channel (also known as trapdoor channel)...more >
Wednesday, 06.09.10, 11:00 a.m. - 12:00 p.m. , Jacobs Hall, Booker Conference Room, 2512
Interactive distributed source coding for network function computation
Nan Ma, Boston University
Today, blocklength, rate, SNR, frequency, quantizer resolution, and network size are well-studied and recognized resources for communication in information theory. A relatively less well recognized and less understood resource for communication and computation is interaction. Interaction as a resource becomes particularly valuable in the context of distributed function computation where it may be necessary for nodes to exchange information bidirectionally, perform computations, and harness the structure of the functions, statistical-dependencies, and the network topology to maximize the overall computation-efficiency as opposed to only generating, receiving, and forwarding data...more >
Wednesday, 05.05.10, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512
The Value of Volatile Resources in Electricity Markets
Sean P. Meyn, University of Illinois at Urbana-Champaign
While renewable resources most certainly provide environmental benefits, and also help to meet aggressive renewable energy targets, their deployment has pronounced impacts on system operations. There is an acute need to understand these impacts in order to fully harness the benefits of renewable resource integration. In this paper we focus on the integration of wind energy resources in a multi-settlement electricity market structure. We study the dynamic competitive equilibrium for a stochastic market model and obtain closed form expressions for the supplier and consumer surpluses. Numerical results based on these formulae show that the value of wind generation to consumers falls {dramatically} with volatility. In fact, we can establish thresholds for the coefficient of variation beyond which the value of wind is questionable. These findings can help guide the integration of renewables in future electricity markets.
Thursday, 04.29.10, 2:00PM - 3:00PM, EBU-I, Room 2512 Henry G. Booker Conference Suite
Mutual Information, Relative Entropy, and the Relationship Between Causal and Non-Causal Mismatched Estimation in AWGN Channels
Tsachy Weissman, Stanford
A continuous-time process with distribution P is observed through an Additive White Gaussian Noise channel, at a given signal-to-noise ratio (SNR), and is estimated by an estimator that would have minimized the mean-square error if the process had distribution Q. We show that the causal filtering mean-square error (MSE) achieved at SNR level snr is equal to the average value of the noncausal (smoothing) MSE achieved with a channel whose SNR is chosen uniformly distributed between 0 and snr. Emerging as the bridge for equating these quantities are mutual information and relative entropy. Our results build on and extend those of [Duncan 1970], [Guo, Shamai and Verdu 2005], and [Verdu 2009] in ways that will be explained. I will also present extensions that accommodate the presence of feedback and discuss implications on minimax estimation.
Wednesday, 04.28.10, 1:30 p.m. - 2:30 p.m. , Atkinson Hall (CALIT2), room 6004
Matrix completion: fundamental limits and efficient algorithms
Sewoong Oh , Stanford University
A number of data sets are naturally described in matrix form. Examples range from micro-arrays to collaborative filtering data. In many of these examples, Singular Value Decomposition (SVD) is a powerful and widely-used technique to construct a low-rank approximation, thus achieving a great dimensionality reduction. However, when we have incomplete data, SVD is strictly sub-optimal...more >
Friday, 04.23.10, 11:00AM - 12:00PM, 4004 Atkinson Hall
Opportunistic Routing in Wireless Networks with Congestion Diversity
Tara Javidi, UCSD
Opportunistic routing for multi-hop wireless networks has seen recent research interest to overcome deficiencies of traditional routing. First,
we, briefly, cast opportunistic routing as a Markov decision problem (MDP)and introduce a stochastic variant of distributed Bellman-Ford which provides a unifying framework for various versions of opportunistic routing such as SDF, GeRaF, and EXOR.

In the second part of the talk, we touch upon the issue of congestion and throughput optimality by contrasting the opportunistic MDP-based schemes
with back-pressure schemes. Inspired by the properties of backpressure algorithm, we propose a modification of the MDP framework to account for congestion and arrive at a throughput-optimal policy, aka ORCD, that exhibits significant delay improvements over the existing candidates in the literature. In the process of proving the throughput optimality of ORCD, we introduce a new Lyapunov function construction which characterizes a large class of throughput optimal policies. The proposed class includes backpressure and ORCD as simple special cases.
Wednesday, 03.17.10, 11:00 AM - 12:00 PM, Atkinson Hall 4004
Large wireless networks: fundamental limits and design issues
Paolo Minero, UCSD
In this talk, we demonstrate how fundamental questions in large wireless networks can be addressed by applying methods from information theory, physics, networking and control. We focus on three examples of emerging systems architecture.

First, we investigate the maximum achievable throughput in a wireless ad-hoc network. By combining Maxwell's physics of wave propagation and
Shannon's theory of information, and departing from idealistic stochastic channel models for signal propagation, we derive an upper bound to the law that determines the scaling of throughput with the
population size of the network, and conclude that the scaling achieved by multi-hop communication is optimal in any constant density wireless
network...more >
Wednesday, 02.17.10, 1:30 PM - 2:30 PM, 6004 Atkinson Hall
On the Duality Between Slepian-Wolf Coding and Channel Coding
Jun Chen, McMaster University
Slepian-Wolf coding, also known as distributed lossless source coding, is of fundamental importance for many emerging applications. In this talk, we will discuss the intimate connections between Slepian-Wolf coding and channel coding. We show that there exist two different dualities between Slepian-Wolf coding and channel coding: type-level duality and linear codebook-level duality. These two dualities together provide a comprehensive picture of Slepian-Wolf coding and clarify many subtle differences between linear block codes, fixed-rate nonlinear codes, and variable-rate codes. The implication of this work on Slepian-Wolf code design will also be discussed.
Friday, 12.11.09, 11:00 - 12:00, 4004 Atkinson Hall
On information theoretic network security
Tracey Ho, Caltech
Information theoretic coding techniques can be used to provide
security against data modification and eavesdropping in networks. Coding
redundant information across multiple network links enables reliable
communication over a network even when individual links cannot be made
reliable, as in the case of adversarial data modification, for which it is
not sufficient to do error correction on a link by link basis. Coding the
source message together with random keys enables information theoretically
secret communication over networks where a subset of links can be
Friday, 11.13.09, 3:00 PM  - 4:00 PM, EBU2, Room 479
Understanding Implicit Communication in Distributed Control
Pulkit Grover, UC Berkeley
In distributed systems, control actions often serve a dual purpose -- minimizing the immediate control cost, and communicating relevant information to help other controllers. Unfortunately, though this “implicit communication” is ubiquitous, it also seems to make such problems hard. General communication problems have been addressed quite successfully using information theory...more >
Wednesday, 11.11.09, 2:00 PM - 3:00 PM, 4004 Atkinson Hall
Coding for online adversaries
Michael Langberg, The Open University of Israel
In this talk we consider the communication of information in the presence of an "online" or "causal" adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x=(x_1,...,x_n) symbol-by-symbol over a communication channel. The (malicious) adversarial jammer can view the transmitted symbols x_i one at a time, and can change up to a p-fraction of them. However, the decisions of the jammer must be made in an online (or causal) manner. Namely, for each symbol x_i the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on x_j for j <= i. This is in contrast to the ``classical' adversarial jammer which may base its decisions on its complete knowledge of the codeword x.
Wednesday, 11.04.09, 1:00 PM - 2:00 PM, 4004 Atkinson Hall
Network Compress-Forward
Young-Han Kim, Electrical and Computer Engineering, UCSD
In this talk, we extend the compress-forward coding scheme to a
general network with multiple sources and multiple destinations,
demonstrating that it provides a robust and scalable building block
for relaying. In particular, we show that the network compress-forward
coding scheme extends all previously known results on relay
networks (except for decode-forward), including multicast network
coding over noiseless networks by Ahlswede, Cai, Li, and Yeung,
coding for wireless relay networks and deterministic networks by
Avestimehr, Diggavi, and Tse, coding for wireless erasure networks
by Dana, Gowaikar, Palanki, Hassibi, and Effros, and coding for
linear erasure networks by Smith and Vishwanath. The key idea behind
network compress-forward is message repetition coding in which the
source transmits a single message over multiple transmission blocks.

Wednesday, 10.28.09, 2:00 PM - 3:30 PM, 4004 Atkinson Hall
Online Learning and Drifting games
Yoav Freund, CSE Department, UCSD
Online learning is an approach to statistical inference based
on the idea of playing a repeated game. Most popular online learning
strategies are based on exponential weights. In this talk I will
present a different family of games, called drifting games, and show
the relationship between them and online learning games. A new online
learning algorithm is derived and analyzed using drifting games. This
algorithm can also be analyzed in the context of continuous time,
revealing a tight connection between these games and Brownian motion.
Friday, 10.23.09, 11:00 - 12:00, 4004 Atkinson Hall
Convergence Results for Ant Routing Algorithms via Stochastic Approximation
Punyaslok Purkayastha, University of Maryland, College Park
We consider a class of routing algorithms for communication networks called Ant-Based Routing Algorithms (ARA), that are inspired by experimental observations of ant colonies in nature. It was found that ant colonies are able to "discover" the shorter of two paths to a food source by laying and following "pheromone trails". This idea has been adapted for purposes of routing in communication networks, whereby probe packets (analogues of ants) are used to explore the network and collect measurements of path delays...more >
Friday, 10.16.09, 11:00 a.m. - 12:00 p.m., Atkinson Hall (CALIT2), room 4004
Learning algorithms and Markov chain computations
Vivek Borkar, School of Technology and Computer Science,Tata Institute of Fundamental Research
This talk will describe potential applications of some reinforcement learning algorithms originally developed for policy evaluation for certain Markov decision problems, for some Markov chain computations. Notably, computation of stationary expectations and stationary distributions will be considered. Connections with Monte Carlo and numerical schemes will be highlighted and some possible acceleration schemes will also be discussed.
Monday, 10.12.09, 4:00 p.m. - 5:00 p.m., EBU1, room 4309
Information Theory meets Game Theory on the Interference Channel
Randall Berry , Northwestern University
As wired and wire-line communication networks migrate to more open models (e.g.~open spectrum access), it is becoming increasingly important to understand the interaction of different users, who may not have an incentive to cooperate with each other. Such questions are naturally studied using game theory. Here, we consider a canonical example of such a problem, namely a game among users sharing a Gaussian interference channel. Previous work on such "interference games" places restrictions on the encoding and decoding strategies of the users and thus are not truly information theoretic in nature. In this talk we discuss a general formulation for interference games that allows users to employ any encoding and decoding strategy. We discuss the solution of these games for the two-user linear deterministic interference channel and then partially extend these results to Gaussian interference channels.

This is joint work with David Tse at Berkeley.

Wednesday, 08.26.09, 2:00 PM - 3:00 PM, Atkinson Hall, Room 4004
On the optimality of universal classifiers for finite-length individual test sequences
Dr. Jacob Ziv, Technion-Israel Institute of Technology
An empirical informational divergence (relative entropy) between two individual sequences has been introduced in [1]. It has been demonstrated that if the two sequences are independent realizations of two finite-order, finite alphabet, stationary Markov processes, the proposed empirical divergence measure (ZMM), converges to the relative entropy almost surely...more >
Wednesday, 07.22.09, 11:00 - 12:00, 3004 Atkinson Hall
Collaboration, Power and Stability
Yoram Bachrach, Microsoft Research, Cambridge, UK
I will consider models of cooperation in multi-agent settings, with or
without strategic behaviour. Cooperation is easier in settings where the
agents are not self interested. In collaborative filtering, agents
attempt to recommend an information item, based on ratings of similar
users. I will discuss a sketching method that allows storing much less
information than the full ratings, and still achieve high quality
recommendations. I will then consider several models of cooperation in
multiagent systems from a computational game theoretic perspective. I
will show how to compute power indices, which reflect how much "real
power" an agent has in such environments. The common thread of both
these techniques are randomized algorithms and a statistical analysis of
the number of required samples.
Friday, 06.19.09, 12:00 - 1:00, 4004 Atkinson Hall
Reliable Relaying with Uncertain Knowledge
Jiwoong Lee, University of California, Berkeley
The motivation for this talkis to analyze the effect of information
uncertainty on the design and performance of protocols. The talk
considers two types of situations. The first is when different nodes in
the network have bounded knowledge about what other nodes know. The
second, called common knowledge about inconsistent beliefs, is when
the information is inconsistent but everyone knows it. Situations of
bounded or inconsistent information arise naturally in networks
because the state of these systems changes and nodes take time to
learn of those changes.
Monday, 06.08.09, 12:00 - 1:00, 4004 Atkinson Hall
Surprisal in real-time human language comprehension and production
Roger Levy, Department of Linguistics, University of California, San Diego
Probabilistic modeling has revolutionized computational linguistics in
the last fifteen years. In this talk, I describe how a fundamental
quantity in probability theory -- surprisal, or self-information -- is
starting to illuminate our understanding of real-time human language
processing as well. The talk covers two fundamental issues, one each
in language comprehension and production: what determines the
difficulty of comprehending a given word in a given sentence, and what
factors influence the choice that a speaker makes when it is possible
to express a meaning more than one way? The first half of the talk
covers models and experimental results in language processing that
show how probabilistic expectations can be a stronger determinant of
comprehension difficulty than more traditional measures of difficulty
based on memory load...more >
Tuesday, 05.26.09, 12:00 - 1:00, 4004 Atkinson Hall
Coding Techniques for Distributed Storage
Distributed storage schemes for Data centers and peer-to-peer networks often use
erasure coding to introduce redundancy for robustness.
We introduce novel network coding techniques that can surprisingly reduce the communication
required to maintain a storage system compared to standard Reed-Solomon codes used in current architectures. We present novel information theoretic performance bounds and explicit network codes that outperform known storage coding techniques. We show the connections of the storage repair problem to matroid theory and a computer search approach to finding optimal storage codes.

Monday, 05.18.09, 4:00 - 5:00, Atkinson Hall Room 4004
A Stochastic Control Viewpoint on `Posterior Matching'-style Feedback Communication Schemes
This paper re-visits Shayevitz & Feder's recent `Posterior Matching Scheme', a deterministic, recursive, capacity-achieving feedback encoding scheme for memoryless channels. We here consider the feedback encoder design problem from a stochastic control perspective. The state of the system is the posterior distribution of the message given current outputs of the channel. The per-trial reward is the average `reduction in distance' of the posterior to the target unit step function. We show that the converse to the channel coding theorem with feedback upper bounds the optimal reward, and that the posterior matching scheme is an optimal policy. We illustrate that this `reduction in distance' symbolism leads to the existence of a Lyapunov function on the Markov chain under this optimal policy, which leads to demonstration of achievability for all rates less than capacity.
Monday, 05.11.09, 12:00 - 1:00, Atkinson Hall Room 4004
Information theoretic generation of secret keys / Evaluation of Marton’s Inner Bound for the General Broadcast Channel
Amin Gohari, University of California, Berkeley
The talk consists of two main parts. In the first part of the talk, I will present our new bounds for two important models defined in the context of information-theoretic security. In the second part of the talk, I will introduce a non-Caratheodory type tool for proving cardinality bounds, and then apply the tool to derive cardinality bounds on the auxiliaries of Marton’s inner bound for the general broadcast channel.
Monday, 05.04.09, 11:45 - 12:45, Atkinson Hall Room 4004
Spectral Clustering of Surfaces
Ery Arias-Castro, University of California, San Diego
A typical generative model for surface clustering assumes that each cluster is the result of sampling a number of points in the neighborhood of a surface. In this setting, we provide theoretical guaranties for the pairwise spectral clustering technique of Ng, Jordan and Weiss (NIPS'01). We also introduce a new multi-way spectral clustering method based on local linear (or higher order) approximations, for which we provide theoretical guaranties as well...more >
Monday, 04.20.09, 12:00 - 1:00, Atkinson Hall Room 4004
Subspace Pursuit for Compressive Sensing and Its Applications
Wei Dai, University of Illinois at Urbana-Champaign
Compressive sensing (CS) is a technique for acquiring sparse signals efficiently. It has recently received significant attention, due to its large potential for practical applications in signal processing, statistics, and wireless communications, and due to its provable reconstruction performance guarantee via polynomial complexity algorithms. In this talk, we will first give a brief tutorial on CS and then focus on a greedy algorithm for signal reconstruction in CS, termed the subspace pursuit (SP) algorithm. The algorithm has two important characteristics: reconstruction accuracy of the same order as that of the benchmark optimization methods, and low computational complexity especially when the unknown signal is sufficiently sparse. Because of the inherent simple structure, the SP algorithm can be extended to different scenarios. We will see how to modify or apply this algorithm to accommodating quantization effects, solving matrix completion problems, and improving the existing interference cancellation techniques in wireless communications.

Monday, 04.13.09, 12:00 - 1:00, TBA
Automatic Verification of Data-centric Business Processes
Alin Deutsch, University of California, San Diego
The talk presents a study of business process systems that are centered
around "business artifacts", or simply "artifacts". This approach
focuses on data records, known as artifacts, that correspond to key
business-relevant objects, and that flow through a business process
specified by a set of services. The artifact-centric approach has
been introduced by IBM, and has enabled significant improvements to the
operations of medium- and large-sized businesses.
Artifacts carry attribute records and internal state relations,
that services can consult and update.
In addition, services can access an underlying database and
can introduce new values from an infinite domain, thus modeling
external inputs or partially specified processes described by
pre-and-post conditions.
Wednesday, 03.11.09, 11:30 - 12:30, Atkinson Hall, Room 6006
An information-theoretic view of early perception (or how nature discovered mutual information long before Shannon)
Nuno Vasconcelos, Department of Electrical and Computer Engineering, UCSD
Fifty years ago, Hubel and Wiesel revolutionized
neuroscience through the measurement of neural
responses in the primary visual cortex of the cat.
They uncovered a computational architecture, based
on simple and complex cells, which has been accepted
as a good model for early perception over the decades.
I will review some of our work on a new interpretation
of these neural computations as the measurement of
certain types of mutual information, for perceptual
stimuli that follow statistical distributions commonly
found in the natural world. This has a number of
interesting consequences for both the understanding
of biological perception and the development of new
algorithms for computer vision. I will review some
examples in the area of visual saliency, object
recognition, and visual tracking.
Monday, 03.02.09, 11:30 AM - 12:30 PM, Atkinson Hall, Room 4004
Haplotype assembly
Vineet Bafna, University of California, San Diego
The availability of high density SNP chips has empowered whole-genome
association scans for many common diseases. However, current genotyping
methods do not reveal haplotypes: the combination of alleles at
neighboring SNPs on a single chromosome that tend to be inherited
together. Knowledge of haplotypes is important for fine-scale
mapping of disease-related variants, and understanding the role of
different evolutionary mechanisms-meiotic recombination, positive
selection-in shaping human genetic variation. Statistical methods, based on
population genotypes analysis can be used, but are limited for long
range haplotyping. Parallel advances in sequencing technologies now allow sequencing of
individual genomes; they also enable haplotyping. In this talk, I will describe
combinatorial and stochastic (Markov Chain Monte Carlo) algorithms for reconstructing long and accurate haplotypes from whole genome sequence data for an individual (J. Craig Venter). While the overall method is a heuristic one, relying on computing cuts in an associated graph, it is motivated by a theoretical analysis of the mixing time for representative markov chains, where we show that two similar markov chains have very different mixing properties. Experimental results on the Venter data, and simulations validate the power of our approach to haplotype assembly.

Wednesday, 02.18.09, 11:30 - 12:30, Atkinson Hall, Room 6006
Graphical Models for Networks
Sujay Sanghavi, Electrical and Computer Enigneering, Purdue University
Graphical models combine probability theory and graph theory into a powerful formalism, facilitating the use of graph algorithms to simplify inferring about, sampling from, and learning of probability distributions. They have found applications in statistical physics, multivariate signal processing, machine learning, communications etc. In this talk we present a broad-based application of this formalism to networks. The talk will be made broadly accessible; in particular, it does not require pre-existing familiarity with graphical models.
Wednesday, 01.28.09, 11:30 - 12:30, Atkinson Hall, Room 6006
Invertible Extractors and Wiretap Protocols
Mahdi Cheraghchi, Laboratory of Algorithmic Mathematics, Swiss Federal Institute of Technology at Lausanne (EPFL)
A wiretap protocol is a pair of randomized encoding and decoding functions such that knowledge of a bounded fraction of the encoding of a message reveals essentially no information about the message, while knowledge of the entire encoding reveals the message using the decoder. We study the notion of efficiently invertible extractors and show that a wiretap protocol can be constructed from such an extractor. We will then construct invertible extractors for symbol-fixing and affine sources and apply them to create wiretap protocols with asymptotically optimal trade-offs between their rate (ratio of the length of the message versus its encoding) and resilience (ratio of the observed positions of the encoding and the length of the encoding). We will then apply our results to create wiretap protocols for challenging communication problems, such as active intruders who change portions of the encoding and the wiretap problem in network coding.
Wednesday, 01.21.09, 11:30 AM - 12:30 PM, Atkinson Hall, Room 6006
The Liar's Game with a List, and Error Correction with Feedback
Ofer Shayevitz, UCSD
Consider the following game played by Alice and Bob. Alice picks one of M objects, and Bob asks n yes/no questions trying to learn which one. Alice is allowed to lie at most t times, and Bob is declared the winner if he is able to provide a list of L objects containing the one selected by Alice. Does there exist a strategy which guarantees that Bob can always win? This question is equivalent to the problem of binary error correction with feedback under list-of-L decoding, and was extensively studied in the past for the unique decoding case of L=1.
Wednesday, 01.14.09, 11:30 AM - 12:30 PM, Atkinson Hall, Room 4004
IEEE 802.11 is Good Enough to Build Wireless Multi-Hop Networks
Apoorva Jindal, University of Southern California
We formally establish that IEEE 802.11 yields exceptionally good performance in the context of wireless multi-hop networks. A common misconception is that existing acceptable CSMA-CA random access schemes like IEEE 802.11 yield unfair and inefficient rates in wireless multi-hop networks. This misconception is based on works which study IEEE 802.11-scheduled multi-hop networks with TCP or in saturation conditions both of which grossly underutilize the available capacity that IEEE 802.11 provides, or use topologies which cannot occur in practice due to physical layer limitations.
Thursday, 08.28.08, 12:00 PM, CALIT2, Room 4004/06
On Universal Coding for Parallel Gaussian Channels
Maryam Modir Shanechi , MIT
Two classes of approximately universal codes are developed for parallel Gaussian channels whose state information is not available at the encoder. Both architectures convert the channel into a set of scalar additive white Gaussian noise (AWGN) channels to which good AWGN base codes can be applied, and both are layered schemes used in conjunction with successive interference cancellation to keep decoding complexity low...more >
Tuesday, 06.03.08, 3:00 PM - 4:00 PM, CSE 4140
Average-case hardness for NP
Andrej Bogdanov, Tsinghua University
The gold standard of difficulty for a computational problem is NP hardness.However, NP hard instances of problems are quite atypical. In practice, and in many theoretical settings as well, one sometimes
adopts the view that NP hard instances are so rare that they present no serious obstacle to the design of efficient algorithms. Yet experience tells us that some NP problems are intractable even on
typical instances...more >
Monday, 06.02.08, 12:00 PM, CALIT2, Room 3004
The Geometry of Ad Hoc Networks and its Impact on Performance
Martin Haenggi , University of Notre Dame
The node distribution in ad hoc and sensor networks is typically modeled as a stochastic point process. Due to its analytical tractability, the (homogeneous) Poisson point process (PPP) is widely popular. We give an overview of interference and outage results for the PPP, and we present an approach to extend these to more general point processes. Next we show how fading can be incorporated in the point process, which leads to a geometric interpretation of fading that permits a convenient characterization of single-hop connectivity and transport capacity...more >
Monday, 04.21.08, 11:00 AM - 12:00 PM, EBU-1, 6504
Testing Low Degree Polynomials over Small Prime Fields
Anindya Patthak , UC Riverside
Polynomials are very important objects in mathematics and theoretical computer science. Every map from a finite field to finite field is a polynomial map. Low degree polynomials are more important for small complexity and for better error correction capability. In this talk, I will present how to test whether a given function is a low degree polynomial over prime fields by querying randomly at few points...more >
Friday, 04.18.08, 11:00 AM - 12:00 PM, EBU 1, Room 6504
Efficient Algorithms for Active Learning
Claire Monteleoni , UC San Diego
The rapidly increasing abundance of data generated by internet transactions, satellite measurements, and environmental sensors, among other sources, creates new and urgent challenges for machine learning. My work on machine learning theory and algorithms is motivated by the problems posed by real-world data. This talk will focus on providing efficient algorithms for active learning, a rich model for learning when labels are missing...more >
Tuesday, 04.15.08, 11 - 12, EBU1, Room 2512
Robust architectures for next generation communication systems
Anand Sarwate, University of California, Berkeley
Researchers have developed a good understanding of the communication systems of the past decades by using random noise models. This has shaped code design as well as overall system architectures. In this talk, I will argue that these models are not appropriate for the challenges of the future systems, such as cognitive radio, ad-hoc networks, and sensor networks...more >
Monday, 04.07.08, 11:00 AM - 12:00 PM, EBU-I 6504
The posterior matching principle for optimal communication with feedback
Ofer Shayevitz, Tel-Aviv University
Feedback cannot increase the capacity of a memoryless channel. Nevertheless, feedback can sometimes significantly simplify the transmission scheme, so that capacity is achieved essentially without coding. This was demonstrated by the celebrated examples of Horstein (1963) for the binary symmetric channel (extendable to any DMC) and Schalkwijk-Kailath (1966) for the additive white Gaussian noise channel...more >
Monday, 03.31.08, 11:00 AM - 12:00 PM, EBU1, Room 6504
Information flow over wireless networks: a deterministic approach
Salman Avestimehr , UC Berkeley
How does information flow over wireless networks? Answer to this basic question is one of the most challenging problems in the field of wireless network information theory. From a practical point of view, the answer to this question will have a significant impact on the architectural design of future wireless systems. So far, the majority of research done in this area has been based on the classical additive Gaussian noise model for wireless channels...more >
Wednesday, 02.27.08, 10.30am - 11.30am, 4004/4006 (4th floor Atkinson)
Computing on Streams: New Results and Directions
Andrew McGregor, UCSD
Over the last ten years, the data stream model has become an active topic of research. I think there are two main reasons for this. First, it is a model that is applicable to a range of practical problems such as monitoring network traffic, query-planning in databases, designing I/O efficient algorithms for massive data sets, and aggregation in sensor networks...more >
Friday, 11.09.07, 1:30 PM - 2:30 PM, EBU 1, Room 4307
Finding low-rank matrices via convex optimization
Maryam Fazel, Caltech
In many engineering applications, notions such as order, complexity, or dimension of a model or design can be expressed as the rank of an appropriate matrix. If the set of feasible models or designs is convex, choosing the simplest model can be cast as a Rank Minimization Problem. For example, a low-rank matrix could correspond to a low-order controller for a plant, a low-degree statistical model for a random process, or an embedding in a low-dimensional space...more >
Monday, 10.22.07, 11 AM - 12 PM, Calit2, Room 4004
Degrees of Freedom and O(1) Capacity of Wireless Interference Networks
Syed Ali Jafar , UC Irvine
The talk will present new insights into the capacity of fully connected wireless networks with finite number of nodes through capacity approximations that are accurate to within a bounded constant for all SNR. While the best known outerbound for the K user interference channel states that there cannot be more than K/2 degrees of freedom, it has been conjectured that in general the constant interference channel with any number of users has only one degree of freedom...more >
Friday, 08.17.07, 2PM - 3PM, Calit2, Rm 4004
Capacity Approaching, Efficiently Decodable Lattice Codes
Meir Feder, Tel Aviv University
Lattice codes can achieve the capacity of the additive white Gaussian
noise channel.
However, the specifiic proposed lattice codes were either of finite
block length, or were
of random structure and require complex decoding to achieve good
performance. On the
other hand, in the recent years coding scheme that attain capacity and
are decoded efficiently
were proposed for finite alphabet channels, the most notable examples
are Low Density
Parity Check Codes (LDPC) and turbo codes...more >
Thursday, 07.26.07, 10 - 11, Calit2 Rm. 4004
On universal compression and classification of individual two-dimensional arrays
Jacob Ziv, The Technion, Israel
A common approach to data compression of two-dimensional arrays is
to first scan the array, thus mapping it into a one-dimensional
sequence, and then apply a data-compression algorithm for sequences.

It has been demonstrated that for individual arrays,
a space-filling Peano-Hilbert scan that is followed by LZ
data-compression algorithm for individual sequences is an
asymptotically optimal two-stage scheme...more >
Tuesday, 05.08.07, 1PM, TBD
Clustering using Correlation and Independence
Kamalika Chaudhuri, UC Berkeley
Clustering, a method of finding structure in unlabelled
data by grouping the data points into few groups based
on a similarity measure, has many applications in AI,
Physics and Biology. A simple theoretical model that captures clustering is
the problem of learning mixtures
of distributions. In this setting, one is given sample
points generated from a mixture of T distributions of
a certain type, and the goal is to recover these
distributions and classify the points correctly...more >
Monday, 05.07.07, 11:30, EBU-1 6504
Cooperative Diversity: Protocols and Analysis
Kambiz Azarian Yazdi, University of Notre Dame
In this talk, we overview several approaches to designing cooperative
transmission schemes. In particular, we differentiate between the relay,
broadcast (down-link), and multiple-access (up-link) scenarios and
propose schemes that efficiently utilize the cooperative diversity
available in the channel. We do so by re-examining the two basic
cooperation techniques (i...more >
Friday, 01.19.07, 2PM - 3PM, Calit 5004
Role of noisy feedback in communication
Young-Han Kim, UCSD
The role of perfect feedback in communication is relatively well understood. Feedback can dramatically reduce the probability of error, decrease communication delay, and simplify the system design. For example, the celebrated Schalkwijk-Kailath coding scheme achieves the capacity of additive white Gaussian noise channel with exponentially improved reliability...more >
Tuesday, 12.05.06, 11 - 12, CSE 4217
Estimation of probability distributions with maximum entropy -- incorporating generalized regularizations and modeling species habitats
Miroslav Dudik, Princeton University
Maximum entropy (maxent) approach, equivalent to
maximum likelihood, is a widely used method for
estimating probability distributions. However, when
trained on small datasets, maxent is likely to overfit.
Therefore, many smoothing techniques were proposed
to mitigate overfitting. In this talk, I will present a
unified treatment for a large and general class of
smoothing techniques including L1 and L2
regularization...more >
Monday, 12.04.06, 11 - 12, CSE 4217
Convex Repeated Games and Fenchel Duality
Shai Shalev-Shwartz, The Hebrew University
Several problems arising in machine learning, such as online learning and boosting, can be modeled as a convex repeated game. A convex repeated game is a two players game which is performed in a sequence of consecutive trials. At each trial of the game, the first player predicts a vector from a predefined set and then the second player responds with a loss function over the set...more >
Friday, 12.01.06, 11 AM - 12 PM, EBU-1 6504
Slepian-Wolf Coding over Broadcast Channels
Ertem Tuncel, UC Riverside
We discuss reliable transmission of a discrete memoryless source over a discrete memoryless broadcast channel, where each receiver has side information (of arbitrary quality) about the source unknown to the sender. When there are two receivers, the optimum coding strategy using separate and stand-alone source and channel codes is to build two independent binning structures and send bin indices using degraded message sets through the channel, yielding a full characterization of achievable rates...more >
Monday, 10.30.06, 1:30 - 2:30, EBU-1 4307
Bionic Human-Machine Interaction
Helen Meng, The Chinese University of Hong Kong
Bionics is a vastly interdisciplinary enterprise that draws inspirations from nature for engineering designs and technology development. Illustrative examples abound, ranging from automobile design, material science, to impressions from science fiction. This talk presents a characterization of bionic human-machine interfaces, in terms of (1) mimicking human forms; (2) supporting human-like functions and (3) augmenting human physical and cognitive abilities...more >
Wednesday, 08.16.06, 11 - 12, Calit2: Synthesis Center
On universal classification with limited memory: How to learn the most out of a training sequence?
Jacob Ziv, Technion–Israel Institute of Technology
Traditionally, the analysis of information processing systems is based on certain modeling of the mechanism that generates the observed data (e.g. being a realization of some ergodic process). Based on this a-priory model, a processor (e.g. a classifier, etc.), is then optimally designed. In practice, there are many cases where not enough a-priori information about this generating model is available and one must base the design of a classifier on the observed training data only, under some complexity constraints that the classifier must comply with....

Friday, 08.04.06, 11 - 12, EBU-1 Rm 4307
Golden Space-Time Trellis Coded Modulation
Emanuele Viterbo, Politecnico di Torino, Italy
In this talk we present a trellis coded modulation scheme based on the Golden code. Set partitioning with increasing minimum determinant and coset coding of the Golden code are designed to optimize the....

Thursday, 06.15.06, 2 - 3, EBU1-6504
On coded and uncoded transmissions of Gaussian sources over Gaussian channels
Amos Lapidoth, ETH, Zurich
We consider the problem of transmitting a Gaussian source over an
additive white Gaussian noise channel and the problem's extension to
the transmission of correlated Gaussian sources over a multiple-access
channel. We focus on the mean squared-error criterion.

For the former problem the classical approaches are based on the
source-channel separation theorem or on Goblick's surprisingly simple
uncoded transmission scheme...more >
Wednesday, 05.31.06, 11:00 - 12:00, EBU-1 4307
Market-based Approaches for Efficient Allocation of Network Resources
Rahul Jain, UC Berkeley
Many systems are characterized by complex (and often strategic) interactions between subsystems. Such systems occur in communication networks, power networks, wireless and sensor networks, etc. The strategic interactions between such subsystems often involve economic issues. This necessitates market-based algorithms for distributed control and optimization...more >
Tuesday, 05.30.06, 2:00 - 3:00, EBU1 4307
CDMA Reverse Link Interference Cancellation
Jilei Hou, Qualcomm
This talk gives the principles and practice of how interference cancellation can be implemented on the CDMA reverse link of modern cellular systems. First, some simple information theoretic analysis is given. Link level analysis and simulations determine the quality of multipath channel estimation techniques. Network level simulations over a wide range of channels confirm that interference cancellation offers significant capacity gains across users, while maintaining the system link budget and stability...more >
Thursday, 05.18.06, 3:00 - 4:00, Calit Auditorium
How to structure, analyse and apply molecular interaction
Sydney Brenner, Molecular Sciences Institute, Salk Institute
Sydney Brenner received the 2002 Medicine Nobel Prize for establishing the C. elegans as an experimental model organism and for linking genetic analysis to cell division and organ development and aging. His many other achievements include the discovery of Messenger RNA. He will present a broad interest talk on the interaction between molecular genomics, structural functionality, and cellular molecular communication...more >
Wednesday, 05.17.06, 3:00 - 4:00, Calit Synthesis Room
Graphs, colorings and beyond in comparative genomics
Sagi Snir, UC Berkeley
Comparative genomics seeks to explore characteristic patterns of a set of organisms by comparing common features of the given organisms. Computational methods are a significant part in this type of discipline. In this talk I will describe the use of colored graphs to solve two problems in comparative genomics:

1. Micro-indels are small insertion or deletion events (indels) that occur during genome evolution...more >
Monday, 05.15.06, 11:00 - 12:00, Calit2 MPR
Streams and samples: new directions for processing massive data sets
Andrew McGregor, University of Pennsylvania
Data streams are ubiquitous. Sometimes data is processed as a stream by necessity; when estimating the statistics of network traffic flowing past a router, it is not feasible to store all the data and run conventional algorithms....
Thursday, 05.04.06, 10:00 am - 11:00 am, EBU1 4307
Reliable Communication in the Presence of Side Information
Tie Liu, University of Illinois at Urbana-Champaign
In many network communication problems including broadcast channel and distributed source coding, there is a natural strategy of converting the problem into a point-to-point problem and a series of side-information problems: one user does its own, and the rest of users treat messages sent from previous users as side information. My research studies such communication problems in two ways...more >
Friday, 04.14.06, 10:00 - 11:00, EBU1 - 4307
Efficient Matching for Recognition and Retrieval
Kristen Grauman, MIT
Local image features have emerged as a powerful way to describe images of objects and scenes. Their stability under variable image conditions is critical for success in a wide range of recognition and retrieval applications. However, comparing images represented by their collections of local features is challenging, since each set may vary in cardinality and its elements lack a meaningful ordering. Existing methods compare feature sets by searching for explicit correspondences between their elements, which is too computationally expensive in many realistic settings.
Tuesday, 04.11.06, 10:00 - 11:00, EBU1 - 4307
Role of Feedback in Communication
Young-Han Kim , Stanford University
Feedback plays a pivotal role in control. Without feedback, even a small amount of error can unstabilize control systems in stochastic environments. Communication systems, in which one ``controls' another's state of knowledge, are notable exceptions. By encoding data with a forward error correcting code in long blocks, one can communicate reliably over a noisy channel without any feedback, as shown by Shannon.