Skip to main content
Open Access Publications from the University of California

Department of Computer Science & Engineering

There are 775 publications in this collection, published between 1998 and 2022.
Technical Reports (238)

Exponential Separation of Res(k) and Res(k+1)

For each $k \geq 1$, we give a famiily of unsatisfiable sets of clauses which have polynomial size ${\mbox{Res}}(k+1)$ refutations, but which require ${\mbox{Res}}(k)$ refutations of $2^{n^{\epsilon_k}}$. This improves the superpolynomial- separation between resolution and ${\mbox{Res}}(2)$ given by Bonet and Galesi to exponential. As a corollary, we obtain an exponential separation between depth 0 Frege and depth 1 Frege, improving upon the superpolynomial separation given by the weak pigeonhole principle.

Pre-2018 CSE ID: CS2002-0697

Approximation Methods for Thin Plate Spline Mappings and Principal Warps

The thin plate spline (TPS) is an effective tool for modeling coordinate transformations that has been applied successfully in several computer vision applications. Unfortunately the solution requires the inversion of a p x p matrix, where p is the number of points in the data set, thus making it impractical for large scale applications. In practical applications, however, a surprisingly good approximate solution is often possible using only a small subset of corresponding points. We begin by discussing the obvious approach of using this subset to estimate a transformation that is then applied to all the points, and we show the drawbacks of this method. We then proceed to borrow a technique from the machine learning community for function approximation using radial basis functions (RBFs) and adapt it to the task at hand. Using this method, we demonstrate a significant improvement over the naive method. One drawback of this method, however, is that is does not allow for principal warp analysis, a technique for studying shape deformations introduced by Bookstein based on the eigenvectors of the p x p bending energy matrix. To address this, we describe a third approximation method based on a classic matrix completion technique that allows for principal warp analysis as a by-product. By means of experiments on real and synthetic data, we demonstrate the pros and cons of these different approximations so as to allow the reader to make an informed decision suited to his or her application.

Pre-2018 CSE ID: CS2003-0764

A Co-Phase Matrix to Guide Simultaneous Multithreading Simulation

Simultaneous Multithreading (SMT) architectures are appearing in commercial processors, yet there is still relatively little support for sampling or determining where to simulate to achieve representative simulation results. The challenge in creating a sampling approach to SMT is determining how far to fast-forward each individual thread between samples. Determining how far to accurately fast-forward each individual thread will vary as the threads execute through different phases of execution, and between different architecture configurations. In this paper, we examine using individual program phase information to guide simulation for Simultaneous Multithreading. This is accomplished through creating what we call a Co-Phase Matrix. The co-phase matrix represents the performance and throughput of the potential combination of the phase behavior found in multiple programs when run together. The co-phase matrix is populated by collecting samples of the program's phase combinations, and is used to to guide how far to fast-forward between samples. We show for a handful of SPEC program combinations that using the co-phase matrix provides an average error rates of 2.2% while replacing most detailed simulation with fast-forwarding.

Pre-2018 CSE ID: CS2003-0771

235 more worksshow all
Open Access Policy Deposits (536)

Diversity, Productivity, and Stability of an Industrial Microbial Ecosystem.

Managing ecosystems to maintain biodiversity may be one approach to ensuring their dynamic stability, productivity, and delivery of vital services. The applicability of this approach to industrial ecosystems that harness the metabolic activities of microbes has been proposed but has never been tested at relevant scales. We used a tag-sequencing approach with bacterial small subunit rRNA (16S) genes and eukaryotic internal transcribed spacer 2 (ITS2) to measuring the taxonomic composition and diversity of bacteria and eukaryotes in an open pond managed for bioenergy production by microalgae over a year. Periods of high eukaryotic diversity were associated with high and more-stable biomass productivity. In addition, bacterial diversity and eukaryotic diversity were inversely correlated over time, possibly due to their opposite responses to temperature. The results indicate that maintaining diverse communities may be essential to engineering stable and productive bioenergy ecosystems using microorganisms.

Location-specific signatures of Crohn's disease at a multi-omics scale.


Crohn's disease (CD), an inflammatory bowel disease (IBD) subtype, results from pathologic interactions between host cells and its resident gut microbes. CD manifests in both isolated disease locations (ileum or colon) or a combination of locations (ileocolonic). To date, a comprehensive understanding of how isolated CD subtypes influence molecular profiles remains outstanding. To address this, we sought to define CD location signatures by leveraging a large cross-sectional feature set captured from the stool of over 200 IBD patients and healthy controls using metaproteomics, shotgun metagenomics, 16S rRNA sequencing, metabolomic profiling, and host genetics paired with clinical endoscopic assessments.


Neither metagenomic nor host genetics alone distinguished CD location subtypes. In contrast, ileal and colonic CD were distinguished using mass spectrometry-based methods (metabolomics or metaproteomics) or a combined multi-omic feature set. This multi-omic feature set revealed colonic CD was strongly associated with neutrophil-related proteins. Additionally, colonic CD displayed a disease-severity-related association with Bacteroides vulgatus. Colonic CD and ulcerative colitis profiles harbored strikingly similar feature enrichments compared to ileal CD, including neutrophil-related protein enrichments. Compared to colonic CD, ileal CD profiles displayed increased primary and secondary bile acid levels and concomitant shifts in taxa with noted sensitivities such as Faecalibacterium prausnitzii or affinities for bile acid-rich environments, including Gammaproteobacteria and Blautia sp. Having shown robust molecular and microbial distinctions tied to CD locations, we leveraged these profiles to generate location-specific disease severity biomarkers that surpass the performance of Calprotectin.


When compared using multi-omics features, colonic- and ileal-isolated CD subtypes display striking differences that suggest separate location-specific pathologies. Colonic CD's strong similarity to ulcerative colitis, including neutrophil and Bacteroides vulgatus involvement, is also evidence of a shared pathology for colonic-isolated IBD subtypes, while ileal CD maintains a unique, bile acid-driven profile. More broadly, this study demonstrates the power of multi-omics approaches for IBD biomarker discovery and elucidating the underlying biology. Video Abstract.

Structure, function and diversity of the healthy human microbiome.

Studies of the human microbiome have revealed that even healthy individuals differ remarkably in the microbes that occupy habitats such as the gut, skin and vagina. Much of this diversity remains unexplained, although diet, environment, host genetics and early microbial exposure have all been implicated. Accordingly, to characterize the ecology of human-associated microbial communities, the Human Microbiome Project has analysed the largest cohort and set of distinct, clinically relevant body habitats so far. We found the diversity and abundance of each habitat's signature microbes to vary widely even among healthy subjects, with strong niche specialization both within and among individuals. The project encountered an estimated 81-99% of the genera, enzyme families and community configurations occupied by the healthy Western microbiome. Metagenomic carriage of metabolic pathways was stable among individuals despite variation in community structure, and ethnic/racial background proved to be one of the strongest associations of both pathways and microbes with clinical metadata. These results thus delineate the range of structural and functional configurations normal in the microbial communities of a healthy population, enabling future characterization of the epidemiology, ecology and translational applications of the human microbiome.

533 more worksshow all