CSE Theory Seminar

Spring 2008

Wednesday 1:00pm-2:00pm, Room: ITE 336

Coordinator:   Aggelos Kiayias

Participating Faculty:   Vincent Huang , Yoo-Ah Kim , Lester Lipsky , Ion Mandoiu , Sanguthevar Rajasekaran, Alexander Russell, Laurent Michel , Alex Shvartsman


The CSE Theory Seminar (CSETS) meets weekly. Participants will give O(1) presentations during the semester, reporting on recent work (not necessarily of the presenter's) in any theoretical area of computer science. Topics include, but are not restricted to, Algorithms, Cryptography, Complexity Theory, Distributed Computing, and Semantics. Graduate Students will receive credit for participating.

Spring 2008

Date Speaker Title Abstract
1/30/2008 Aggelos Kiayias How to Collect a Function Securely? [ click here ]
2/6/2008 cancelled [ click here ]
2/13/2008 Matt Coolbeth Approximation Algorithms for Scheduling Real-Time Multicast Flows in Wireless Networks [ click here ]
2/20/2008 Matt Coolbeth        " [ click here ]
2/27/2008 Hieu Dinh Cross-Layer Latency Minimization in Wireless Network with SINR Constraints [ click here ]
3/5/2008 Hong-Sheng Zhou Equivocal Blind Signatures and Adaptive UC-Security [ click here ]
3/19/2008 Cancelled [ click here ]
3/26/2008 Alexander Russell Computation of Knot Invariants [ click here ]
4/2/2008 Sixia Chen Distance-1 Constrained Channel Assignment in Single Radio Wireless Mesh Networks [ click here ]
4/9/2008 Chadi Kari Deterministic Broadcast protocols for Ad Hoc Networks [ click here ]
4/16/2008 Solomon Berhe XML Schema Based RBAC Approach [ click here ]
4/23/2008 Narasimha Shashidar Anonymous Identification in Ad Hoc Groups [ click here ]
4/30/2008 Serdar Pehlivanoglu TBA [ click here ]

Previous in Fall 2007

9/5/2007 Aggelos Kiayias Secure Two Party Computation with a Deck of Cards [ click here ]
9/12/2007 Chadi Kari Soft Edge Coloring [ click here ]
9/19/2007 Yufeng Wu Algorithms for Reconstructing Mosaic Pattern of a set of Recombinants [ click here ]
9/27/2007 Vamsi Krishna Simple Linear Work Suffix Array Construction [ click here ]
10/03/2007 Radhika Vind Model-Driven Data Acquisition in Sensor Networks [ click here ]
10/10/2007 Hong-Sheng Zhou Universally Composable Key-Exchange [ click here ]
10/17/2007 Matthew Coolbeth Dominating and Absorbent Sets for Wireless Ad-hoc Networks with Different Transmission Ranges [ click here ]
10/24/2007 Solomon Berhe Decidability of Safety in Graph-based Models for Access Control Models [ click here ]
10/31/2007 Jorge Duitama Multiplex PCR Primer Set Selection with Amplification Length Constraints [ click here ]
11/7/2007 Hieu Dinh Approximation algorithms for Telephone Broadcast Problem and Poise Problem [ click here ]
11/14/2007 Sixia Chen Complexity and Approximation algorithm of two problems in Geometric SINR [ click here ]
11/28/2007 Mai Hamdalla Title Simulation-based analysis of E2E voting systems [ click here ]
12/5/2007 Seda Davtyan Performing work Efficiently in the Presence of Faults [ click here ]

Previous in Spring 2007

Date Speaker Title Abstract
1/24/2007 Aggelos Kiayias Zero-knowledge Proofs of Knowledge [ click here ]
1/31/2007 Serdar Pehlivanoglou Broadcast encryption [ click here ]
2/07/2007 Kentros Sotiris Fast Paxos by Leslie Lamport [ click here ]
2/14/2007 Cancelled (Due to Snow) [ click here ]
2/21/2007 Hieu Dinh On Semidefinite Programming Relaxations for Graph Coloring and Vertex Cover [ click here ]
2/28/2007 Dolly Sharma Sequence matching in large DNA databases [ click here ]
3/14/2007 Mai Hamdalla String Barcoding [ click here ]
3/21/2007 Hong-Sheng Zhou Securely Obfuscating Re-Encryption [ click here ]
3/28/2007 Seda Davtyan An Algorithm for the asynchronous Write-All Problem [ click here ]
4/04/2007 Narasimha Shashidhar Efficient Steganography with Provable Security Guarantees [ click here ]
4/11/2007 George Pantazis Auction Theory and Mechanisms [ click here ]
4/18/2007 Mohammed Ahmed Derivation of Randomized Sorting and Selection Algorithms [ click here ]
4/25/2007 Chadi El Kari Approximation algorithm for uncapacitated metric facility location [ click here ]

Previous in Fall 2006

Date Speaker Title Abstract
9/06/2006 Aggelos Kiayias Private Information Retrieval [ click here ]
9/13/2006 Ion Mandoiu The chords' problem [ click here ]
9/20/2006 Kentros Sotiris The Byzantine Generals Problem [ click here ]
9/27/2006 Dragos Trinca Data Distortion Techniques for Privacy-preserving Data Mining [ click here ]
10/4/2006 Michael Korman The Zero-One Law for Graphs [ click here ]
10/11/2006 Serdar Pehlivanoglou Collusion Resistant Broadcast Encryption [ click here ]
10/18/2006 George Pantazis Security for Multicast Communication [ click here ]
10/25/2006 Jin Jun Off-target search algorithm for siRNA [ click here ]
11/01/2006 Justin Kennedy Incomplete Directed Perfect Phylogeny [ click here ]
11/08/2006 Bogdan Pasaniuc Set Covering approach for Reconstruction of Sibling Relationships [ click here ]
11/15/2006 Laurent Michel Automatic Differentiation in Constraint-Based Local Search [ click here ]
11/29/2006 Hong-Sheng Zhou Efficient and Adaptive Blind Signatures in the Universal-Composability Framework [ click here ]
12/06/2006 Rania Kilany A Transaction Mapping Algorithm for Frequent Itemsets Mining [ click here ]

Previous in Spring 2006

Date Speaker Title Abstract
1/18/2006 Aggelos Kiayias Verifiable Anonymous Encryption [ click here ]
2/8/2006 Vishal Tharpar A Text Summarizer Based on Meta-Search [ click here ]
2/22/2006 Peng Xie A Key Management Scheme for Wireless Sensor Networks Using Deployment Knowledge [ click here ]
3/01/2006 Ramandeep Kaur SACA: SCM-based Adaptive Clustering Algorithm [ click here ]
3/15/2006 Cancelled [ click here ]
3/22/2006 Yoo-Ah Kim A robust maximum completion time measure for scheduling [ click here ]
3/29/2006 Jin Jun An Approximation Algorithm for Haplotype Inference by Maximum Parsimony [ click here ]
4/05/2006 Bogdan Pasaniuc Approximation algorithms for selection of Robust Tag SNPs [ click here ]
4/12/2006 Sabhay Kapoor Detecting False Matches in String-Matching Algorithms [ click here ]
4/19/2006 Yona Raekow Selectively Traceable Anonymity [ click here ]
4/26/2006 Osama Saeed Khan Optimally Scheduling Video-on-Demand to Minimize Delay When Server
and Receiver Bandwidth May Differ
[ click here ]

Previous in Fall 2005

Date Speaker Title Abstract
8/31/2005 Aggelos Kiayias Introduction
9/7/2005 Ion Mandoiu Exact and Approximation Algorithms for DNA Tag Set Design [ click here ]
9/14/2005 Michael Korman Filtering of Injected False Data in Sensor Networks [ click here ]
9/21/2005 Gorjan Alagic The Shortest Vector Problem [ click here ]
9/28/2005 Ibrahim Saleh Using S-Tree Structure for Lossless Image Compression [ click here ]
10/5/2005 David Keil Interaction, Direct and Indirect [ click here ]
10/12/2005 Jin Jun Finding founder sequences [ click here ]
10/19/2005 Sotirios Kentros Snakes, Shapes, and Gradient Vector Flow [ click here ]
10/26/2005 Dalia Terhesiu From dynamical complexity to structural complexity [ click here ]
11/2/2005 Justin Kennedy On Sorting by Translocations [ click here ]
11/2/2005 Fan Zhang Smartcards with biometric user verification [ click here ]
11/9/2005 Nicolaos Nicolaou Time-efficient implementations of atomic read/write registers [ click here ]
11/16/2005 Hai Yan The Sybil Attack in Sensor Networks: Analysis & Defenses [ click here ]
11/16/2005 Shirin Safa [ click here ]
11/30/2005 Hong-Sheng Zhou Private Searching on Streaming Data [ click here ]
12/7/2005 Chadi Kari On the Cost and Benefits of Procrastination [ click here ]
12/7/2005 Vishal Tharpar Finding composite regulatory patterns in DNA Sequences [ click here ]
12/14/2005 Ramandeep Kaur Finding Subtle Motifs by Branching from Sample Strings [ click here ]
12/14/2005 David Walluck Program Obfuscation [ click here ]

Previous in Spring 2005

Previous in Fall 2004:

Date Speaker Title Abstract
12/8/2004 Hong-Sheng Zhou Short Signatures Without Random Oracles [ click here ]
12/8/2004 Peng Xie Statistical En-route Filtering and Sensor Networks [ click here ]
12/1/2004 Claudia Prajescu String Barcoding Problem [ click here ]
12/1/2004 Gorjan Alagic The Local Lemma [ click here ]
11/17/2004 Chadi El Kari Collaborative Filtering [ click here ]
11/17/2004 Sandeep Suresh Regular languages in Constraing Programming [ click here ]
11/10/2004 Jin Jun Bayesian Methods for Haplotype Inference [ click here ]
11/3/2004 Andrew See Symmetry Breaking in Constraint Programming [ click here ]
10/27/2004 Nicolaos Nicolaou How Fast can a Distributed Atomic Read be? [ click here ]
10/20/2004 Rehab El Khabourtly Motif Finding Approaches [ click here ]
10/20/2004 Dragos Trinca A BWT-based Compression Scheme [ click here ]
10/13/2004 Jaime Davila A Tight Analysis of the Greedy Algorithm for Set Cover [ click here ]
10/6/2004 Bogdan Pasaniuc Haplotype inference -- a parsimony approach [ click here ]
9/29/2004 Yuan Su Pancake Sorting by Prefix Reversal [ click here ]
9/22/2004 Yona Raekow CAPTCHA: Using hard AI Problems for security [ click here ]
9/15/2004 Dave Walluck Hash Functions and Collisions [ click here ]
9/8/2004 Michael J. Korman Secure Electronic Voting [ click here ]
9/1/2004 S. Student How not to give a (theory) talk! [ click here ]

Previous in Spring 2004:

Date Speaker Title Abstract
4/28/2004 Nicolas Nicolaou Cake-Cutting is Not a Piece of Cake. [ click here ]
4/28/2004 Yona Raekow Information Theoretic Steganography. [ click here ]
4/21/2004 Narasimha Shashidhar A Network Design Game [ click here ]
4/14/2004 Andrew See Cancelled [ click here ]
4/7/2004 Kishori Konwar The Join Problem in Dynamic Network Algorithms [ click here ]
3/31/2004 Sandeep Suresh Kumar Using Approximated Consistency for Knapsack Constraints [ click here ]
3/24/2004 Peter Musial Formal Specification of Distributed Systems: Reasoning about RAMBO [ click here ]
3/17/2004 German Finez Revisiting the Anderson-Woll algorithms [ click here ]
3/3/2004 Yuan Su A* and Time Complexity [ click here ]
2/25/2004 Cancelled [ click here ]
2/18/2004 Michael Korman The Secure Sockets Layer [ click here ]
2/11/2004 Alex Russell The probabilistic method, Ramsey theory, and minimum cuts [ click here ]
2/4/2004 Cancelled [ click here ]
1/28/2004 Moshe Y. Vardi Automated Verification = Graphs, Automata, and Logic [ click here ]
1/21/2004 Aggelos Kiayias Who signed what? [ click here ]

Fall 2003

Date Speaker Title Abstract
12/3/2003 Yuan Su PRIMES in P [ click here ]
11/19/2003 Liyuan Yu Solving the Maximum Clique Problem with Constraint Programming [ click here ]
11/12/2003 German Finez Efficient Algorithms for the Asynchronous Write-All Problem [ click here ]
11/5/2003 Andrew See An Incremental Algorithm for a Generalization of the Shortest Path Problem [ click here ]
10/29/2003 Peter Musial RAMBO with Incremental Gossip and Leave Protocol [ click here ]
10/22/2003 Yona Raekow A stateful steganographic protocol [ click here ]
10/15/2003 Narasimha Shashidhar When trees collide: An approximation algorithm for the generalized Steiner problem on networks. [ click here ]
10/8/2003 Chryssis Georgiou Efficient Gossip and Robust Distributed Computation [ click here ]
10/1/2003 Lester Lipsky Heavy-tailed (or Power-Tailed) Distributions and Their Importance in Computer Science [ click here ]
9/24/2003 Cancelled
9/17/2003 Aggelos Kiayias Public-Key Traitor Tracing and Revoking [ click here ]
9/10/2003 Ion Mandoiu Approximation Algorithms for the QoS Steiner Tree Problem [ click here ]
9/9/2003 Stathis Zachos Combinatory Complexity: Operators on Complexity Classes [ click here ]

Spring 2003