enter search term and/or author name
Eigenvalue bounds, spectral partitioning, and metrical deformations via flows
Punyashloka Biswal, James R. Lee, Satish Rao
Article No.: 13
We present a new method for upper bounding the second eigenvalue of the Laplacian of graphs. Our approach uses multi-commodity flows to deform the geometry of the graph; we embed the resulting metric into Euclidean space to recover a bound on the...
Amplifying lower bounds by means of self-reducibility
Eric Allender, Michal Koucký
Article No.: 14
We observe that many important computational problems in NC1 share a simple self-reducibility property. We then show that, for any problem A having this self-reducibility property, A has polynomial-size TC0...
Geometric suffix tree: Indexing protein 3-D structures
Article No.: 15
Protein structure analysis is one of the most important research issues in the post-genomic era, and faster and more accurate index data structures for such 3-D structures are highly desired for research on proteins. This article proposes a new...
A dynamic data structure for 3-D convex hulls and 2-D nearest neighbor queries
Timothy M. Chan
Article No.: 16
We present a fully dynamic randomized data structure that can answer queries about the convex hull of a set of n points in three dimensions, where insertions take O(log3n) expected amortized time, deletions take...
Improved bounds and new techniques for Davenport--Schinzel sequences and their generalizations
Article No.: 17
We present several new results regarding λs(n), the maximum length of a Davenport--Schinzel sequence of order s on n distinct symbols.
First, we prove that λs(n)...
Transitive closure logic, nested tree walking automata, and XPath
Balder Ten Cate, Luc Segoufin
Article No.: 18
We study FO(MTC), first-order logic with monadic transitive closure, a logical formalism in between FO and MSO on trees. We characterize the expressive power of FO(MTC) in terms of nested tree-walking automata. Using the latter, we show that...
A discriminative model for semi-supervised learning
Maria-Florina Balcan, Avrim Blum
Article No.: 19
Supervised learning—that is, learning from labeled examples—is an area of Machine Learning that has reached substantial maturity. It has generated general-purpose and practically successful algorithms and the foundations are quite well...