|Locally Testable Codes and L<sub>1</sub> Embeddings of Cayley Graphs
A locally testable code (LTC) is an error correcting code which admits a very efficient procedure for testing membership in the code: a local tester queries few locations in the received word but still distinguishes codewords from words that are far from the code. The main open questions about LTCs are about the tradeoffs possible between rate, distance and query complexity.
We show that the local testability of a binary linear code is related (and in fact equivalent) to the L1 embeddability of a related Cayley graph. Thus one can reformulate existential questions about LTCs as questions about the existance of certain Cayley graphs that admit constant distortion embeddings into L1. We discuss what this tells us about existing results on LTCs and what it might tell us about new results.
Joint work with Salil Vadhan (Harvard) and Yuan Zhou (CMU).
|Explorations in Probabilistic Programming: Generative Probabilistic Graphics Programming and New Research Directions
Probabilistic programming has recently attracted much attention in Computer Science and Machine Learning communities. I will demonstrate two generative probabilistic graphics programs (models), which I contributed to develop. The first can read text from simple CAPTCHAs, and the second can find roads from real-world images. Both work by performing approximate inference over the executions of simple renderers, using the general-purpose Metropolis-Hastings inference engine built into a probabilistic programming system. I will briefly touch on two other research directions I am interested in pursuing: a path to scaling up general-purpose approximate inference in probabilistic programs using parallelism, based on preliminary work on a multithreaded approximate MCMC scheme for Church-like languages, and a much longer-term path to automatic programming via general-purpose approximate inference.
This is based on joint work with Vikash Mansinghka, Tejas Kulkarni, and Joshua Tenenbaum, especially 'Approximate Bayesian Image Interpretation using Generative Probabilistic Graphics Programs', http://arxiv.org/abs/1307.0060
This is joint work with Frolin Ocariza, Kartik Bajaj and Ali Mesbah from UBC.
|Probabilistic Program Analysis using Martingale Theory
Probabilistic programs are standard imperative programs enriched with constructs to generate random values according to a pre-specified distribution. Such programs are common in a variety of application domains, including risk assessment, biological systems, sensor fusion algorithms and randomized algorithms. We present deductive techniques for the analysis of infinite state probabilistic programs to synthesize probabilistic 'invariants' and prove almost-sure termination. Our analysis is based on the notion of martingales and super martingales from probability theory. First, we define the concept of (super) martingales for loops in probabilistic programs, and present analogies between super martingales and inductive invariants. We then use concentration of measure inequalities to bound the values of martingales with high probability. This directly allows us to infer probabilistic bounds on assertions involving the program variables. Using the notion of a super martingale ranking function (SMRF), we prove almost sure termination of probabilistic programs. We extend constraint-based approaches for synthesizing inductive invariants to also synthesize martingales and super-martingale ranking functions for probabilistic programs. We present some applications of our approach to reason about invariance and termination of some probabilistic program benchmarks. Joint work with Aleksandar Chakarov, University of Colorado Boulder.
|Recent Advances in Arithmetic Circuit Lower Bounds
Arithmetic circuits provide a robust measure of understanding the hardness of polynomials. The most important open problem in this field is to separate the complexities of the `Determinant' and `Permanent' families; this was also formalized by an arithmetic version of the 'P vs NP' problem by Valiant.
The task of proving lower bounds has always been daunting. However, there has been a lot of progress in the last year that has greatly increased our optimism that the task of proving arithmetic circuit lower bounds may not be that far away from our reach. Jointly with Ankit Gupta, Pritish Kamath and Neeraj Kayal (CCC 2013), we presented a new technique that takes us tantalizingly close to our goal. In this talk, I shall describe this lower bound in reasonable detail, and also briefly present some subsequent work.
|Networking Technologies for Real-Time, Interactive Applications
Interactive and real-time communication (RTC) applications are constituting an increasing share of internet traffic these days. As they operate on increasingly complex and noisy networks, their performance suffers due to the fact that they require both high throughput as well as low end-to-end delay. In this talk we present several networking technologies developed to improve the performance of RTC applications: RAPID, URCP, and PROTEUS. RAPID provides a reliable and adaptive protocol using an intelligent hybrid FEC/ARQ scheme designed to remove the delay caused by retransmissions of lost packets. RAPID provides the underlying technology in the RemoteFX for WAN UDP protocol shipping with Remote Desktop. URCP is a universal rate control protocol designed to provide both low delay as well as high throughput on noisy networks such as cellular networks. PROTEUS provides a framework for network prediction of cellular networks so that RTC applications can make intelligent decisions to improve performance.
|Web Search Engines- Challenges with Scale
Sree Hari Nagaralu
Designing ICT systems for rural users in the developing world can be very hard. Just a few of the challenges we face are low literacy, limited experience using digital technologies, and the wide variability in spoken languages. To overcome some of these issues, we created VideoKheti, a mobile system that uses speech, graphics, and touch interaction to help low-literate farmers in rural India find and watch agricultural extension videos in their own language and dialect.
|Distributed Systems Research@PLATO
Kapil Vaswani, Researcher, Microsoft Research India, talks about the PLATO group's research in distributed Systems.
|Accelerated Learning with Kernels
Kernel learning algorithms occupy a prominent position within machine learning having given state-of-the-art performance in several domains. Much of the power of kernel methods comes from their ability to implicitly represent complex functions in high dimensional spaces. This however, comes at a price of increased hypothesis complexity that causes these algorithms to be slow at prediction time. With an increase in demand for real time applications, this prevents kernel algorithms from being applied to several domains. A second limitation of traditional kernel-based learning methods is their dependence on so-called 'Mercer kernels' that prevents them from fully utilizing rich domain-specific knowledge in the learning process.
Our work seeks to address both these issues by developing kernel learning algorithms that offer fast prediction routines. We further develop a learning framework that allows efficient use of non-Mercer kernels in addition to offering fast training and testing routines.
- Microsoft Research India
196/36 2nd Main
Sadashivnagar, Bangalore 560 080