Research Notes

African populations and the evolution of human mitochondrial DNA	On finding minimal length superstrings	A 2.5-approximation algorithm for shortest superstring
Lecture notes on evolution trees	Approximate matching of polygonal shapes	How to reconstruct a large genetic network from n gene perturbations in fewer than n² easy steps
Applications of symbolic logic to gene regulation systems	The full Steiner tree problem	An algorithm for the Steiner problem in graphs
Algorithms for identifying Boolean networks and related biological networks based on matrix multiplication and fingerprint function	The Church-Turing thesis: breaking the myth	Probabilistic coloring of bipartite and split graphs
An algorithm for the Steiner problem in graphs (revisit in Nov. 16, 2005)	Approximating the minimum spanning tree weight in sublinear time	A simple linear time algorithm for the domatic partition problem on strongly chordal graphs
Evaluation algorithms for NOR circuits and min-max principle	Stable marriage problem and the coupon collector's problem	The Chernoff bounds
A randomized approximation scheme for metric MAX-CUT	Introduction to property testing	Three theorems regarding testing graph properties (the first theorem)
Constructing phylogenies from quartets: elucidation of eutherian superordinal relationships	New fixed-parameter algorithms for the minimum quartet inconsistency problem	Introduction to the Regularity Lemma
Testing k-colorability	A characterization of easily testable induced subgraphs (I)	Ph.D. Dissertation Proposal
An example of property testing with a two-sided error and with a one-sided error	A characterization of easily testable induced subgraphs (II)	Clusters and quartenary relations
Equitable coloring extends Chernoff-Hoeffding bounds	Testing induced P₃-freeness	Computing branching numbers
Complement reducible graphs	Finding and counting given length cycles	A faster algorithm for the single source shortest path problem with few distinct positive lengths
Testing expansion in bounded-degree graphs	Testing cycle-freeness in bounded-degree graphs	Computing the girth of a planar graph
On positive influence dominating sets in social networks	A greedy, graph-based algorithm for the alignment of multiple homologous gene lists	Testing tree-consistency with k missing quartets
Testing if a bounded-degree graph has a simple k-path	Slides for Ph.D. Dissertation Oral Defense	Evolutionary conserved elements in vertebrate, insect, worm, and yeast genomes
Accurate identification of A-to-I RNA-editing in human by transcriptome sequencing	Identification of widespread ultra-edited human RNAs	Accurate identification of human Alu and non-Alu RNA editing sites
A survey of genomic traces reveals a common sequencing error, RNA editing, and DNA editing	Landscape of transcription in human cells	Global regulation of alternative splicing by adenosine deaminase acting on RNA (ADAR)
Global regulation of alternative splicing by adenosine deaminase acting on RNA (ADAR)	Features of evolutionarily conserved alternative splicing events between Brassica and Arabidopsis	Shotgun proteomics aids discovery of novel protein-coding genes, alternative splicing, and resurrected pseudogenes in the mouse genome
Pattern matching with don’t cares and few errors	Simple approximate equilibria in large games	On discrete preferences and coordination
Revenue and Reserve Prices in a Probabilistic Single Item Auction	Aggregating partial rankings with applications to peer grading in massive online open courses	The K-armed dueling bandits problem
Celebrity games	Query complexity of approximate equilibria in anonymous games	epsilon-covers and Nash equilibrium computation
Discretized multinomial distributions and Nash equilibria in anonymous games	Sampling correctors	Of the people: voting is more effective with representative candidates
Competing bandits: Learning under competition	How good is a two-party election game?	No-Regret Online Learning Algorithms
When do prediction market makers make profits?	Network Creation Games plus Social Network Creation	A Sketch of Nash's Theorem from Fixed Point Theorems
Online Learning for Min-Max Discrete Problems