| ||||||||||

Upcoming |
||||||||||

Gone |
||||||||||

SeminarWednesday, 12.10.14, 3PM - 4PM, Jacobs Hall, Room 4309 Fixed- and variable-length data compression at finite blocklengthVictoria Kostina, Caltech In data compression, a block of source symbols is compressed down into a smaller length string, while ensuring that the original block can be recovered from that encoded string, either exactly or approximately. Identifying the optimum rate-fidelity tradeoffs achievable in principle, regardless of the complexity of the code, is the subject of information-theoretic interest in data compression...more > | ||||||||||

SeminarWednesday, 12.03.14, 3PM - 4PM, Atkinson Hall, Room 4004 Matroids and NetworksKen Zeger, UC San Diego A tutorial on matroids and their connection to network coding is given. Specifically, a method for constructing networks from known matroids is described. Such matroidal networks retain certain algebraic properties from their parent matroid. | ||||||||||

SeminarWednesday, 11.19.14, 3PM - 4PM, Atkinson Hall, Room 4004 Distributed Variable-Length Limited Feedback in Cooperative Wireless NetworksHamid Jafarkhani, UC Irvine We study the role of limited feedback in cooperative wireless networks. Our emphasis is on the distributed nature of the network and the need for simultaneous transmission from different users. We address the effect of interference in such a distributed network and the corresponding challenges in designing reliable systems. Then, we discuss the design of quantized feedback in wireless relay-interference networks. Finally, we show that the performance of the full-CSIT systems can be achieved asymptotically using variable-length quantizers with very low feedback rates. | ||||||||||

SeminarFriday, 11.14.14, 2PM - 3PM, Atkinson Hall, Room 4004 Mathematical Foundations of the Next-Generation Robust and Resource-Efficient Information Systems: Algorithms and Code DesignsLara Dolecek, UC Los Angeles We are witnessing an unprecedented explosion in data generation. To make a full use of this data deluge, information systems must be architected in a way that makes them robust and resource-efficient. Yet, many existing design metrics that were once appropriate fail to meet the scaling demands of the modern-era information systems. To address these growing challenges, our work focuses on the development of the mathematical foundations of the emerging information systems. Our models not only offer a systematic way to address strict design requirements, but they also advance the available analytical toolbox of coding theory and algorithms. In this talk, I will review several of our recent results, focusing on the complementary topics that span channel coding for reliable storage and memories, data synchronization methods, and fault-tolerant information processing algorithms. Our methods have rigorous mathematical descriptions that are rooted in advanced algebraic and combinatorial tools, offer firm performance guarantees, and thus meet the needs of modern information systems. I will conclude the talk by highlighting additional future directions and emerging applications. | ||||||||||

SeminarWednesday, 11.12.14, 3PM - 4PM, Atkinson Hall, Room 4004 Approximate Capacity of the Energy Harvesting Communication ChannelAyfer Ozgur, Stanford University Recent advances in energy harvesting technologies enable wireless devices to harvest the energy they need from the natural resources in their environment. This development opens the exciting new possibility to build wireless networks that are self-powered, self-sustainable and which have lifetimes limited by their hardware and not the size of their batteries. However, communication with energy-harvesting devices has a number of aspects which make it fundamentally different from conventional battery-powered communication. In conventional systems, energy (or power) is a deterministic quantity continuously available to the transmitter and communication is typically constrained only in terms of average power. In harvesting systems, the energy available for communication is a stochastic rather than a deterministic process which has memory and is input-dependent. In this talk, we will investigate the information-theoretic capacity of this non-traditional communication system and provide an approximate characterization within a constant number of bits independent of the system parameters. | ||||||||||

SeminarFriday, 10.31.14, 3PM - 4PM, Atkinson Hall, Room 4004 Theory and Applications of Interactive Information TheoryProf. Todd P. Coleman, UC San Diego In this talk, we discuss two topics of active learning and causal inference. In the former, we pose the problem of active learning from a team decision theory viewpoint - using the lens of "two agents cooperating to achieve a common goal". With this, we make a connection with reliable communication of an analog message point over a noisy channel with feedback and develop optimal schemes in arbitrary dimensions using the theory of optimal transportation. We demonstrate the motivation of this approach with brain-machine interfaces, and elucidate how the importance of developing systems that are optimal yet are amenable for easy human use gives rise to new mathematical developments. In terms of causal inference, we consider the problem of simultaneously observing many time series and attempting to identify the causal interactions amongst them. We re-visit Granger's statistical notion of causality and generalize it to arbitrary modalities using a sequential prediction viewpoint, where the directed information arises as the unique embodiment. By establishing a connection with coupled differential equations, we demonstrate an equivalence between directed information graphs and minimal generative graphs. We use recent results on robust identification of such graphs subject to uncertainty on pairwise estimates to elucidate interacting neural processes whose causal interactions co-vary with brain function and disease. | ||||||||||

SeminarThursday, 10.23.14, 3PM - 4PM, Atkinson Hall, Room 4004 New advances on the log-rank conjectureShachar Lovett, University of California, San Diego New advances on the log-rank conjecture | ||||||||||

SeminarWednesday, 10.15.14, 3PM - 4PM, Atkinson Hall, Room 4004 Converse Bounds for Information Theoretic CryptographyHimanshu Tyagi, UC San Diego Computationally secure cryptography is computationally expensive to implement. For data security over the internet, this limitation was circumvented by relying on the rapid improvement in the computation power of processors. However, as we move into the era of internet of things where data is handled by several small devices with limited computational capability, there is a pressing need for computationally economic means of data security. When the parties involved have access to correlated randomness, information theoretic methods of cryptography provide such economic means of attaining secrecy; the availability of formal proofs of security is an added bonus. In this talk, we will present a technique for establishing converse bounds (impossibility results) for information theoretically secure secret key generation, oblivious transfer, and bit commitment. A distinguishing feature of our bounds is their validity for arbitrary distributions of the observations, which is in contrast to the traditional asymptotic analysis in information theoretic security. This is joint work with Shun Watanabe. | ||||||||||

SeminarThursday, 06.26.14, 2:00 PM - 2:45 PM, Room 4004, Atkinson Hall Effective Secrecy: Reliability, Confusion and StealthJie Hou, Technische Universität München A security measure called effective security is defined that includes strong secrecy and stealth communication. Effective secrecy ensures that a message cannot be deciphered and that the presence of meaningful communication is hidden. To measure stealth we use resolvability and relate this to binary hypothesis testing. Results are developed for wire-tap channels and broadcast channels with confidential messages...more > | ||||||||||

SeminarTuesday, 06.17.14, 11 a.m - 12 p.m., Jacobs Hall, Room 6504 Flexible Fork-Join NetworksRamtin Pedarsani, UC Berkeley We consider a general flexible fork-join processing network, in which jobs are modeled as directed acyclic graphs with nodes representing tasks, and edges representing precedence constraints among tasks. Both servers and tasks are flexible in the sense that each task can be processed by several servers, which in turn can serve multiple task types. The system model is motivated by the problem of efficient scheduling of both sequential and parallel tasks in a flexible processing environment, which arises in many application areas such as data centers...more > | ||||||||||

SeminarWednesday, 06.04.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Principal Component Analysis with Structured FactorsAndrea Montanari , Stanford University Many modern data sets are naturally presented as data matrices. Examples include recommendation systems (with rows corresponding to products, and columns to customers), hyper-spectral imaging (with rows corresponding to pixels, and columns to frequencies), gene expression data (with rows corresponding to patients, and columns to genes). Principal component analysis aims at reducing the dimensionality of such datasets by projecting samples in a few directions of maximum variability...more > | ||||||||||

SeminarWednesday, 05.28.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Plug and play operation of microgrids: Objectives and StrategiesFlorian Dörfler , UCLA Microgrids are low-voltage electrical distribution networks, heterogeneously composed of distributed generation, storage, load, and managed autonomously from the larger transmission network. Modeled after the hierarchical control architecture of power transmission systems, a layering of primary, secondary, and tertiary control has become the standard operation paradigm for microgrids...more > | ||||||||||

SeminarWednesday, 05.14.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Compute-and-forward: an explicit link between finite field and Gaussian interference networks This talk overviews the compute-and-forward strategy, which exploits the interference property of the wireless channel to achieve higher end-to-end rates in a network. The key idea is that users should decode linear combinations of the transmitted messages over an appropriate finite field. This is a departure from classical information-theoretic frameworks which tend to either to decode interfering messages in their entirety or treat them as noise...more > | ||||||||||

SeminarWednesday, 05.07.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Quantization and Encoding of Linear MeasurementsRayan Saab, UCSD In the digital era, to acquire a signal one must not only sample (or measure) it but also quantize (or digitize) the measurements. One popular family of quantization methods, known for its robustness to errors and ability to act progressively on the measurements is Sigma-Delta quantization. In this talk, we discuss some recent results on the Sigma-Delta quantization of generalized linear measurements, both in the frame setting (where one has more measurements than the ambient dimension of the signal) and in the compressed sensing setting (where one has fewer measurements, but the signal is sparse)...more > | ||||||||||

SeminarWednesday, 04.30.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Detecting Emotional Contagion in Massive Social NetworksLorenzo Coviello, UCSD Online social networks are an invaluable source of data for the study of social phenomena related to influence and contagion. In most cases, running large-scale experiments on these online platforms is infeasible (e.g., it requires close collaboration with private companies, or the company wants to offer an homogeneous experience to all its users) or undesirable (for the potential interaction of users assigned to different experimental treatments), and researchers have to rely on observational data, which poses inherent difficulties in assessing causality...more > | ||||||||||

SeminarWednesday, 04.23.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Load Balancing in Large GraphsVenkat 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 > | ||||||||||

SeminarFriday, 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 > | ||||||||||

SeminarWednesday, 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 > | ||||||||||

SeminarWednesday, 04.02.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Modulation and Coding Techniques for Enhancing Flash Memory EnduranceEyal En Gad, Caltech Motivation: Current ﬂash 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 > | ||||||||||

SeminarTuesday, 03.25.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Coverage and Percolation in Random Geometric GraphsAmites 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 > | ||||||||||

SeminarWednesday, 03.12.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Cooperative Schemes for Real-Time Applications on Mobile DevicesAthina 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 > | ||||||||||

SeminarThursday, 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 limitationsLuca 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 > | ||||||||||

SeminarWednesday, 02.26.14, 3:00 PM - 4:00 PM, Atkinson Hall, Room 4004 Towards Clinically Viable Neural Prosthetic SystemsVikah 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 > | ||||||||||

SeminarWednesday, 02.19.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Brownian Motion Through Invertible Matrices in High DimensionTodd Kemp, UCSD | ||||||||||

SeminarFriday, 02.07.14, 3:00 p.m. - 4:00 p.m., Atkinson Hall, Room 4004 Non-Asymptotic Analyses on Problems with Markovian MemoryShun 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 > | ||||||||||

SeminarWednesday, 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 NetworksKobi 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 > | ||||||||||

SeminarWednesday, 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 > | ||||||||||

SeminarWednesday, 01.22.14, 3PM - 4PM, Atkinson Hall (Calit2) 4004 Designing Optimal Resource Sharing in the Long RunMihaela van der Schaar, Electrical Engineering, UCLA Designing Optimal Resource Sharing in the Long Run | ||||||||||

SeminarWednesday, 01.15.14, 3PM - 4PM, Atkinson Hall (Calit2) 4004 Catching Up Faster by Switching Sooner: Improved Data Compression and Statistical Inference with Nested ModelsPeter Grünwald, CWI Amsterdam & Leiden University Catching Up Faster by Switching Sooner: Improved Data Compression and Statistical Inference with Nested Models | ||||||||||

SeminarWednesday, 12.11.13, 11 a.m - 12 p.m., Jacobs Hall, Room 6504 On Cooperative Radio Resource Allocation techniques based on Game TheoryEphi Zehavi, Bar Ilan University On Cooperative Radio Resource Allocation techniques based on Game Theory | ||||||||||

SeminarMonday, 11.18.13, 3PM - 4PM, Atkinson Hall (Calit2) 4004 Cognitive Access Policies under a Primary ARQ process via Forward-Backward Interference CancellationMichele Zorzi, Department of Information Engineering, University of Padova Cognitive Access Policies under a Primary ARQ process via Forward-Backward Interference Cancellation | ||||||||||

SeminarFriday, 11.15.13, 3PM - 4PM, Atkinson Hall (Calit2) 4004 VIP: A Framework for Joint Dynamic Forwarding and Caching in Named Data NetworksEdmund Yeh, Electrical and Computer Engineering, Northeastern University VIP: A Framework for Joint Dynamic Forwarding and Caching in Named Data Networks | ||||||||||

SeminarWednesday, 11.13.13, 3PM - 4PM, Jacobs Hall, Room 4309 Resource Sharing in Stochastic NetworksRuth J. Williams, Dept. of Mathematics, UCSD Resource Sharing in Stochastic Networks | ||||||||||

SeminarTuesday, 11.05.13, 3PM - 4PM, Jacobs Hall, Room 4309 CAUSAL ERASURE CHANNELSRaef Bassily, Dept. of Computer Science & Engineering, Penn State University CAUSAL ERASURE CHANNELS | ||||||||||

SeminarWednesday, 10.30.13, 3PM, Jacobs Hall, Room 4309 Frames and Spherical Codes: where Slepian meets Fourier and GaloisBabak Hassibi, Department of Electrical Engineering, CALTECH Babak Hassibi | ||||||||||

Friday, 10.25.13, 8:30 AM - 5:00 PM, Atkinson Hall Auditorium CWC Research ReviewCWC Research Review | ||||||||||

SeminarWednesday, 10.23.13, 3PM, Jacobs Hall, Room 4309 Compression for Similarity QueriesTsachy Weissman, Dept. of Electrical Engineering, Stanford University Compression for Similarity Queries | ||||||||||

Monday, 10.21.13, 2PM - 3PM, Jacobs Hall, Booker Conference Room 2512 Kandou Codes for Chip-to-Chip CommunicationAmin Shokrollahi, Kandou Bus & EPFL Kandou Codes for Chip-to-Chip Communication | ||||||||||

Wednesday, 10.16.13, 3PM - 4PM, Jacobs Hall, Room 4309 From Stochastic Control to Feedback CodesTara Javidi, Electrical & Computer Engineering From Stochastic Control to Feedback Codes | ||||||||||

SeminarWednesday, 10.09.13, 3PM - 4PM, Jacobs Hall, Booker Conference Room 2512 Selfish routing: networks, games, and individual choiceProfessor Ilze Ziedins, University of Auckland Selfish routing: networks, games, and individual choice | ||||||||||

SeminarFriday, 09.20.13, 10AM - 11AM, Jacobs Hall, Booker Conference Room 2512 Integer-forcing for channels, sources and ADCsOr Ordentlich, Tel Aviv University Integer-forcing for channels, sources and ADCs | ||||||||||

WorkshopFriday, 09.13.13, Room TBD test admin workshop | ||||||||||

SeminarTuesday, 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 | ||||||||||

SeminarThursday, 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 AntennasMartin Haardt, Ilmenau University of Technology, Germany Efficient Two-Way Relaying Schemes for Amplify and Forward Relays with Multiple Antennas | ||||||||||

SeminarWednesday, 05.22.13, 10 AM - 11 AM, Jacobs Hall, Room 2512 (Booker Conference Room) Topological Interference ManagementSyed Ali Jafar , UC Irvine W..more > | ||||||||||

SeminarMonday, 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 | ||||||||||

SeminarTuesday, 04.09.13, 11:00am - 12:00pm, Calit2, Atkinson Hall, Room 4004 Variable-Length Coding with Feedback: Finite-Length Analysis and OptimizationTsung-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. | ||||||||||

SeminarTuesday, 03.12.13, 11:00am - 12:00pm, Jacobs Hall, Room 2512, Henry G. Booker Conference Suite From Likelihood Filtering to Quantum ProbabilitiesHans-Andrea Loeliger, ETH Zurich From Likelihood Filtering to Quantum Probabilities | ||||||||||

SeminarFriday, 02.01.13, 3:30pm - 4:30pm, Jacobs Hall, Room 2512, Henry G. Booker Conference Suite Integration of Sensing, Communication, and Navigation in Mobile NetworksYasamin Mostofi, University of California, Santa Barbara In this talk, I develop a foundation for the integration of sensing, communication and navigation in mobile networks. | ||||||||||

SeminarThursday, 01.10.13, 4:00pm - 5:00pm, AP&M Building, Room 6402 Near-Optimal Quantization and Encoding for Oversampled SignalsRayan 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. | ||||||||||

SeminarWednesday, 11.28.12, 2:00pm - 3:00pm, Jacobs Hall, Room 4309 Two Network Problems and Their Application to Streaming CodesTracey 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. | ||||||||||

SeminarMonday, 11.19.12, 11 AM - 12 PM, Atkinson Hall, Room 4004 The Art of Gambling in a Team: Multi-player multi-armed banditsRahul 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 11.16.12, 11 AM - 12 PM, Jacobs Hall, Room 2512 (Booker Conference Room) What Risks Lead to Ruin? Venkat Anantharam, UC Berkeley Insurance transfers losses from the insuree to the insurer for a price per unit time, the premium. The pace of modern technology throws up scenarios where it is difficult to have confidence about what the loss distribution is. For instance, how would one insure potential losses incurred by entities operating on the Internet? Nevertheless, insurance has many benefits: by aggregating risk, it allows for more risk-taking by innovators...more > | ||||||||||

ECE/ITA ColloquiumThursday, 11.15.12, 3:00 PM - 4:00 PM, Jacobs Hall, Room 2512 (Booker Conference Room) Empirical Processes, Typical Sequences and Coordinated Actions Maxim Raginsky, UIUC Recent work by Cuff, Permuter and Cover on coordination via communication has revealed a fascinating aspect of strongly typical sequences --- they can be thought of as a means of reproducing relative frequencies of symbols emitted by stationary memoryless sources using finite communication resources. This viewpoint has a number of useful and far-reaching implications in such settings as distributed control and decision-making, network security, and statistical learning...more > | ||||||||||

SeminarThursday, 11.15.12, 10 a.m - 11 a.m, Applied Physics & Mathematics Building (AP&M), Room 6402 A toy limit order bookElena 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 11.09.12, 10 a.m - 11 a.m, Jacobs Hall, Room 2512 (Booker Conference Room) The Genetic Codes Governing Gene RegulationBrendan Frey, University of Toronto In September, the international ENCODE consortium reported that 80% of human genome sequence is used to control the expression of genes, which comprise only 1% of the genome. However, it is not yet clear how those elements combine to form the logic circuits that dictate gene expression in response to the cellular environment. I'll review different approaches to inferring such 'regulatory codes' and then I'll focus on a statistical method, where codes are inferred using gene expression data for thousand of genes, dozens of different conditions and multiple species...more > | ||||||||||

SeminarThursday, 11.08.12, 2:00 PM - 3:00 PM, Jacobs Hall, Room 2512 (Booker Conference Room) Modeling Random Access in Underwater Acoustic NetworksPaolo Casari, University of Padova, Italy T..more > | ||||||||||

SeminarFriday, 11.02.12, Atkinson Hall CWC SeminarIf you would like to attend, please register by Wednesday 10/31 Morning presentations8: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 > | ||||||||||

SeminarThursday, 11.01.12, 2pm - 3pm, Calit2 Atkinson Hall 4004 Lossy Compression for BigData: First StepsDr. 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. | ||||||||||

SeminarFriday, 10.26.12, 2:00pm, Jacobs Hall, Room 4309 Towards Computational Sensing through large number of Networked SensorsProf. 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 > | ||||||||||

SeminarThursday, 10.25.12, 3:00 PM - 4:00 PM, Jacobs Hall, Room 2512 (Booker Conference Room) Three Open Problems in Network CommunicationMichael 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 > | ||||||||||

SeminarThursday, 10.04.12, 10 a.m - 11 a.m, Applied Physics & Mathematics Building (AP&M), Room 6402 Queue-Size Scaling in Switched NetworksDevavrat 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 > | ||||||||||

SeminarTuesday, 08.14.12, 11:00 am - 12:00 pm, Jacobs Hall, Room 4309 Long Range Dependent Markov ModelsBarlas 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 sufﬁcient 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 ﬁelds of information theory, queuing networks, and ﬁnance. | ||||||||||

SeminarFriday, 06.15.12, 11:00am - 12:00pm, Atkinson Hall (Calit2), Room 4004 ITA Seminar: On q-ary Antipodal Matchings and ApplicationsDr. 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.) | ||||||||||

ECE/ITA ColloquiumMonday, 06.11.12, 11 AM - 12 PM, Jacobs Hall, Room 4309 Data Compression and SecrecyPrakash Narayan, University of Maryland, College Park The multiterminal data compression problem of attaining omniscience and the secrecy problems of secret key generation and secure computing might suggest contrasting communication requirements. In fact, they are innately coupled. In this talk, we discuss connections between omniscience attainment by multiple terminals which observe separate but correlated signals, and secret key generation and secure function computation by those terminals, all in a distributed manner...more > | ||||||||||

ECE/ITA ColloquiumWednesday, 05.30.12, 11 AM - 12 PM, Jacobs Hall, Room 4309 On Equivalence, Dependence, and Delay: Results from a Simple Tool for Information TheoryMichelle Effros, Caltech The expansion of information theory from the study of very small networks to the understanding of extremely large networks is often viewed as both critically important and insurmountably difficult. Nonetheless, many general properties of large networks can be derived using very simple tools. This talk focuses on a reduction strategy borrowed from CS theory, exploring a few simple applications and their implications for understanding the nature of noise, the impact of dependence, and the consequences of delay for reliable communications in large (and small) communication networks...more > | ||||||||||

SeminarWednesday, 05.23.12, 11 AM - 12 PM, Atkinson Hall, Room 4004 Error Correcting Codes for Distributed ControlRavi 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 > | ||||||||||

SeminarMonday, 04.30.12, 3:00 pm - 4:00 pm, Jacobs Hall, Room 2512, Henry G. Booker Conference Suite On Source-Channel Communication in NetworksJun 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. | ||||||||||

ECE/ITA ColloquiumFriday, 04.20.12, 11 AM - 12 PM, Jacobs Hall, Room 2512 (Booker Conference Room) Optimal Power Flow and Demand ResponseSteven Low, Caltech Optimal power flow (OPF) problems determine the most efficient power generations, reactive powers for voltage support, or demand response. They are well-known to be nonconvex and hence NP hard. In the first part of the talk, we propose exact relaxations that can be solved efficiently. We prove that, if the network is radial (tree), then a semidefinite relaxation of OPF is always exact, provided the constraints on power flows satisfy a simple pattern. Using the branch flow model, we propose another simple conic relaxation to OPF, and prove that it is exact for radial networks. For mesh networks, we provide an exact condition under which the relaxation can is exact. We propose a simple method to convexify a mesh network using phase shifters so that OPF for the convexified network can always be solved efficiently for a globally optimal solution. We prove that convexification requires phase shifters only outside a spanning tree of the network graph. In the second part of the talk, we describe a simple model that integrates two-period electricity markets, uncertainty in renewable generation, and real-time dynamic demand response. A load serving entity decides its day-ahead procurement to optimize expected social welfare a day before energy delivery. At delivery time when renewable generation is realized, it coordinates with users, in a decentralized manner, to manage load and purchase real-time balancing power in the real-time market, if necessary. We derive the optimal day-ahead decision, propose real-time demand response algorithm, and study the effect of volume and variability of renewable generation on the optimal social welfare. (Joint work with Subhomesh Bose, Mani Chandy, Masoud Farivar, Dennice Gayme, Libin Jiang, Javad Lavaei, Caltech, and Chris Clarke, SCE.) | ||||||||||

SeminarTuesday, 02.14.12, 10:30 a.m - 11:30 a.m, Jacobs Hall, Room 2512 (Booker Conference Room) Compressive Depth Acquisition Cameras: Principles and DemonstrationsVivek 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 problems. | ||||||||||

WorkshopSunday, 02.05.12 - Friday, 02.10.12, Catamaran Hotel and Resort, San Diego 7^{th} Information Theory and Applications Workshop | ||||||||||

SeminarMonday, 01.30.12, 3:00 PM - 4:00 PM, Jacobs Hall, Room 2512 (Booker Conference Room) Algorithmic Phase TransitionsDimitris 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 > | ||||||||||

SeminarFriday, 01.27.12, 11 AM - 12 PM, Atkinson Hall, room 4004 Load balancing for dynamically scalable web servicesYi Lu, UIUC 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 > | ||||||||||

SeminarWednesday, 01.25.12, 11 AM - 12 PM, Room 2512, Jacobs Hall (Booker Conference Room) An Exploration of Sparse Projections: Networks, Signals and GeneticsSoheil 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. | ||||||||||

SeminarWednesday, 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). | ||||||||||

SeminarFriday, 10.14.11, 11 AM - 12 PM, Jacobs Hall, room 4309 Sampling Online Social NetworksAthina 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 > | ||||||||||

Thursday, 08.25.11, 4:00 p.m. - 5:00 p.m., Fung Auditorium, Powell-Focht Bioengineering Hall Cortically coupled image search: a practical systemDr. Barbara Hanna, CEO, Neuromatters With billions of images online, GPixels images sent down each day from satellites and video feeds abounding, rapidly searching and finding relevant information is a defining problem of this century. By enabling a seamless coupling between man and machine, and leveraging cortical and computational capabilities, search systems based on neural interfaces can foster the emergence of transformative paradigms...more > | ||||||||||

SeminarFriday, 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 > | ||||||||||

SeminarTuesday, 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 > | ||||||||||

SeminarMonday, 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-SpotsDr. 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 04.15.11, 1:00 p.m. - 2:00 p.m., Jacobs Hall, Booker Conference Room, 2512 Network architecture and its discontentsJohn Doyle, Caltech Measurement, prediction, communication, computation, decision, and control are at the heart of the modern mathematical theories in engineering and science. Yet research in these areas remains largely fragmented, and at times incompatible. The principle aim of this talk is to motivate an integrated theory based on optimization and robustness. Insights will be drawn from three converging research themes...more > | ||||||||||

SeminarWednesday, 04.13.11, 11:00 a.m. - 12:00 p.m. , Jacobs Hall, Booker Conference Room, 2512 On channel polarization and polar codesEren 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 > | ||||||||||

SeminarWednesday, 04.06.11, 11:00 a.m. - 12:00 p.m. , Jacobs Hall, Booker Conference Room, 2512 Finite-Constellation Capacity of the Gaussian ChannelYihong 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 > | ||||||||||

SeminarFriday, 04.01.11, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512 Data transmission: non-asymptotic fundamental limitsYury 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 > | ||||||||||

SeminarWednesday, 03.30.11, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512 Network Interference Management via Interference AlignmentViveck 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 > | ||||||||||

CourseTuesday, 03.22.11 - Wednesday, 03.23.11, 1PM-5PM Tuesday - 9AM-5PM Wednesday, Jacobs Hall 2512 (Booker Room) Wireless Communications Andrea Goldsmith, Stanford Prof. Goldsmith will present a short course based on her “Wireless Communications” textbook, published by Cambridge University Press in 2005. Classes will be held Tuesday from 1 to 5 and Wednesday from 9 to 5. See event for full details. Please note that registration is now closed.
| ||||||||||

WorkshopSunday, 02.06.11 - Friday, 02.11.11, Calit2 6^{th}Information Theory and Applications Workshop | ||||||||||

ECE/ITA ColloquiumTuesday, 01.18.11, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512 Sampling in the Age of SparsityMartin Vetterli, Ecole Polytechnique Fédérale de Lausanne, Switzerland and UC Berkeley Joint work with Thierry Blu (CUHK), Y.Barbotin, Ali Hormati (EPFL), Y.Lu (Harvard), Pier-Luigi Dragotti (ICL) and Pina Marziliano (NTU). Sampling is a central topic not just in signal processing and communications, but in all fields where the world is analog, but computation is digital. This includes sensing, simulating, and rendering the real world...more > | ||||||||||

SeminarFriday, 01.07.11, 12:00PM - 1:00PM, Atkinson Hall 3004 Utility Optimal Scheduling in Networks: Small Delay and No UnderflowLongbo 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... | ||||||||||

SeminarWednesday, 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 ResilienceEdmund 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 10.29.10, 1:30 p.m. - 2:30 p.m. , Jacobs Hall, Booker Conference Room, 2512 Machine Learning Challenges in Ecological Science and Ecosystem ManagementThomas G. Dietterich, Oregon State University Just as machine learning has played a huge role in genomics, there are many problems in ecological science and ecosystem management that could be transformed by machine learning. This talk will give an overview of several research projects at Oregon State University in this area and discuss the novel machine learning problems that arise. These include (a) automated data cleaning and anomaly detection in sensor data streams, (b) automated classification of images of arthropod specimens, (c) species distribution modeling including modeling of bird migration from citizen science data, and (d) design of optimal policies for managing wildfires in forest ecosystems. The machine learning challenges include flexible anomaly detection for multiple data streams, trainable high-precision object recognition systems, explicit models of sampling bias and measurement processes, and optimization of complex spatio-temporal Markov processes. | ||||||||||

WorkshopFriday, 10.08.10, 9am - 3:15pm, Calit2 Auditorium, Atkinson Hall From GSR to CTOThree of the communications industry's leading innovators: Roberto Padovani, CTO of Qualcomm, Arogyaswami Paulraj, CTO of Beceem, and Nambi Seshadri, CTO of Broadcom, will join five of our graduate student researchers (GSRs) who recently received significant recognition for their research achievements to share their views on the future of the information theory field, and to answer the questions: What does it take to transform great research into commercial success? And from GSR...more > | ||||||||||

SeminarWednesday, 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 SequencesJacob 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 > | ||||||||||

SeminarFriday, 07.30.10, 11:00 a.m. - 12:00 p.m., Atkinson Hall (CALIT2), room 4004 Decomposing permutations by cost-constrained transpositionsOlgica Milenkovic, University of Illinois at Urbana-Champaign We address the problem of ﬁnding the minimum decomposition of a permutation in terms of transpositions with non-uniform cost. Our investigation is motivated by three different applications. The ﬁrst 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 > | ||||||||||

SeminarWednesday, 06.09.10, 11:00 a.m. - 12:00 p.m. , Jacobs Hall, Booker Conference Room, 2512 Interactive distributed source coding for network function computationNan 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.19.10, 11:00 AM - 12:00 PM, Atkinson Hall (CALIT2), room 4004 Asynchrony, asymptotics, and asymmetry in distributed consensusAnand D. Sarwate, ITA Center, CALIT2, UCSD Distributed consensus algorithms compute a function of data held at different locations in a network by passing messaged between agents in the network. Applications for this simple operation include load balancing in power networks, coordination in robotic networks, and calibration in sensor networks. In this talk I will discuss work on asynchronous "gossip"-style algorithms for computing averages in networks and provide asymptotic results for large networks as well as guarantees for smaller networks under different assumptions on the network's capabilities. | ||||||||||

ECE/ITA ColloquiumFriday, 05.07.10, 11:00 a.m. - 12:00 p.m., EBU-l, Room 2512 Real-Time Embedded Convex OptimizationStephen P. Boyd, Stanford University This talk concerns the use of convex optimization, embedded as part of a larger system that executes automatically with newly arriving data or changing conditions, in areas such as automatic control, signal processing, real-time estimation, real-time resource allocation and decision making, and fast automated trading. Such systems are already in use in applications such as model predictive control or supply chain optimization, with sample times measured in minutes (or longer); our focus is on systems with much faster dynamics, with execution times measured in milliseconds or microseconds for small and medium size problems. We describe a preliminary implementation of an automatic code generation system, which scans a description of the problem family and performs much of the analysis and optimization of the algorithm, such as choosing variable orderings used with sparse factorizations, at code generation time; compiling the generated source code yields an extremely efficient custom solver for the problem family. | ||||||||||

SeminarWednesday, 05.05.10, 11:00 a.m. - 12:00 p.m., Jacobs Hall, Booker Conference Room, 2512 The Value of Volatile Resources in Electricity MarketsSean 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. | ||||||||||

SeminarThursday, 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 ChannelsTsachy 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. | ||||||||||

SeminarWednesday, 04.28.10, 1:30 p.m. - 2:30 p.m. , Atkinson Hall (CALIT2), room 6004 Matrix completion: fundamental limits and efficient algorithmsSewoong 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 > | ||||||||||

SeminarFriday, 04.23.10, 11:00AM - 12:00PM, 4004 Atkinson Hall Opportunistic Routing in Wireless Networks with Congestion DiversityTara 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. | ||||||||||

Thursday, 03.18.10, 11:00 - 12:00, 4004 Atkinson Hall A code for all seasons: 1. Concatenated polar codes, 2. Coding for causal adversaries, 3. Robust network tomography, 4. Randomized non-adaptive group testingSidharth Jaggi, Chinese University of Hong Kong (CUHK) A code for all seasons: 1. Concatenated polar codes 2. Coding for causal adversaries 3. Robust network tomography 4. Randomized non-adaptive group testing These mini-talks aim to initiate conversations (at the cost of detailed proofs). A subset (1-3) of talks will be presented depending on an audience poll and a tetrahedral dice. | ||||||||||

SeminarWednesday, 03.17.10, 11:00 AM - 12:00 PM, Atkinson Hall 4004 Large wireless networks: fundamental limits and design issuesPaolo 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 > | ||||||||||

Monday, 03.15.10, 2:00 - 3:00, 4004 Atkinson Hall Codes for Secure Content DistributionN. Prasanth Anthapadmanabhan, University of Texas, Austin In this talk, we provide constructions for fingerprinting codes that have an efficient algorithm to detect guilty users. Next, we illustrate a communication-theoretic viewpoint which enables the derivation of upper bounds. Furthermore, we also introduce the notion of two-level fingerprinting. In this setting, the users are organized in a hierarchical manner by classifying them into various groups; for instance, by collecting users from the same geographic region into one group. We construct two-level fingerprinting codes that can detect guilty users using a polynomial-time algorithm. | ||||||||||

SeminarWednesday, 02.17.10, 1:30 PM - 2:30 PM, 6004 Atkinson Hall On the Duality Between Slepian-Wolf Coding and Channel CodingJun 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. | ||||||||||

WorkshopSunday, 01.31.10 - Friday, 02.05.10, Calit2 5^{th}Information Theory and Applications Workshop | ||||||||||

SeminarFriday, 12.11.09, 11:00 - 12:00, 4004 Atkinson Hall On information theoretic network securityTracey 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 wiretapped. | ||||||||||

SeminarFriday, 11.13.09, 3:00 PM - 4:00 PM, EBU2, Room 479 Understanding Implicit Communication in Distributed ControlPulkit 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 > | ||||||||||

SeminarWednesday, 11.11.09, 2:00 PM - 3:00 PM, 4004 Atkinson Hall Coding for online adversariesMichael 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. | ||||||||||

SeminarWednesday, 11.04.09, 1:00 PM - 2:00 PM, 4004 Atkinson Hall Network Compress-ForwardYoung-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. | ||||||||||

SeminarWednesday, 10.28.09, 2:00 PM - 3:30 PM, 4004 Atkinson Hall Online Learning and Drifting gamesYoav 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. | ||||||||||

SeminarFriday, 10.23.09, 11:00 - 12:00, 4004 Atkinson Hall Convergence Results for Ant Routing Algorithms via Stochastic ApproximationPunyaslok 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 > | ||||||||||

SeminarFriday, 10.16.09, 11:00 a.m. - 12:00 p.m., Atkinson Hall (CALIT2), room 4004 Learning algorithms and Markov chain computationsVivek 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. | ||||||||||

SeminarMonday, 10.12.09, 4:00 p.m. - 5:00 p.m., EBU1, room 4309 Information Theory meets Game Theory on the Interference ChannelRandall 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. | ||||||||||

SeminarWednesday, 08.26.09, 2:00 PM - 3:00 PM, Atkinson Hall, Room 4004 On the optimality of universal classifiers for finite-length individual test sequencesDr. 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 > | ||||||||||

Friday, 07.31.09, 1:00 - 2:00, 4004 Atkinson Hall Towards Anonymity in NetworkingParv Venkitasubramaniam, Cornell University / UC Berkeley As wireless networks increasingly dominate our means of communication, the vulnerability of the open medium has brought the issues of privacy and security to the fore. While cryptography serves to protect the contents of communication, it is equally essential to hide the very act of communication. For example, knowledge of direction of data flow in sensor networks can provide critical information such as event locations and cluster head identities. | ||||||||||

SeminarWednesday, 07.22.09, 11:00 - 12:00, 3004 Atkinson Hall Collaboration, Power and StabilityYoram 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. | ||||||||||

SeminarFriday, 06.19.09, 12:00 - 1:00, 4004 Atkinson Hall Reliable Relaying with Uncertain KnowledgeJiwoong 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 ﬁrst 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. | ||||||||||

SeminarMonday, 06.08.09, 12:00 - 1:00, 4004 Atkinson Hall Surprisal in real-time human language comprehension and productionRoger 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 > | ||||||||||

SeminarTuesday, 05.26.09, 12:00 - 1:00, 4004 Atkinson Hall Coding Techniques for Distributed StorageDistributed 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. | ||||||||||

ECE/ITA ColloquiumFriday, 05.22.09, 3:00 PM - 4:00 PM, EBU-l, Room 2512 On Optimal Fix-free CodesSerap Savari, Texas A&M University Fix-free codes are variable length codes in which no codeword is the prefix or suffix of another codeword. They have been investigated for joint source-channel coding and have been applied within the video standards H.263+ and MPEG-4 because their property of efficient decoding in both the forward and backward directions assists with error resilience. They are also interesting for problems in information retrieval such as searching for patterns directly in compressed text. We provide a low-complexity heuristic to produce fix-free codes. The design of optimal or minimum-redundancy fix-free codes has been a longstanding open problem. We offer the first solution both to this problem and to a variation in which all codewords are also required to be palindromes. | ||||||||||

SeminarMonday, 05.18.09, 4:00 - 5:00, Atkinson Hall Room 4004 A Stochastic Control Viewpoint on `Posterior Matching'-style Feedback Communication SchemesThis 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. | ||||||||||

ECE/ITA ColloquiumFriday, 05.15.09, 11:00 a.m. - 12:30 p.m. , EBU-l, Room 2512 Can MEMS Revolutionize the Semiconductor Industry? Sensor Integration, Energy Scavenging, and Tunable RadioFarrokh Ayazi, Georgia Institute of Technology Recent years have witnessed the maturity of MEMS in automotive safety applications and its penetration into cost sensitive consumer markets. Breakthrough researches have enabled high performance silicon-based sensors, actuators and signal-processing elements such as accelerometers, gyroscopes, microphones, micromirrors, high-Q microresonators and switches...more > | ||||||||||

SeminarMonday, 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 ChannelAmin 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. | ||||||||||

ECE/ITA ColloquiumFriday, 05.08.09, 1:00 p.m. - 2:00 p.m., EBU-l, Room 2512 How Random-Set Theory Can Help Wireless CommunicationsDr. Ezio Biglieri, UCLA A number of problems arising in the analysis of wireless communication systems require the estimation of the components of a vector whose dimension is unknown. Two of these problems are, (a) Multiuser detection in which the number of active users is unknown and time-varying, and (b) Estimation of multipath channels where the number of paths is not known a priori and possibly time-varying. Standard solutions to these problems are intrinsically suboptimum, as they proceed either by assuming a fixed number of vector components, or by first estimating this number, then the values taken on by the components. For an optimum solution, one may use random-set theory, which is a probability theory of finite sets exhibiting randomness not only in their elements, but also in their cardinality. Some examples, related to problems (a) and (b) above, illustrate the results obtained from this theory. | ||||||||||

SeminarMonday, 05.04.09, 11:45 - 12:45, Atkinson Hall Room 4004 Spectral Clustering of SurfacesEry 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 05.01.09, 1:30 p.m. - 2:30 p.m. , EBU-l, Room 2512 On the intersection between queueing and information theory - some new results.Muriel Medard, MIT The interaction between queueing and information theory is an important one in bringing information-theoretic principles into networking. In this talk, we highlight some new results in this area, with an emphasis on wireless systems. The first set of results consider the issue of coding in queues, in particular in the context of network coding. Coding in this context blurs the traditional delineation among packets, but it allows for considerable benefits for delay...more > | ||||||||||

SeminarMonday, 04.20.09, 12:00 - 1:00, Atkinson Hall Room 4004 Subspace Pursuit for Compressive Sensing and Its ApplicationsWei 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. | ||||||||||

SeminarMonday, 04.13.09, 12:00 - 1:00, TBA Automatic Verification of Data-centric Business ProcessesAlin 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. | ||||||||||

SeminarWednesday, 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. | ||||||||||

SeminarMonday, 03.02.09, 11:30 AM - 12:30 PM, Atkinson Hall, Room 4004 Haplotype assemblyVineet 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. | ||||||||||

ECE/ITA ColloquiumFriday, 02.27.09, 3:00 PM - 4:15 PM, Booker Conference Room, EBU 1 Room 2512 TBAPatrick Yue, UC Santa Barbara | ||||||||||

Wednesday, 02.25.09, 11:30 - 12:30, Atkinson Hall, Room 6006 A Channel Coding Perspective of Recommendation SystemsOnkar Dabeer, Tata Institute for Fundamental Research The goal of a recommendation system is to exploit available ratings (assigned by buyers to items) to suggest relevant items to the buyers. We assume that the observed rating matrix is obtained by passing a piecewise constant matrix through a channel causing unknown row and column permutations, errors, and erasures. Our goal is to recover the underlying rating block constant matrix (up to some ``block" permutations) asymptotically as the matrix size approaches infinity. Our main result identifies a threshold such that if the cluster sizes are below the threshold, then exact recovery is not possible, but if the cluster sizes are above the threshold, then exact recovery is possible using a polynomial time algorithm. The results also apply to the case when the channel parameters are not known exactly. | ||||||||||

SeminarWednesday, 02.18.09, 11:30 - 12:30, Atkinson Hall, Room 6006 Graphical Models for NetworksSujay 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. | ||||||||||

WorkshopSunday, 02.08.09 - Friday, 02.13.09, 9AM - 5PM, UCSD 4^{th} Information Theory and Applications WorkshopThis is the 4th annual ITA Workshop. As in the past, the first part of the week will center around information theory and communications, while the latter part will involve networking, signal processing, control, bioinformatics and related disciplines. We are also planning a keynote and several tutorials on theoretical computer science, some talks by outstanding graduating students, and more...more > | ||||||||||

SeminarWednesday, 01.28.09, 11:30 - 12:30, Atkinson Hall, Room 6006 Invertible Extractors and Wiretap ProtocolsMahdi 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. | ||||||||||

SeminarWednesday, 01.21.09, 11:30 AM - 12:30 PM, Atkinson Hall, Room 6006 The Liar's Game with a List, and Error Correction with FeedbackOfer 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. | ||||||||||

SeminarWednesday, 01.14.09, 11:30 AM - 12:30 PM, Atkinson Hall, Room 4004 IEEE 802.11 is Good Enough to Build Wireless Multi-Hop NetworksApoorva 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. | ||||||||||

Monday, 11.24.08, 3:00 - 4:30, Calit2 4004 Directed Information and Causal Conditioning in Communication, Compression, Investments, and Statistics Haim Permuter, Ben-Gurion University and Stanford University In this talk, we will introduce the notions of ``directed information" and ``causal conditioning", and investigate their roles in several fields. We will begin by defining and establishing some key properties of causal conditioning and directed information. These properties will be seen to be natural counterparts, for the case where the system has causality constraints, to the well-known properties of regular conditioning and mutual information...more > | ||||||||||

Friday, 10.31.08, 2:00 PM, EBU 1, Room 6504 Interference channel with source/destination cooperationVinod Prabhakaran , UIUC Current wireless systems rely on a centralized interference management system which tries to limit interference by centrally controlling medium access. As wireless systems move towards a decentralized architecture (*e.g.*, femtocells), decentralized interference management is set to take center-stage. To study the role of cooperation in interference management, we consider a two-user Gaussian interference channel where the source/destination nodes can both talk and listen...more > | ||||||||||

Monday, 09.15.08, TBD, TBD Some universal compression algorithms for individual finite-length N-blocks are better than othersJacob Ziv, Technion | ||||||||||

SeminarThursday, 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 > | ||||||||||

Lunchtime informal seminarWednesday, 06.04.08, 11:30am - 1:00pm, 4004/06 CalIT2 TBAYoung-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 > | ||||||||||

SeminarTuesday, 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 > | ||||||||||

SeminarMonday, 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 > | ||||||||||

Lunchtime informal seminarWednesday, 05.28.08, 12 - 1.30pm, 4004/4006 (4th floor Atkinson) Entry wise bounds for eigenvectors of random graphsPradipta 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 > | ||||||||||

Tuesday, 05.27.08, 12:00 PM, CALIT2, Room 4004/06 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 > | ||||||||||

Lunchtime informal seminarWednesday, 05.07.08, 12pm - 1:00pm, 4004/06 CalIT2 Uniform Direct Product Theorems: Simplified, Optimized, and DerandomizedRussell 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 > | ||||||||||

Monday, 04.28.08, 11:00 AM - 12:00 PM, EBU 1, Room 6504 Learning to Discover: Adaptive Data Selection for Classification and EstimationRui M. Castro, University of Wisconsin, Madison Science is arguably the pinnacle of human intellectual achievement, yet the scientific discovery process itself remains an art. Human intuition and experience is still the driving force of the high-level discovery process: we determine which hypotheses and theories to entertain, which experiments to conduct, how data should be interpreted, when hypotheses should be abandoned, and so on...more > | ||||||||||

SeminarMonday, 04.21.08, 11:00 AM - 12:00 PM, EBU-1, 6504 Testing Low Degree Polynomials over Small Prime FieldsAnindya 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 > | ||||||||||

SeminarFriday, 04.18.08, 11:00 AM - 12:00 PM, EBU 1, Room 6504 Efficient Algorithms for Active LearningClaire 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 > | ||||||||||

Lunchtime informal seminarWednesday, 04.16.08, 12pm - 1.30pm, 4004/4006 (4th floor Atkinson) Interference Alignment and the Capacity of Wireless NetworksSyed 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 > | ||||||||||

SeminarTuesday, 04.15.08, 11 - 12, EBU1, Room 2512 Robust architectures for next generation communication systemsAnand 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 > | ||||||||||

SeminarMonday, 04.07.08, 11:00 AM - 12:00 PM, EBU-I 6504 The posterior matching principle for optimal communication with feedbackOfer 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 > | ||||||||||

SeminarMonday, 03.31.08, 11:00 AM - 12:00 PM, EBU1, Room 6504 Information flow over wireless networks: a deterministic approachSalman 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 > | ||||||||||

Lunchtime informal seminarWednesday, 03.05.08, 12pm - 1.30pm, 4th Floor Conference Room CALIT2 Functional SparsityJohn 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 > | ||||||||||

Lunchtime informal seminarWednesday, 02.27.08, 12pm - 1.30pm, 4th Floor Conference Room CALIT2 Learning Classifiers from Only Positive and Unlabeled DataKeith 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 > | ||||||||||

SeminarWednesday, 02.27.08, 10.30am - 11.30am, 4004/4006 (4th floor Atkinson) Computing on Streams: New Results and DirectionsAndrew 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 > | ||||||||||

Lunchtime informal seminarWednesday, 02.20.08, 12:00pm - 1:00pm, 4004/06 (4th floor conference room), CALIT2 Designing a content-based music search engineGert Lanckriet, ECE,UCSD If you go to Amazon.com 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 02.15.08, 11, TBD The power and weakness of computational randomnessAvi Wigderson, Institute for Advanced Study Man has grappled with the meaning and utility of randomness for centuries. Research in the Theory of Computation in the last thirty years has enriched this study considerably. I will describe two main aspects of this research on randomness, demonstrating its power and weakness respectively. -Randomness is paramount to computational efficiency: The use of randomness can dramatically enhance computation (and do other wonders) for a variety of problems and settings...more > | ||||||||||

Lunchtime informal seminarWednesday, 02.13.08, 12pm - 1.30pm, 4th Floor Conference Room CALIT2 Communicating Delay-Sensitive and Bursty Information over an Outage ChannelTara 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 > | ||||||||||

Lunchtime informal seminarWednesday, 02.06.08, 12pm - 1.30pm, 4004/4006 (4th floor Atkinson) Efficient reductions among lattice problemsDaniele 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 > | ||||||||||

WorkshopMonday, 01.28.08 - Friday, 02.01.08, Room TBD 3^{rd} Information Theory and Applications Workshop | ||||||||||

Lunchtime informal seminarWednesday, 01.16.08, 12 - 1.30, 4th Floor Conference Room CALIT2 Wireless ad-hoc networks: from probability to physics via information theoryMassimo 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 11.30.07, 11 - 12, EBU-1 4307 Wireless Networks: Cellular System Engineering and Multiterminal Information TheoryPramod Viswanath, UIUC Successful design of reliable networks, for information compression and transmission, requires posing questions at appropriate levels of abstraction. At a coarser level, one asks for optimal architectures. At a finer level, once a specific architecture has been adopted, one asks for efficient engineering schemes. This talk discusses two pieces of work that exemplify this approach, one in the context of information transmission and the other for information compression...more > | ||||||||||

WorkshopFriday, 11.16.07, 9:25 - 5:00, Calit2 - Multipurpose Room Drawingboard to Boardroom - an (Entre/Intra)preneurship Workshop Information and registration at: http://cwc.ucsd.edu/drawingboard.php | ||||||||||

SeminarFriday, 11.09.07, 1:30 PM - 2:30 PM, EBU 1, Room 4307 Finding low-rank matrices via convex optimizationMaryam 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 11.02.07, 11 - 12, EBU-1 4307 Extracting Information from Music AudioDan Ellis , Columbia University Large online collections of music audio present a rich opportunity for automatic analysis, particularly by machine learning techniques that can take advantage of huge datasets. We have been investigating a number of music audio analysis applications, mostly oriented towards the goal of prediction of perceived similarity or preference. I will describe several of these projects, including music classification based on spectral feature distributions, incremental learning of playlist classes, rhythm pattern decomposition, and automatic detection of cover song versions...more > | ||||||||||

SeminarMonday, 10.22.07, 11 AM - 12 PM, Calit2, Room 4004 Degrees of Freedom and O(1) Capacity of Wireless Interference NetworksSyed 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 > | ||||||||||

CourseFriday, 10.05.07, 9 - 5, Rm 4004, Calit2 Stochastic Network OptimizationMichael J. Neely, USC This course presents a theory of stochastic network optimization for modern wireless networks with time varying channels, mobility, and randomly arriving traffic. We view the network as a queueing system with general transmission rate capabilities determined by the physical properties of each network element. Explicitly including queues in the model not only provides a more complete cross-layer perspective, but facilitates the design of opportunistic resource allocation, routing, and flow control decisions...more > | ||||||||||

ECE/ITA ColloquiumFriday, 10.05.07, 11 - 12, EBU-1 4307 WHAT IS INFORMATION?Wojciech Szpankowski, Purdue University Information permeates every corner of our lives and shapes our universe. Understanding and harnessing information holds the potential for significant advances. The breadth and depth of underlying concepts of the science of information transcend traditional disciplinary boundaries of scientific and commercial endeavors. Information can be manifested in various forms: business information is measured in dollars; chemical information is contained in shapes of molecules; biological information stored and processed in our cells prolongs life...more > | ||||||||||

SeminarFriday, 08.17.07, 2PM - 3PM, Calit2, Rm 4004 Capacity Approaching, Efficiently Decodable Lattice CodesMeir 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 > | ||||||||||

SeminarThursday, 07.26.07, 10 - 11, Calit2 Rm. 4004 On universal compression and classification of individual two-dimensional arraysJacob 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 > | ||||||||||

Lunchtime informal seminarTuesday, 06.12.07, 1 - 2, CSE 4140 A Topic in Coding TheoryRoxana Smarandache, San Diego State University | ||||||||||

Lunchtime informal seminarTuesday, 06.05.07, 1 - 2, CSE 4140 Antenna Synthesis and Channel CapacityMarco 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 > | ||||||||||

Lunchtime informal seminarFriday, 06.01.07, 1 - 2, CSE 2109 A physical approach to multiple antenna communicationMassimo 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 > | ||||||||||

Lunchtime informal seminarTuesday, 05.29.07, 1 - 3.30, CSE 4140 A Stochastic Control Approach to Variable Length Menus in P300 Neural Communication ProsthesesTodd 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 > | ||||||||||

Lunchtime informal seminarWednesday, 05.23.07, 1 - 2, CSE 2109 Distance metric learning for large margin nearest neighbor classificationLawrence 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 > | ||||||||||

SeminarTuesday, 05.08.07, 1PM, TBD Clustering using Correlation and IndependenceKamalika 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 > | ||||||||||

SeminarMonday, 05.07.07, 11:30, EBU-1 6504 Cooperative Diversity: Protocols and AnalysisKambiz 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 > | ||||||||||

Lunchtime informal seminarTuesday, 04.17.07, 12 - 1, CSE 4140 Using Random Projections to Learn the Distribution of Data Concentrated on a Low Dimensional ManifoldYoav Freund, UCSD In this lunchtime informal seminar, Yoav will discuss some recent work and present some open problems. | ||||||||||

Lunchtime informal seminarTuesday, 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. | ||||||||||

WorkshopMonday, 01.29.07 - Friday, 02.02.07, UCSD 2^{nd} ITA WorkshopThe 2007 Information Theory and Applications Workshop will be held Monday 1/29 to Friday 2/2 at UCSD. As with the inaugural workshop, Monday and Tuesday will focus on information theory and communication while Thursday and Friday will center on bioinformatics, machine learning, statistics, and related fields. New for the 07 workshop will be presentations by graduating students and recent postdocs, the co-location of NetCod07, and...more > | ||||||||||

WorkshopFriday, 01.26.07 - Saturday, 01.27.07, CMRR Auditorium Theory and applications of message passing: probability, physics, computer science and communicationsOrganized by Andrea Montanari, Stanford, and Ruediger Urbanke, EPFL | ||||||||||

SeminarFriday, 01.19.07, 2PM - 3PM, Calit 5004 Role of noisy feedback in communicationYoung-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 > | ||||||||||

SeminarTuesday, 12.05.06, 11 - 12, CSE 4217 Estimation of probability distributions with maximum entropy -- incorporating generalized regularizations and modeling species habitatsMiroslav 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 > | ||||||||||

SeminarMonday, 12.04.06, 11 - 12, CSE 4217 Convex Repeated Games and Fenchel DualityShai 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 > | ||||||||||

SeminarFriday, 12.01.06, 11 AM - 12 PM, EBU-1 6504 Slepian-Wolf Coding over Broadcast ChannelsErtem 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 > | ||||||||||

CourseFriday, 11.17.06, 9:00 - 5:00, MPR, Calit2 Space-time codingHamid Jafarkhani, UC Irvine This course covers the fundamental principles of space-time coding for wireless communications over multiple-input multiple-output (MIMO) channels, and sets out practical coding methods for achieving the performance improvements predicted by the theory. Starting with background material on wireless communications and the capacity of MIMO channels, the course then reviews design criteria for space-time codes...more > | ||||||||||

SeminarMonday, 10.30.06, 1:30 - 2:30, EBU-1 4307 Bionic Human-Machine InteractionHelen 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 > | ||||||||||

Lunchtime informal seminarMonday, 10.30.06, 12 - 1, 4004/4006 (4th floor Atkinson) The physical layer of WiMedia OFDM UWBRabih 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 > | ||||||||||

CourseMonday, 09.25.06 - Tuesday, 09.26.06, 9-4:30 Monday and 9-12 Tuesday, Room TBD Modern coding theory Ruediger Urbanke, EPFL The advent of iterative coding schemes has had a large impact on the theory as well as the practice of coding. Most of the current standards include iterative coding schemes to either replace or enhance traditional coding solutions. The goal of this course is to study the fundamental concepts that underlie the idea of iterative coding: what makes them work, how can they be analyzed, and how can they be improved...more > | ||||||||||

CourseThursday, 09.21.06 - Friday, 09.22.06, 9-4:30 Thursday and 9-12 Friday, Calit2 MPR Coding for wireless channels Ezio Biglieri, Universitat Pompeu Fabra This course will cover several topics related to coding for wireless communication, including: fading channel models: independent fading, block fading, MIMO; information-theoretic performance limits; coding on signal spaces; optimization criteria for code design; factor-graphical models of codes... | ||||||||||

SeminarWednesday, 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.... | ||||||||||

SeminarFriday, 08.04.06, 11 - 12, EBU-1 Rm 4307 Golden Space-Time Trellis Coded ModulationEmanuele 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.... | ||||||||||

CourseTuesday, 08.01.06, 9AM - 5PM, Calit Auditorium Network coding Ralf Koetter, UIUC, and Muriel Medard, MIT The advent of network coding promises to change many aspects of networking. Network coding moves away from the classical approach of networking, which treats networks as akin to physical transportation systems... | ||||||||||

SeminarThursday, 06.15.06, 2 - 3, EBU1-6504 On coded and uncoded transmissions of Gaussian sources over Gaussian channelsAmos 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 > | ||||||||||

CourseFriday, 06.09.06 - Saturday, 06.10.06, 9-4:30 Friday and 9-12 Saturday, Calit Auditorium Fundamentals of wireless communications David Tse, U.C. Berkeley The past decade has seen a surge of research activities in the field of wireless communications. This is due to a confluence of factors: the explosive growth in demand for tetherless connectivity, dramatic improvement in hardware implementation technology, as well as the success of 2-G digital wireless standards. Emerging from this research thrust are new points of view on how to communicate effectively over wireless channels...more > | ||||||||||

SeminarWednesday, 05.31.06, 11:00 - 12:00, EBU-1 4307 Market-based Approaches for Efficient Allocation of Network ResourcesRahul 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 > | ||||||||||

SeminarTuesday, 05.30.06, 2:00 - 3:00, EBU1 4307 CDMA Reverse Link Interference CancellationJilei 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 > | ||||||||||

Seminar (2002 Medicine Nobel Laureate)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 > | ||||||||||

SeminarWednesday, 05.17.06, 3:00 - 4:00, Calit Synthesis Room Graphs, colorings and beyond in comparative genomicsSagi 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 > | ||||||||||

SeminarMonday, 05.15.06, 11:00 - 12:00, Calit2 MPR Streams and samples: new directions for processing massive data setsAndrew 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.... | ||||||||||

ECE/ITA ColloquiumFriday, 05.05.06, 11:00 am - 12:00 pm, Calit2 Multipurpose Room Capacity, cooperation, and cross-layer design in wireless wetworksAndrea Goldsmith, Stanford University We consider fundamental capacity limits in wireless networks where nodes can cooperate in transmission, reception, and routing. We propose novel cooperation techniques that approach the capacity bounds, including virtual MIMO transmission, relaying, and conferencing. The optimal cooperation strategy is cross-layer in nature and depends on the network topology, the channel SNR, and the channel side information available at the nodes...more > | ||||||||||

SeminarThursday, 05.04.06, 10:00 am - 11:00 am, EBU1 4307 Reliable Communication in the Presence of Side InformationTie 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 > | ||||||||||

ECE/ITA ColloquiumFriday, 04.21.06, 4:00 p.m., CMRR Auditorium Shannon lecture: Demodulation Meets Signal Processing - Two-Dimensional Information TheoryRichard E. Blahut, University of Illinois at Urbana-Champaign This year's Shannon Memorial Lecture by Professor Blahut will examine agorithms for demodulation and signal processing such as the Viterbi algorithm and the Wiener filter are highly valued by those who use them. Motivated by problems of two-dimensional recording, we will consider these problems in a unified way. The Richardson-Lucy algorithm will be described as an information-theoretic algorithm suitable for both demodulation and signal processing, and often superior to both the Viterbi algorithm and the Wiener filter (work based in part on the thesis of Zhijun Zhao...more > | ||||||||||

SeminarFriday, 04.14.06, 10:00 - 11:00, EBU1 - 4307 Efficient Matching for Recognition and RetrievalKristen 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. | ||||||||||

SeminarTuesday, 04.11.06, 10:00 - 11:00, EBU1 - 4307 Role of Feedback in CommunicationYoung-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. | ||||||||||

ECE/ITA ColloquiumFriday, 03.17.06, 11:00 - 12:00, Calit2 MPR Signal Processing for GenomicsP.P. Vaidyanathan, Caltech The theory and methods of signal processing are becoming increasingly important in molecular biology. This talk includes a brief review of molecular biology, followed by a review of the applications of signal processing theory. Also presented is the relatively new topic of noncoding genes, and the associated problem of identifying ncRNA buried in DNA sequences...more > | ||||||||||

ECE/ITA ColloquiumFriday, 03.03.06, 11:00 - 12:00, Calit2 MPR Error-Correcting Codes for Automatic ControlLeonard Schulman, Caltech Increasingly, systems with automatic feedback control may consist of several remote devices, connected only by unreliable communication channels. It is necessary in these conditions to have a method for accurate, real-time state estimation in the presence of channel noise. We address this problem, for the case of polynomial-growth-rate state spaces, by providing a new type of error-correcting code that is on-line and computationally efficient...more > | ||||||||||

ECE/ITA ColloquiumFriday, 02.17.06, 11:00 - 12:00, Calit2 MPR Design in the Late Silicon AgeJan Rabaey, UC Berkeley Scaling of silicon integrated technology into the deep sub-100 nm space brings with it a number of formidable challenges to the designer. Issues such as design complexity, power dissipation, process variability and reliability are challenging the traditional design methodologies. In this presentation, it is conjectured that the only viable long-term solution to these challenges is to drastically revise the way we do design, and a roadmap of potential solutions is presented...more > | ||||||||||

WorkshopMonday, 02.06.06 - Friday, 02.10.06, Calit2 Information Theory and Applications Workshop ITA's inaugural workshop was attended by 439 participants hailing from 21 countries, 25 companies, and 84 universities, and presenting 183 technical talks. Monday and Tuesday focused on communication, coding, and compression while Thursday and Friday centered around networking, machine learning, statistics, statistics, vision, and bio-informatics. Thursday also included a life-science-tutorial with talks on Systems biology, bioinformatics, and population genetics... | ||||||||||

ECE/ITA ColloquiumFriday, 02.03.06, 11:00 - 12:00, Calit2 MPR Approaches to Network CodingRalf Koetter, UIUC Network coding allows information from different streams to be processed or coded together at network nodes. This is a more general and powerful framework than the traditional store and forward approach. This talk will give a short introduction to this field and its ramifications. Particular attention will be paid to the problem of actually designing network codes in the multiple unicasts scenario in directed graphs...more > | ||||||||||

ECE/ITA ColloquiumFriday, 01.27.06, 11:00 - 12:00, Calit2 MPR Quantization, Compression, and Classification: Extracting Discrete Information from a Continuous WorldRobert M. Gray Scientists and engineers often seek to measure, communicate, store, process, reproduce, or analyze signals encountered in the real world. Most such signals are inherently continuous or analog in nature, yet increasingly the means for communicating, storing, and processing such information are discrete. Generally something is lost when continuous information is converted into discrete approximations, so a natural goal is to preserve as much of the original information as possible...more > | ||||||||||

ECE/ITA ColloquiumFriday, 01.20.06, 11:00 - 12:00, Calit2 MPR MM-wave RFICHossein Hashemi In this talk, I will present an overview of various forms of multi-antenna configurations such as phased-arrays, beam forming schemes, and diversity multiple-input multiple-output (MIMO) systems. Antenna arrays for communications, radar, imaging, and sensing applications will be described in more detail. I will then describe our current research in the following three areas: Ultra-Wide Band (UWB) beam-forming on silicon for high resolution ranging applications Silicon-based integrated phased arrays at millimeter waves for high data rate communication and imaging applications Concurrent multi-frequency beam-forming for multi-functional communication/imaging/sensory systems Various transceiver architectures and circuit implementations for a complete integration of multi-antenna systems using a silicon technology and experimental results will be presented...more > | ||||||||||