The advent of large language models (LLMs) and their adoption by the legal community has given rise to the question: what types of legal reasoning can LLMs perform? To enable greater study of this question, we present LegalBench: a collaboratively constructed legal reasoning benchmark consisting of 162 tasks covering six different types of legal reasoning. LegalBench was built through an interdisciplinary process, in which we collected tasks designed and hand-crafted by legal professionals. Because these subject matter experts took a leading role in construction, tasks either measure legal reasoning capabilities that are practically useful, or measure reasoning skills that lawyers find interesting. To enable cross-disciplinary conversations about LLMs in the law, we additionally show how popular legal frameworks for describing legal reasoning—which distinguish between its many forms—correspond to LegalBench tasks, thus giving lawyers and LLM developers a common vocabulary. This paper describes LegalBench, presents an empirical evaluation of 20 open-source and commercial LLMs, and illustrates the types of research explorations LegalBench enables.

We explore how ideas from infectious disease and genetics can be used to uncover patterns of cultural inheritance and innovation in a corpus of 591 national constitutions spanning 1789–2008. Legal “ideas” are encoded as “topics”—words statistically linked in documents—derived from topic modeling the corpus of constitutions. Using these topics we derive a diffusion network for borrowing from ancestral constitutions back to the US Constitution of 1789 and reveal that constitutions are complex cultural recombinants. We find systematic variation in patterns of borrowing from ancestral texts and “biological”‐like behavior in patterns of inheritance, with the distribution of “offspring” arising through a bounded preferential‐attachment process. This process leads to a small number of highly innovative (influential) constitutions some of which have yet to have been identified as so in the current literature. Our findings thus shed new light on the critical nodes of the constitution‐making network. The constitutional network structure reflects periods of intense constitution creation, and systematic patterns of variation in constitutional lifespan and temporal influence.

We present a general construction for dependent random measures based on thinning Poisson processes on an augmented space. The framework is not restricted to dependent versions of a specific nonparametric model, but can be applied to all models that can be represented using completely random measures. Several existing dependent random measures can be seen as specific cases of this framework. Interesting properties of the resulting measures are derived and the efficacy of the framework is demonstrated by constructing a covariate-dependent latent feature model and topic model that obtain superior predictive performance.

Many standard computer vision datasets exhibit biases due to a variety of sources including illumination condition, imaging system, and preference of dataset collectors. Biases like these can have downstream effects in the use of vision datasets in the construction of generalizable techniques, especially for the goal of the creation of a classification system capable of generalizing to unseen and novel datasets. In this work we propose Unbiased Metric Learning (UML), a metric learning approach, to achieve this goal. UML operates in the following two steps: (1) By varying hyper parameters, it learns a set of less biased candidate distance metrics on training examples from multiple biased datasets. The key idea is to learn a neighborhood for each example, which consists of not only examples of the same category from the same dataset, but those from other datasets. The learning framework is based on structural SVM. (2) We do model validation on a set of weakly-labeled web images retrieved by issuing class labels as keywords to search engine. The metric with best validation performance is selected. Although the web images sometimes have noisy labels, they often tend to be less biased, which makes them suitable for the validation set in our task. Cross-dataset image classification experiments are carried out. Results show significant performance improvement on four well-known computer vision datasets.

Multiscale representations of images have become a standard tool in image analysis. Such representations offer a number of advantages over fixed-scale methods, including the potential for improved performance in denoising, compression, and the ability to represent distinct but complementary information that exists at various scales. A variety of multiresolution transforms exist, including both orthogonal decompositions such as wavelets as well as nonorthogonal, overcomplete representations. Recently, techniques for finding adaptive, sparse representations have yielded state-of-the-art results when applied to traditional image processing problems. Attempts at developing multiscale versions of these so-called dictionary learning models have yielded modest but encouraging results. However, none of these techniques has sought to combine a rigorous statistical formulation of the multiscale dictionary learning problem and the ability to share atoms across scales. We present a model for multiscale dictionary learning that overcomes some of the drawbacks of previous approaches by first decomposing an input into a pyramid of distinct frequency bands using a recursive filtering scheme, after which we perform dictionary learning and sparse coding on the individual levels of the resulting pyramid. The associated image model allows us to use a single set of adapted dictionary atoms that is shared--and learned--across all scales in the model. The underlying statistical model of our proposed method is fully Bayesian and allows for efficient inference of parameters, including the level of additive noise for denoising applications. We apply the proposed model to several common image processing problems including non-Gaussian and nonstationary denoising of real-world color images.

In this paper, we show how the tools of empirical mode decomposition (EMD) analysis can be applied to the problem of “visual stylometry,” generally defined as the development of quantitative tools for the measurement and comparisons of individual style in the visual arts. In particular, we introduce a new form of EMD analysis for images and show that it is possible to use its output as the basis for the construction of effective support vector machine (SVM)-based stylometric classifiers. We present the methodology and then test it on collections of two sets of digital captures of drawings: a set of authentic and well-known imitations of works attributed to the great Flemish artist Pieter Bruegel the Elder (1525-1569) and a set of works attributed to Dutch master Rembrandt van Rijn (1606-1669) and his pupils. Our positive results indicate that EMD-based methods may hold promise generally as a technique for visual stylometry.

BACKGROUND: Multi-gene interactions likely play an important role in the development of complex phenotypes, and relationships between interacting genes pose a challenging statistical problem in microarray analysis, since the genes involved in these interactions may not exhibit marginal differential expression. As a result, it is necessary to develop tools that can identify sets of interacting genes that discriminate phenotypes without requiring that the classification boundary between phenotypes be convex. RESULTS: We describe an extension and application of a new unsupervised statistical learning technique, known as the Partition Decoupling Method (PDM), to gene expression microarray data. This method may be used to classify samples based on multi-gene expression patterns and to identify pathways associated with phenotype, without relying upon the differential expression of individual genes. The PDM uses iterated spectral clustering and scrubbing steps, revealing at each iteration progressively finer structure in the geometry of the data. Because spectral clustering has the ability to discern clusters that are not linearly separable, it is able to articulate relationships between samples that would be missed by distance- and tree-based classifiers. After projecting the data onto the cluster centroids and computing the residuals ("scrubbing"), one can repeat the spectral clustering, revealing clusters that were not discernible in the first layer. These iterations, each of which provide a partition of the data that is decoupled from the others, are carried forward until the structure in the residuals is indistinguishable from noise, preventing over-fitting. We describe the PDM in detail and apply it to three publicly available cancer gene expression data sets. By applying the PDM on a pathway-by-pathway basis and identifying those pathways that permit unsupervised clustering of samples that match known sample characteristics, we show how the PDM may be used to find sets of mechanistically-related genes that may play a role in disease. An R package to carry out the PDM is available for download. CONCLUSIONS: We show that the PDM is a useful tool for the analysis of gene expression data from complex diseases, where phenotypes are not linearly separable and multi-gene effects are likely to play a role. Our results demonstrate that the PDM is able to distinguish cell types and treatments with higher accuracy than is obtained through other approaches, and that the Pathway-PDM application is a valuable technique for identifying disease-associated pathways.

In this paper, we propose an approach for the accurate rotation of a digital image using Hermite expansions. This exploits the fact that if a 2-D continuous bandlimited Hermite expansion is rotated, the resulting function can be expressed as a Hermite expansion with the same bandlimit. Furthermore, the Hermite coefficients of the initial 2-D expansion and the rotated expansion are mapped through an invertible linear relationship. Two efficient methods to compute the mapping between Hermite coefficients during rotation are proposed. We also propose a method for connecting the Hermite expansion and a discrete image. Using this method, we can obtain the Hermite expansion from a discrete image and vice versa. Combining these techniques, we propose new methods for the rotation of discrete images. We assess the accuracy of our methods and compare them with an existing FFT-based method implementing three shears. We find that the method proposed here consistently has better accuracy than the FFT-based method.

Many quantum algorithms, including Shor's celebrated factoring and discrete log algorithms, proceed by reduction to a hidden subgroup problem, in which an unknown subgroup H of a group G must be determined from a quantum state $\psi$ over G that is uniformly supported on a left coset of H. These hidden subgroup problems are typically solved by Fourier sampling: the quantum Fourier transform of $\psi$ is computed and measured. When the underlying group is nonabelian, two important variants of the Fourier sampling paradigm have been identified: the weak standard method, where only representation names are measured, and the strong standard method, where full measurement (i.e., the row and column of the representation, in a suitably chosen basis, as well as its name) occurs. It has remained open whether the strong standard method is indeed stronger, that is, whether there are hidden subgroups that can be reconstructed via the strong method but not by the weak, or any other known, method. In this article, we settle this question in the affirmative. We show that hidden subgroups H of the q-hedral groups, i.e., semidirect products ${\mathbb Z}_q \ltimes {\mathbb Z}_p$, where $q \mid (p-1)$, and in particular the affine groups $A_p$, can be information-theoretically reconstructed using the strong standard method. Moreover, if $|H| = p/ {\rm polylog}(p)$, these subgroups can be fully reconstructed with a polynomial amount of quantum and classical computation. We compare our algorithms to two weaker methods that have been discussed in the literature—the “forgetful” abelian method, and measurement in a random basis—and show that both of these are weaker than the strong standard method. Thus, at least for some families of groups, it is crucial to use the full power of representation theory and nonabelian Fourier analysis, namely, to measure the high-dimensional representations in an adapted basis that respects the group's subgroup structure. We apply our algorithm for the hidden subgroup problem to new families of cryptographically motivated hidden shift problems, generalizing the work of van Dam, Hallgren, and Ip on shifts of multiplicative characters. Finally, we close by proving a simple closure property for the class of groups over which the hidden subgroup problem can be solved efficiently.

We look at the problem of extracting geometric functions such as spatial transformations and curves delineating edges to subpixel accuracy from noisy, sampled data. We analyze the stochastic properties of continuous B-spline interpolation to show that, in general noisy circumstances, sub-pixel accuracy is not obtainable when using low degree B-splines. Results using magnetic resonance image (MRI) data are shown

The quantum Fourier transform (QFT) is a principal ingredient appearing in many efficient quantum algorithms. We present a generic framework for the construction of efficient quantum circuits for the QFT by “quantizing” the highly successful separation of variables technique for the construction of efficient classical Fourier transforms. Specifically, we apply Bratteli diagrams, Gel'fand-Tsetlin bases, and strong generating sets of small adapted diameter to provide efficient quantum circuits for the QFT over a wide variety of finite Abelian and non-Abelian groups, including all families of groups for which efficient QFTs are currently known and many new families as well. Moreover, our method provides the first subexponential-size quantum circuits for the QFT over the linear groups GL k ( q ), SL k ( q ), and the finite groups of Lie type, for any fixed prime power q .

The theory of spectral analysis of a particular class of noncommutative groups-wreath products of cyclic groups-has been shown to have a group-based convolution that leads to a new class of noncommutative filters. These filters, with their group and scale-selective properties and their relationship to DFT filter banks, offer some intriguing possibilities in signal processing applications. We give a summary of some of the basic properties of convolution with wreath product cyclic groups and illustrate those properties through an example. Applications to some basic signal processing tasks are proposed.

We present a direct generalization of local trigonometric bases to decompositions of L/sup 2/(R/sup 2/) with non-rectangular support. We describe decompositions of L/sup 2/(R/sup 2/) into n subspaces supported on approximate equiangular sectors and work out the case for n=3 in detail. For prototypical decompositions, windowed circular harmonics serve as basis functions. The technique applies equally well to decompositions of higher dimensional space.

This paper introduces methods based on generalized Fourier analysis for working with a class of errorcorrecting codes constructed in terms of Cayley graphs. Our work is motivated by the recent results of Sipser and Spielman [15] showing graph expansion to be essential for efficient decoding of certain low-density parity-check codes. They leave open the problem of sub-quadratic encoding for this class of codes, and it is this problem that we address. We show that when the codes are constructed in terms of Cayley graphs, the symmetry of the graphs can be exploited by using the representation theory of the underlying group to devise a sub-quadratic encoding algorithm that, in the case where the group is PSL 2 (Z=qZ), requires O(n 4=3 ) operations, where n = O(q 3 ) is the block length. Our results indicate that this new class of codes may combine many of the strengths of two of the most powerful and successful, but previously disparate areas of coding theory: the class of cyclic codes...

Let $\poly = \{P_0,\dots,P_{n-1}\}$ denote a set of polynomials with complex coefficients. Let $\pts = \{z_0,\dots,z_{n-1}\}\subset \cplx$ denote any set of {\it sample points}. For any $f = (f_0,\dots,f_{n-1}) \in \cplx^n$, the {\it discrete polynomial transform} of f (with respect to $\poly$ and $\pts$) is defined as the collection of sums, $\{\fhat(P_0),\dots,\fhat(P_{n-1})\}$, where $\fhat(P_j) = \langle f,P_j \rangle = \sum_{i=0}^{n-1} f_iP_j(z_i)w(i)$ for some associated weight function w. These sorts of transforms find important applications in areas such as medical imaging and signal processing. In this paper, we present fast algorithms for computing discrete orthogonal polynomial transforms. For a system of N orthogonal polynomials of degree at most $N-1$, we give an $O(N\log^2 N)$ algorithm for computing a discrete polynomial transform at an arbitrary set of points instead of the $N^2$ operations required by direct evaluation. Our algorithm depends only on the fact that orthogonal polynomial sets satisfy a three-term recurrence and thus it may be applied to any such set of discretely sampled functions. In particular, sampled orthogonal polynomials generate the vector space of functions on a distance transitive graph. As a direct application of our work, we are able to give a fast algorithm for computing subspace decompositions of this vector space which respect the action of the symmetry group of such a graph. This has direct applications to treating computational bottlenecks in the spectral analysis of data on distance transitive graphs, and we discuss this in some detail.

We present a wreath product approach for matched filtering to detect rotated copies of a template in an image. We view the image as a homogeneous space for a wreath product, a noncommutative symmetry group. The corresponding Fourier analysis has a natural multiresolution structure and accompanying efficient algorithm which we explain and illustrate with an example. The associated matched filter is a new example of the use of a noncommutative convolution for image processing. Numerical experiments are described in which this noncommutative approach outperforms standard Fourier-based methods.

A fast algorithm for the computation of spherical harmonic expansions of bandlimited functions on the 2-sphere is described. The algorithm also provides for an efficient inverse transform (synthesis) as well and consequently fast convolution on the 2-sphere is also possible. We discuss applications to image processing and medical imaging as well as aspects of our working implementation.

Let G be a finite group and let f' be a complex-valued function on G.If p is a matrix represen~ation of G (of dimension LIP)then the Fourier trarzsfiirnz o~~at p k defined to be the matrix .f(p) = X, c ~f(s)p(s).Let % be a complete set of inequivalent irreducible matrix representations of G.The Foaner trarzsfomr of f (with respect to %') is defined as the set of matrices {jl p)},, ~~.Recove~of ~from its Fourier transform may be accomplished via the Fourier inlerscon formula, f(s) = ~~dPtrace(f( P) P(S)-').pe9Given the Fourier transform of f, direct computation of ~by Fourier inversion requires on the order of IGI2 operations.In this paper, using the techniques of induced representations, general results for more efficient computation of Fourier inversion are given.In combination with earlier results for fast computation of the Fourier transform [Diaconis and Rockmore, 1990] fast algorithms for computing group convolutions (or equivalently, multiplication in the group algebra) also are obtained.In a particular case of interest, when G is the symmetric group Sn, the methods are readily applied and careful analysis reduces (n! )2 to (n( n !)) a"z where a k the exponent of

Let G be a group of matrices with entries over an alge-