Algorithms Reading Group
Main Menu
About
We'll be focusing on topics in algorithm theory with special emphasis given towards the end of the sessions to currently active areas of algorithms research.
We meet weekly on Tuesdays, from 5 p.m.  6 p.m. in Lindley Hall, room 101. Spring break week we will not be meeting. See the calendar for details on each meeting (topic, presenter, etc.). The meetings are open to all, please feel free to drop by any time.
If you'd like to be added to the mailing list for the group, drop me a line: jj56@indiana.edu.
Schedule
This is our schedule of speakers for Spring 2010 (although it is, like all things in life, subject to change). We still have openings, so if you'd like to speak on a given date, click it to send me an email with details. Thanks!
Date  Topic  Topic References  Presenter 

Jan. 12  Singular Value Decomposition  Prof. Paul Purdom  
Jan. 19  Defining BPP and PCP Complexity Classes, pt. 1  Christopher Cole  
Jan. 26  Defining BPP and PCP Complexity Classes, pt. 2  Christopher Cole  
Feb. 2  Basic Computational Geometry 

Christine Task 
Feb. 9  Bayesian Filtering  Jeff Johnson  
Feb. 16  Complexity of Finding Nash Equilibria  Christopher Cole  
Feb. 23  Higher Order Complexity  Ramyaa Ramyaa  
Mar. 2  Particle Filtering  Jeff Johnson  
Mar. 9  Probabilistic Roadmap Motion Planning  Prof. Kris Hauser  
Mar. 23  Minimizing Communication in Linear Algebra  Nilesh Narayanrao Mahajan  
Mar. 30  Satisfiability  Prof. Paul Purdom  
Apr. 6  Introduction to Factoring of Integers  Prof. Paul Purdom  
Apr. 13  Generic Programming  Prof. Andrew Lumsdaine  
Apr. 20  Algorithms in SAT/SMT Solvers  Nilesh Narayanrao Mahajan  
Apr. 27  Factoring of Integers  Paul Grubbs  
May. 4  On expressiveness and inexpressiveness result for query languages  Prof. Van Gucht 
Members
In no particular order, these are the current members of the group:
 Christine Task
 Christopher Cole
 Minh Tang
 Jeff Johnson
 Nilesh Narayanrao Mahajan
 Ramyaa Ramyaa
 Emel Gencer
 Girish Subramanian
 ChinHua Kong
 Brent Castle
 Torsten Hoefler
 Adrija Sen
 Prashnat R. Singhal
 Jong Choi
 Ben Kovitz
 Damien Sullivan
 Ammar Halabi
 Rebecca Ingram
 Mike Hansen
Resources
Courses
 B502 Computational Complexity (3 cr.) P: B501. Study of computational complexity classes, their intrinsic properties, and relations between them. Topics include time and space computational complexity. Reducibility and completeness of problems within complexity classes. Complexity of optimization problems. Complexity hierarchies. Relativization of the P =? NP conjecture. Parallel computation models and the class NC.
 B503 Algorithms Design and Analysis (3 cr.) P: Mathematics M216 and C343. Models, algorithms, recurrences, summations, growth rates. Probabilistic tools, upper and lower bounds; worstcase and averagecase analysis, amortized analysis, dynamization. Comparisonbased algorithms: search, selection, sorting, hashing. Information extraction algorithms (graphs, databases). Graphs algorithms: spanning trees, shortest paths, connectivity, depthfirst search, breadthfirst search. Credit not given for both B503 and B403.
 B510 Introduction to Applied Logic (3 cr.) Structures: relations between structures, term structures. Description: notation and meaning, substitution operations, first order formulas, database languages, program verification conditions, semantics valuation, normal forms, quantifier reduction, axiomatic theories. Proof: resolution, sequential calculi, natural deduction, automated theorem proving, semantic completeness. Limits of formalization: compactness, undecidability of truth, undecidability of canonical theories, nonformalizability of database theory.
Faculty
 Paul W. Purdom: Analysis of algorithms, rewriting systems, compilers, game playing, and singular value decomposition.
 David S. Wise: Current research interests pursue a paradigm for for solving matrix problems, specifically with a blockrecursive perspective on arrays.
Sites
 http://rjlipton.wordpress.com/
 http://blog.computationalcomplexity.org/
 Complexity Zoo
 Beer & Algorithms
Literature
 Probabilistic Robotics
 Introduction to Algorithms
 The Analysis of Algorithms
 Computational Complexity: A Modern Approach
 Computational Geometry Introduction
 Computational Geometry Lecture Notes
 Randomized Algorithms (Amazon  Google Books): This book is available online at no cost through the IU Library.
 Introduction to Algorithms (CLRS) (Amazon  Google books)
Questions for the Group
 Can you construct a language that can only be solved by an algorithm running in time Θ(n^{100})? One of the arguments for polynomial time being tractable is that "often when an algorithm is found for a problem where the polynomial has high degree, a refinement is found that significantly reduces the degree." So is this a conjecture on a property of P, or is just that practical problems tend to have low degree?
The Time Hierarchy Theorem for deterministic TMs tells us, basically, that a TM that runs for a longer time can decide more languages than one that is restricted to run in a shorter time. Using this, I can say that some language exists that runs in time T(n) such that n^{99+ε} < T(n) < n^{100}, ε > 0. (And, technically, ε must be chosen so that n^{99+ε} is "timecomputable.") So, this question is really getting at constructing a reasonably natural language that takes Θ(n^{100}) time to decide on a TM rather than just asserting it must exist. This is also in contrast to finding an algorithm that has Θ(n^{100}) runtime, which is pretty easy for any decidable language.
Any ideas?
Chris Cole