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 e-mail with details. Thanks!

Date	Topic	Topic References	Presenter
Jan. 12	Singular Value Decomposition	Singular Value Decomposition and Missing Values (abstract)	Prof. Paul Purdom
Jan. 19	Defining BPP and PCP Complexity Classes, pt. 1	PCP - Probabilistically Checkable Proof BPP - Bounded Error, Probabilistic, Polynomial time	Christopher Cole
Jan. 26	Defining BPP and PCP Complexity Classes, pt. 2		Christopher Cole
Feb. 2	Basic Computational Geometry	Ch. 33: Introduction to Algorithms	Christine Task
Feb. 9	Bayesian Filtering	Ch. 2: Probabilistic Robotics On sequential Monte Carlo sampling methods for Bayesian filtering	Jeff Johnson
Feb. 16	Complexity of Finding Nash Equilibria		Christopher Cole
Feb. 23	Higher Order Complexity		Ramyaa Ramyaa
Mar. 2	Particle Filtering	Ch. 4: Probabilistic Robotics Particle Filters and their Applications An Implementation	Jeff Johnson
Mar. 9	Probabilistic Roadmap Motion Planning	Path Planning in Expansive Configuration Spaces Randomized Kinodynamic Motion Planning with Moving Obstacles On the Probabilistic Foundations of Probabilistic Roadmap Planning	Prof. Kris Hauser
Mar. 23	Minimizing Communication in Linear Algebra	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 in-expressiveness result for query languages	Abstract	Prof. Van Gucht

Members

In no particular order, these are the current members of the group:

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; worst-case and average-case analysis, amortized analysis, dynamization. Comparison-based algorithms: search, selection, sorting, hashing. Information extraction algorithms (graphs, databases). Graphs algorithms: spanning trees, shortest paths, connectivity, depth-first search, breadth-first 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, non-formalizability 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 block-recursive perspective on arrays.

Sites

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¹⁰⁰)? 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¹⁰⁰, ε > 0. (And, technically, ε must be chosen so that n^99+ε is "time-computable.") So, this question is really getting at constructing a reasonably natural language that takes Θ(n¹⁰⁰) 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¹⁰⁰) runtime, which is pretty easy for any decidable language.
Any ideas?

-Chris Cole