all by date all by type workshops courses colloquium seminars lunches
Lunchtime informal seminar
Wednesday, 06.04.08, 11:30am - 1:00pm, 4004/06 CalIT2
Young-Han Kim, ECE, UCSD
Shannon's mutual information arises as the canonical answer to a variety of questions such as communication (channel coding theorem), data compression (rate distortion theorem and Gallager's minimax redundancy theorem), and investment (Kelly's growth-optimal portfolio). In this talk, we discuss how causality affects these problems and introduce Massey's directed information as a natural answer...more >
Wednesday, 05.28.08, 12 - 1.30pm, 4004/4006 (4th floor Atkinson)
Entry wise bounds for eigenvectors of random graphs
Pradipta Mitra, Yale
I will talk about a certain spectral property of random graphs. The
goal is to investigate what the first eigenvector of the adjacency
matrix of a random graph looks like. Let G be a G_{n, p} random graph
on n vertices. Also, let A be the adjacency matrix of G, and v_1 be
the first eigenvector of A. I will show a nearly optimal bound on
|v_1(i) - frac{1}{sqrt{n}}| that holds for all i in [n], with high
probability...more >
Wednesday, 05.07.08, 12pm - 1:00pm, 4004/06 CalIT2
Uniform Direct Product Theorems: Simplified, Optimized, and Derandomized
Russell Impagliazzo, CSE, UCSD and IAS
The Direct Product Theorem for circuits says,
``If no small circuit can compute Boolean function
$f(x)$ with probability at least $1-delta$ for a random
$x$, then no circuit of a slightly smaller size can
compute $f(x_1)...f(x_k)$ with even a small probability of
success.' While highly intuitive, the proof of the direct
product theorem is non-trivial...more >
Wednesday, 04.16.08, 12pm - 1.30pm, 4004/4006 (4th floor Atkinson)
Interference Alignment and the Capacity of Wireless Networks
Syed Ali Jafar, UC Irvine
We use the idea of interference alignment to characterize the capacity of wireless interference networks with accuracy approaching 100% at high SNR. The talk covers three main results.

(1) We show that wireless interference networks are not fundamentally interference limited. At high SNR, inspite of the interference, every user
in an interference network can achieve a rate close to 1/2 of his interference-free capacity...more >
Wednesday, 03.05.08, 12pm - 1.30pm, 4th Floor Conference Room CALIT2
Functional Sparsity
John Lafferty, School of Computer Science, Carnegie Mellon University
Substantial progress has recently been made on understanding the
behavior of sparse linear models in the high dimensional setting,
where the number the variables can greatly exceed the number of
samples. This problem has attracted the interest of multiple
communities, including applied mathematics, signal processing,
statistics, and machine learning...more >
Wednesday, 02.27.08, 12pm - 1.30pm, 4th Floor Conference Room CALIT2
Learning Classifiers from Only Positive and Unlabeled Data
Keith Noto, UCSD
The input to an algorithm that learns a binary classifier consists of two sets
of examples. Normally, one set contains positive examples of a concept, and
the other set contains negative examples. However, it is often the case that
the available input consists of an incomplete set of positive examples, and a
set of unlabeled examples, some of which are positive and some of which are
negative...more >
Wednesday, 02.20.08, 12:00pm - 1:00pm, 4004/06 (4th floor conference room), CALIT2
Designing a content-based music search engine
Gert Lanckriet, ECE,UCSD
If you go to or Apple Itunes, your ability to search for new music will largely be limited by the `query-by-metadata' paradigm: search by song, artist or album name. However, when we talk or write about music, we use a rich vocabulary of semantic concepts to convey our listening experience. If we can model a relationship between these concepts and the audio content, then we can produce a
more flexible music search engine based on a 'query-by-semantic-description' paradigm...more >
Wednesday, 02.13.08, 12pm - 1.30pm, 4th Floor Conference Room CALIT2
Communicating Delay-Sensitive and Bursty Information over an Outage Channel
Tara Javidi, UCSD
In this talk, we consider the classic (cross-layer) queue-channel optimization problem for bursty and delay-sensitive information sources. In particular, we are interested in communications over
outage-limited channels (with no feedback) when the number of bits that arrive at the transmitter during any time slot is random but the delivery of bits at the receiver must adhere to a strict delay constraint...more >
Wednesday, 02.06.08, 12pm - 1.30pm, 4004/4006 (4th floor Atkinson)
Efficient reductions among lattice problems
Daniele Micciancio, CSE, UCSD
We give various deterministic polynomial time reductions among approximation problems on point lattices. Our reductions are both efficient and robust, in the sense that they preserve the rank of the lattice and approximation factor achieved. Our main result shows that for any g >= 1, approximating all the successive minima of a lattice (and, in particular, approximately solving the Shortest Independent Vectors Problem, SIVPg) within a factor g reduces under deterministic polynomial time rank-preserving reductions to approximating the Closest Vector Problem (CVP) within the same factor g...more >
Wednesday, 01.16.08, 12 - 1.30, 4th Floor Conference Room CALIT2
Wireless ad-hoc networks: from probability to physics via information theory
Massimo Franceschetti, ECE, UCSD
In this interdisciplinary talk we consider the problem of determining the information capacity of a network of wireless transmitters and receivers and try to draw some non-trivial connections between spatial stochastic processes, physics, and information theory.

We present the following main result of statistical physics flavor: By distributing uniformly at random an order of n nodes wishing to establish pair-wise independent communications inside a domain of size of the order of n, the per-node information rate must follow an inverse square-root of n law, as n tends to infinity...more >
Tuesday, 06.12.07, 1 - 2, CSE 4140
A Topic in Coding Theory
Roxana Smarandache, San Diego State University
Tuesday, 06.05.07, 1 - 2, CSE 4140
Antenna Synthesis and Channel Capacity
Marco Migliore
In this lecture the problem of antenna synthesis is reviewed from an information-theoretic perspective. Antennas are characterized by their ability to convey information in a communication system and different classes of antennas, e.g. “classic” antennas, adaptive antennas and MIMO antennas, are analysed in a unified framework using the concept of the number of degrees of freedom of the field...more >
Friday, 06.01.07, 1 - 2, CSE 2109
A physical approach to multiple antenna communication
Massimo Franceschetti, UCSD
In multiple antenna (MIMO) systems communication is performed through the act of propagation of electromagnetic (EM) waves. EM research typically focuses on the physical aspects of propagation, while information theory (IT) focuses mainly on the communication aspects, often considering random channel models. In this talk we attempt to address the gap between these two approaches...more >
Tuesday, 05.29.07, 1 - 3.30, CSE 4140
A Stochastic Control Approach to Variable Length Menus in P300 Neural Communication Prostheses
Todd Coleman, University of Illinois at Urbana-Champaign
The P300 neural communication prosthesis allows an individual to type words from an on-screen menu by recording visually evoked potentials related to the user’s intention. Typing rates are affected in part by two sources of uncertainty: (a) noise in the P300 signal, and (b) statistical language structure. Early system designs focused on classification to address P300 noise...more >
Wednesday, 05.23.07, 1 - 2, CSE 2109
Distance metric learning for large margin nearest neighbor classification
Lawrence Saul, UCSD
The accuracy of k-nearest neighbor (kNN) classification depends in general on the metric used to compute distances between different inputs. We show how to learn a Mahanalobis distance metric for kNN classification from labeled examples. The metric is trained with the goal that the k-nearest neighbors always belong to the same class while examples from different classes are separated by a large margin...more >
Tuesday, 04.17.07, 12 - 1, CSE 4140
Using Random Projections to Learn the Distribution of Data Concentrated on a Low Dimensional Manifold
Yoav Freund, UCSD
In this lunchtime informal seminar, Yoav will discuss some recent work and present some open problems.
Tuesday, 04.10.07, 12 - 1, CSE 4140
Repeat classification and fragment assembly.
Pavel Pevzner, UCSD
In this inagural lunchtime seminar, Pavel will discuss his research and present some open problems.
Monday, 10.30.06, 12 - 1, 4004/4006 (4th floor Atkinson)
The physical layer of WiMedia OFDM UWB
Rabih Chrabieh
The WiMedia Ultra-Wideband system uses OFDM, rather than ultra-narrow impulses, to fill up a vast amount of spectrum, more than 500 MHz, with high data rate transmissions at short distances, and very low power. In a nutshell, it is like a high data rate Bluetooth. We will present the physical layer of this standard with some references to the MAC layer...more >