Skip to content. Skip to navigation
McGill Home SOCS Home
Personal tools
You are here: Home Announcements and Events Seminars Seminar History

Seminar Home
Fall 2013 Schedule
Winter 2014 Schedule
Summer 2014 Schedule
Archives

Date
( Fall 2010 )
Category Seminar Info
2010/12/16 Theory Place: MC320
Time: 15:00 - 16:30
Speaker: Pranab Sen
Affiliation: McGill and School of Technology and Computer Science
Area: complexity theory
Title: Non-Uniform ACC Circuit Lower Bounds (part II)
Abstract: This is the follow up from last week's seminar. Pranab will present part II of the recent paper by Ryan Williams. Here is the paper's abstract. The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m > 1 is an arbitrary constant. We prove: NTIME[2^n] does not have non-uniform ACC circuits of polynomial size. The size lower bound can be slightly strengthened to quasi-polynomials and other less natural functions E^NP, the class of languages recognized in 2^O(n) time with an NP oracle, doesn’t have non-uniform ACC circuits of 2^n^o(1) size. The lower bound gives an exponential size-depth tradeoff: for every d there is a delta > 0 such that E^NP doesn’t have depth-d ACC circuits of size 2^n^delta. Previously, it was not known whether EXP^NP had depth-3 polynomial size circuits made out of only MOD6 gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms entail the above lower bounds. The algorithm combines known properties of ACC with fast rectangular matrix multiplication and dynamic programming, while the second step requires a subtle strengthening of the author’s prior work [STOC’10].
2010/12/09 Theory Place: MC320
Time: 15:00 - 16:30
Speaker: Pranab Sen
Affiliation: McGill University and Tata Institute of Fundamental Research
Area: complexity theory
Title: Non-Uniform ACC Circuit Lower Bounds
Abstract: Pranab will present the recent paper by Ryan Williams. Here is the paper's abstract. The class ACC consists of circuit families with constant depth over unbounded fan-in AND, OR, NOT, and MODm gates, where m > 1 is an arbitrary constant. We prove: NTIME[2^n] does not have non-uniform ACC circuits of polynomial size. The size lower bound can be slightly strengthened to quasi-polynomials and other less natural functions E^NP, the class of languages recognized in 2^O(n) time with an NP oracle, doesn’t have non-uniform ACC circuits of 2^n^o(1) size. The lower bound gives an exponential size-depth tradeoff: for every d there is a delta > 0 such that E^NP doesn’t have depth-d ACC circuits of size 2^n^delta. Previously, it was not known whether EXP^NP had depth-3 polynomial size circuits made out of only MOD6 gates. The high-level strategy is to design faster algorithms for the circuit satisfiability problem over ACC circuits, then prove that such algorithms entail the above lower bounds. The algorithm combines known properties of ACC with fast rectangular matrix multiplication and dynamic programming, while the second step requires a subtle strengthening of the author’s prior work [STOC’10].
2010/12/02 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Adrien Lemaitre
Affiliation: University of Montreal
Area: logic and complexity
Title: Digraph homomorphism problems and tree duality
Abstract: Constraint satisfaction problems are a class of natural problems which consist in attributing values to variables while respecting relations on those variables. An important conjecture states that any constraint satisfaction problem is either tractable or NP-complete. It is known that constraint satisfaction problems reduce to digraph homomorphism problems. While the dichotomy has been established in the undirected case, the directed case remains open. We'll present subcases of the digraph that are tractable and explain how tree duality helps in their study.
2010/11/18 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Laszlo Egri
Affiliation: McGill
Area: complexity theory
Title: Optimal Algorithms and Inapproximability Results for Every CSP?
Abstract: This is the continuation of the talk from last week. The abstract is here: I will go over some results from the paper "Optimal Algorithms and Inapproximability Results for Every CSP?" (Raghavendra 2008). In particular, I will explain how to obtain dictatorship tests from SDP integrality gaps. (If time allows, I might also discuss a general rounding scheme for SDPs.) Dictatorship tests can be used to obtain UG-hardness results. Using this machinery, it can be shown that every generalized constraint satisfaction problem can be optimally approximated by a simple SDP.
2010/11/12 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Laszlo Egri
Affiliation: McGill
Area: complexity theory
Title: Optimal Algorithms and Inapproximability Results for Every CSP?
Abstract: I will go over some results from the paper "Optimal Algorithms and Inapproximability Results for Every CSP?" (Raghavendra 2008). In particular, I will explain how to obtain dictatorship tests from SDP integrality gaps. (If time allows, I might also discuss a general rounding scheme for SDPs.) Dictatorship tests can be used to obtain UG-hardness results. Using this machinery, it can be shown that every generalized constraint satisfaction problem can be optimally approximated by a simple SDP.
2010/11/04 Theory Place: MC320
Time: 16:00 - 17:30
Speaker: Pranab Sen
Affiliation: Tata Institute of Fundamental Research
Area: complexity theory
Title: Information theoretic techniques in communication complexity theory
Abstract: This is the second talk by Pranab Sen. He will continue to talk about information theoretic techniques in communication complexity theory. The room is McConnell 320
2010/10/28 Theory Place: MC320
Time: 15:00 - 17:00
Speaker: Pranab Sen
Affiliation: Tata Institute of Fundamental Research
Area: complexity theory
Title: Information theoretic techniques in communication complexity theory
Abstract: This week we start the season at 3pm on Thursday (October 28). We are very pleased to have Pranab Sen, a professor from Tata Institute who is visiting McGill. He will talk about information theoretic techniques in communication complexity theory. The room is McConnell 320.
2010/10/27 CQIL - Cryptography and Quantum Information Place: McConnell Engineering 320
Time: 15:00 - 16:00
Speaker: Saikat Guha
Affiliation: Raytheon BBN Technologies
Area: quantum information theory
Title: Introduction to the Quantum Theory of Optical Communications
Abstract: Communication theory applied to optical channels is routinely carried out using the semiclassical theory of photodetection. Development of nonclassical light sources during the recent years--whose photodetection statistics require the use of quantum theory--plus increasing interest in optics-based approaches to quantum information processing necessitates a thorough understanding of the similarities and distinctions between the semiclassical and quantum theories of optical communications. This talk will be addressed to that need, focusing, for convenience, on the free-space optical communication channel. The quantum version of the Huygens-Fresnel diffraction will be reviewed, along with the semiclassical and quantum theories of direct, homodyne, and heterodyne detection. We will review our recent work that has established the gaps between the ultimate limit to channel capacity as permitted by the laws of quantum mechanics, and the well-known Shannon capacity limits that we know how to achieve today using conventional optical receivers. The talk will introduce a few simple examples of receiver mechanisms that are capable of attaining higher channel capacity than what can be achieved by any collection of single-channel-use measurements. Such joint-detection receivers, which act inseparably on multiple channel symbols, will be needed to approach capacity performance close to the quantum limit. This talk will bring up several interesting facets of quantum measurement, information theory, and optical communications, and will review recent work and several open problems in the area of quantum-limited optical communications. Biography of Speaker:

Saikat Guha currently works for Raytheon BBN Technologies in Cambridge, MA. He received his B.Tech. in Electrical Engineering from Indian Institute of Technology (IIT) Kanpur in May 2002, and S.M. in EECS from MIT in February 2004 with a thesis on capacities of free-space quantum optical communication channels. Saikat represented India as a part of the first Indian team of five students at the 29th International Physics Olympiad at Reykjavik, in July 1998 where he received the European Physical Society (EPS) award for the experimental component. He carried out his doctoral research under the supervision of Prof. Jeffrey H. Shapiro at the Optical and Quantum Communications Group of Research Laboratory of Electronics (RLE), MIT. He earned his Ph.D. in June 2008 from the department of EECS, MIT, with a thesis on multiple-user quantum information theory for quantum-optical channels. His current research interests include fundamental limits of single and multiple-user quantum-limited optical communications, quantum Shannon theory, quantum limits to optical sensing, network information theory, and quantum error correction.


2010/10/07 CIM - Centre for Intelligent Machines Place: Trottier Bldg., 1100
Time: 16:00 - 17:00
Speaker: Phillip Holmes
Affiliation: Department of Mechanical and Aerospace Engineering Princeton University
Title: The Neurodynamics of Simple Decisions: Drift-diffusion Equations as Models for Single Brains, and fo
Abstract: I will describe how simple stochastic differential equations can model evidence accumulation and decision making, sketching their derivation from biophysically-detailed models of spiking neurons, and relating them to the sequential probability ratio test from statistical decision theory. This connection yields a speed-accuracy tradeoff that optimizes rewards in a simple two-alternative perceptual decision task. I will compare the resulting model predictions with human behavior and advance explanations for failures to optimize. Finally, I will show how drift-diffusion models can be extended to describe choices in a social gambling task in which players receive limited information regarding other group members' choices and rewards. Biography of Speaker:

Since 1994 he has been Professor of Mechanics and Applied Mathematics at Princeton University, where he directed the Program in Applied and Computational Mathematics until 1997. He is an associate faculty member in the Department of Mathematics. In 1981 he was a Visiting Scholar in the Department of Mathematics at the University of California , Berkeley. From 1981-86 he was Director of the Center for Applied Mathematics at Cornell. In 1985-86 he held the Chaire Aisenstadt of the Centre de Recherches Mathematiques, Universite de Montreal; in 1988-89 he was a Sherman Fairchild Distinguished Scholar at the California Institute of Technology and, in 1993-94, a John Simon Guggenheim Memorial Fellow. He was elected a Fellow of the American Academy of Arts and Sciences in 1994. In January 2000 he held a Visiting Professorship at the Paul Erdös Mathematical Center, Budapest, Hungary, and in 2001 he was elected an Honorary Member of the Hungarian Academy of Sciences. Dr Holmes teaches courses at all levels from freshman to advanced graduate, and conducts seminars in dynamics and applied mathematics. He helped Ingrid Daubechies develop 'Math Alive:' an applied mathematics course for non-science majors. He has published over 200 papers, articles and reviews. He has supervised 30 PhD. and 3 MSc theses, mentored 17 postdoctoral fellows, and he currently has five PhD students and four postdoctoral fellows working with him.


2010/09/13 General Place: MC13
Time: 15:30 - 16:30
Speaker: Various
Affiliation: McGill University
Title: Soup and Science, 10th Edition
Abstract: Soup and Science is held for one week at the start of each fall and winter term. Each day at lunch, undergraduate science students are invited to see and hear some of our coolest professors give short presentations about their research. Then as you mingle over lunch, you will be able to find out more about their research and how you can participate. Come and discover some of the opportunities that exist both within and outside your own departments.

web casts
2010/09/11 CIM - Centre for Intelligent Machines Place: Room G-10 , Macdonald-Harrington Building
Time: 17:30 - 18:30
Speaker: Friedrich Pfeiffer
Affiliation: Technical University Munich Angewandte Mechanik, Germany
Title: On Biological and Artificial Walking
Abstract: Walking is a fascinating invention of nature. It is versatile, flexible and perfectly adapted to a natural environment. Walking in its various realizations enables the biological systems to have access to all natural structures of the earth. Walking realizes motion, and motion with motion planning is the basis for intelligence, as modern biologists say. If intelligence is defined as the ability to deal with unknown and new situations biological motion, both mental and physical, can be considered as a manifestation of intelligence. Walking has been detected by engineers some 20-30 years ago, although before that time numerous trials had been made to realize some mechanisms with walking capabilities. Nowadays the computer age and a large variety of sophisticated technologies give walking machine realizations a high probability of success, which can best be seen in Japan. My group at the Technical University of Munich started in 1989 to design and to realize walking machines, partly in cooperation with neurobiologists specialized in biological walking problems. The presentation will touch some problems connected with machine walking, especially in the fields of design, dynamics, control and stabilization. It will also discuss some of the open questions connected with walking, especially stabilization problems. Finally, the chances of walking machines will be discussed. For further details, click here.