Prof. I. G. Sarma Memorial Lecture

Department of Computer Science and Automation
Indian Institute of Science
NAVIGATION

Vectors, Probability, and Algorithms

by

Prof. Ravindran Kannan

Adjunct Professor, Dept. of CSA, IISc
Principal Researcher, Microsoft Research India
and
Recipient of Knuth Prize, 2011 and
Fulkerson Prize In Discrete Mathematics, 1991


Venue: Faculty Hall, Indian Institute of Science
Date: Friday, July 22, 2011
Time: 4 - 5 PM

Professor P. Balaram, Director, IISc, will preside.

 

 

Click here to download the poster.

 

 

A B S T R A C T

Title: Vectors, Probability, and Algorithms


  • Is a document just a 25000 dimensional vector?
  • Are dot products, orthogonality, eigenvectors and values of any practical use in the 25000 dimensional space?
  • Can you summarize the collection of all new articles of the last year by a small random sample collected on the fly?
  • How many random samples do you need to do linear regression in 20000 dimensional space?
The talk will discuss (from first principles) recent research from Theoretical Computer Science and Mathematics bearing on these questions.






A B O U T   T H E   S P E A K E R

Ravindran Kannan is currently a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also an adjunct faculty member of CSA, IISc. Earlier, he was the William K. Lanman Jr. Professor of Computer Science and Professor of Applied Mathematics at Yale University. He has also taught at MIT and CMU. Ravi Kannan did his B.Tech at IIT, Bombay and PhD at Cornell University. His research interests include Algorithms, Theoretical Computer Science, and Mathematics.















A B O U T   P R O F.   I.   G.   S A R M A   M E M O R I A L   L E C T U R E

The prestigious lecture was instituted in 1997 in memory of Professor I.G. Sarma, the founding chairperson of the Department of Computer Science and Automation (then called the School of Automation) during 1971-1979. His tenure as the chairman, Centre for Continuing Education and later as the Dean, Faculty of Engineering was marked by many important academic and education initiatives being launched at the Indian Institute of Science. The talk by Professor Ravi Kannan will be the seventh in the series of lectures.







A B O U T   T H E   K N U T H   P R I Z E

The Donald E. Knuth Prize is awarded for outstanding contribution to the foundations of computer science, named after the legendary computer scientist Donald E. Knuth. This prestigious prize is awarded by ACM and IEEE Computer Society for major research accomplishments and contributions to the foundations of computer science over an extended period of time.










O R G A N I Z A T I O N

The lecture is organized by Faculty, Students and Staff of the Department of Computer Science and Automation, Indian Institute of Science, Bangalore.

For queries, contact office@csa.iisc.ernet.in.










P O S T E R

Please feel free to send the poster or the link to this website to your colleagues.

Click on the image for larger view.



B I T S   N   B Y T E S
Fun for Programming Geeks!

Time: 10:45 -- 11:45 (Prelims) and 16:00 -- 17:30 (Finals).
Venue: CSA Seminar Hall (Prelims) and Intel Lab (Finals).

Bits N Bytes is our Online Programming Contest for geeks who love problem solving, to pit their programming and problem solving skills against others on our online codechecker.

The contest will be at the department of CSA, IISc and is also open over the Internet. So if you unable to visit IISc on Open Day, you can still participate from home! However, on-site teams are eligible for attractive prizes! Please visit the contest site, register your team, get used to the interface, and submit solutions to a few practice problems.

Team Composition
This is a team event with a maximum of two participants in each team. Team members need not be from the same organisation.

Rounds
There will be two on-site rounds of the contest as follows.
  • Preliminary Round:  This will be paper based and of 45 minutes duration. Top 8 teams from this round will qualify for the final programming round.
  • Final Programming Round:  This round consists of algorithm oriented programming problems that have to be solved under given time and space constraints.
Programming Languages Supported
C, C++

Environment
The teams in the Programming Round will be a given a Linux machine each. The gcc compiler that comes with it will be sufficient to write programs that will run on the online tester. Teams submit only source code. The Online Judge will compile your program and run them against a predefined set of test cases and match the results. Input and Output formats will be specified clearly in the problem statement. Please adhere to them carefully to ensure that your submission does not fail because of incorrect output formatting.
The compiler commands for C and C++ are as follows:
     gcc -O2 program.c -o program
     g++ -O2 program.cpp -o program


Prizes & Certificates 
The top three teams in the on-site Programming Round will receive attractive prizes and all the finalist teams will receive a certificate of participation. Judges' decision will be final.

Registration
Please register on this form if you plan to come to IISc to participate in this event. This is only an informal registration to help us plan. There will be a formal registration later. The registration is free.

Contact
If you have any questions, please feel free to contact Aditya.


G E D A N K E N

Time: 10:00 -- 10:45 (Prelims), 12:45 -- 13:00 (Finals question paper distribution) and 16:00 -- 16:15 (Finals answer paper submission).
Venue: CSA Seminar Hall.

Description.
Gedanken is a problem solving contest that involves mathematical, logical, Computer Science related problems and puzzles.

Rounds.
There will be two rounds: Prelims and Finals. Both the rounds will be written.
The participants would be given a set of questions and a time-line. They have to write answers on the sheets of paper provided and submit to the organizers.

Team Composition.
Maximum two participants per team.

Prizes & Certificates.
There will be an attractive prize for the first and the second winners. All finalists will receive certificates of participation. Judges' decision will be final.

Contact
If you have any questions, please feel free to contact subramanya@csa.iisc.ernet.in.


R A N D O M   A C C E S S

Time: 16:00 -- 17:30 (Prelims + Finals).
Venue: E-Classroom, CSA.

Description
For all the quiz enthusiasts, we are organizing Random Access, a technical quiz contest. The contest will involve questions related to computer science field.

Rounds
There will be two rounds.
  • Preliminary Round:  It will involve a written quiz.
  • Final Round:  This will be an oral quizzing round for the people clearing the preliminary round.

Team Composition
Maximum two participants per team.

Registration
Participants have to register on the day of the event at CSA department. Registration is free!

Prizes & Certificates.
There will be attractive prizes for the first, second and third winners. All finalists will receive certificates of participation. Judges' decision will be final.

Contact
If you have any questions, please feel free to contact mayuresh@csa.iisc.ernet.in.


O P P O R T U N I T I E S   A T   C S A

Department of Computer Science and Automation is a pioneering academic centre for higher education, research, and innovation in key areas of computer science. The driving mission for the department is to advance the frontiers of research in computer science and automation and impart world-class training in computer science to students.

There are several ways in which one can become a part of the vibrant community of the CSA Department. This interactive session would give you an overview of all these opportunities. CSA faculty would help you shape your future to take a dip into the ocean of knowledge represented by Indian Institute of Science. You can get your career related queries answered in the session.

Specifically, this talk would focus on ME, MSc and PhD programs of the department and their prerequisites. It would also highlight Internships, Project Assistantships, Research Assistantships, and other academic ways to be associated with CSA.



F E E D B A C K

Thank you everyone for your valuable comments. These would help us improve.

Dr. M.K. Sridhar, National Degree College, Bangalore.
'Open Day' program of IISc on Feb 26, 2010 has certainly opened up new vistas to young students in various professional courses. The department of CSA has contributed significantly for the R&D of IT in India and globally as well. Hearty congratulations for the staff, research students and office staff for doing a great academic service under the very efficient dynamic chairmanship of Prof. Y. Narahari.

Hiti Saini, Christ University, Bangalore.
Impression about CSA Open Day: Challenging.
Suggestions: There should be more events. Contact numbers should be given on brochures.

Avinash Krishnan R., MSRIT, Bangalore.
Most liked event: Demos (Graphics Lab > Game Theory Lab > ...).
Suggestions: More technical talks.

Taral Shah, Christ University, Bangalore.
Most liked event: Technical Quiz.
Impression about CSA Open Day: Excellent.

Sinny Kumari, DSI, Bangalore.
Most liked event: Puzzle solving.
Impressions about CSA Open Day: It is a very good place and programs and events were very good.
Suggestions: Give certificates to all the participants.

Sudhendu Kumar, BMSCE, Bangalore.
Most liked event: Programming contest.
Impression about CSA Open Day: Impressive, exposure gaining.
Suggestions: Try not to clash events.

Vipin Nair, Christ University, Bangalore.
Most liked event: Technical Quiz.
Impression about CSA Open Day: Very nice. Excellent.

Shantanu Tushar, BMSCE, Bangalore.
Most liked event: Programming contest.
Impression about CSA Open Day: It was fun and exciting.
Suggestions: There wasn't enough space for the attendees for some seminars.

Adarsh J., MSRIT, Bangalore.
Most liked events: All the demos.
Impression about CSA Open Day: A great opportunity to interact with intelligent minds. The event should be happening more number of times.
Suggestions: Goodies were missing :(.

Swaroop S.M., Christ University, Bangalore.
Most liked event: Technical Quiz.
Impression about CSA Open Day: Challenging.
Suggestions: Addition of more events.


W I N N E R S

Hearty congratulations to all the winners.

Event Winner First Runner-up Second Runner-up
Gedanken -- Puzzle SolvingBruhati H.S. &
Madhuri Venkatesh
Govindaray M. Naik &
Benhur Chetak D'Souza
   -- and --
Harinarayanan S. &
Janakiraman V.
Bits N Bytes -- Programming ContestAvinash Krishnan &
Adarsh
Anil C.R. &
Anish
Manu C. &
Bharath S. Kallur
Random Access -- Technical QuizCoca Sai Prajeeth &
Ameen Mohammed
Ganapathy S.E.K. &
Basavaraj Talwar
Amal Antony &
Mahima Sivasankar