Chris Umans

FOCS Conference 2022 Conference Paper

Fast Multivariate Multipoint Evaluation Over All Finite Fields

• Vishwas Bhargava
• Sumanta Ghosh
• Zeyu Guo 0001
• Mrinal Kumar 0001
• Chris Umans

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field F that outputs the evaluations of an m-variate polynomial of degree less than d in each variable at N points in time $(d^{m}+N)^{1+o(1)}$ poly $(m, \ d, \ \log|\mathbb{F}|)$ for all $m\in \mathbb{N}$ and all sufficiently large $d\in \mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables m is at most $d^{o(1)}$ and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than $d^{o(1)}$. In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri-Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in d of bounded height.

FOCS Conference 2019 Conference Paper

Fast Generalized DFTs for all Finite Groups

• Chris Umans

For any finite group G, we give an arithmetic algorithm to compute generalized Discrete Fourier Transforms (DFTs) with respect to G, using O(|G| ω/2+ε ) operations, for any ε > 0. Here, ω is the exponent of matrix multiplication.

SODA Conference 2018 Conference Paper

A fast generalized DFT for finite groups of Lie type

• Chloe Ching-Yun Hsu
• Chris Umans

MFCS Conference 2017 Conference Paper

On Multidimensional and Monotone k-SUM

• Chloe Ching-Yun Hsu
• Chris Umans

The well-known k-SUM conjecture is that integer k-SUM requires time Omega(n^{\ceil{k/2}-o(1)}). Recent work has studied multidimensional k-SUM in F_p^d, where the best known algorithm takes time \tilde O(n^{\ceil{k/2}}). Bhattacharyya et al. [ICS 2011] proved a min(2^{\Omega(d)}, n^{\Omega(k)}) lower bound for k-SUM in F_p^d under the Exponential Time Hypothesis. We give a more refined lower bound under the standard k-SUM conjecture: for sufficiently large p, k-SUM in F_p^d requires time Omega(n^{k/2-o(1)}) if k is even, and Omega(n^{\ceil{k/2}-2k(log k)/(log p)-o(1)}) if k is odd. For a special case of the multidimensional problem, bounded monotone d-dimensional 3SUM, Chan and Lewenstein [STOC 2015] gave a surprising \tilde O(n^{2-2/(d+13)}) algorithm using additive combinatorics. We show this algorithm is essentially optimal. To be more precise, bounded monotone d-dimensional 3SUM requires time Omega(n^{2-\frac{4}{d}-o(1)}) under the standard 3SUM conjecture, and time Omega(n^{2-\frac{2}{d}-o(1)}) under the so-called strong 3SUM conjecture. Thus, even though one might hope to further exploit the structural advantage of monotonicity, no substantial improvements beyond those obtained by Chan and Lewenstein are possible for bounded monotone d-dimensional 3SUM.

STOC Conference 2017 Conference Paper

Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace

• William M. Hoza
• Chris Umans

MFCS Conference 2016 Conference Paper

Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields

• Zeyu Guo 0001
• Anand Kumar Narayanan
• Chris Umans

The fastest known algorithm for factoring univariate polynomials over finite fields is the Kedlaya-Umans (fast modular composition) implementation of the Kaltofen-Shoup algorithm. It is randomized and takes ~O(n^{3/2}*log(q)+n*log^2(q)) time to factor polynomials of degree n over the finite field F_q with q elements. A significant open problem is if the 3/2 exponent can be improved. We study a collection of algebraic problems and establish a web of reductions between them. A consequence is that an algorithm for any one of these problems with exponent better than 3/2 would yield an algorithm for polynomial factorization with exponent better than 3/2.

SODA Conference 2013 Conference Paper

Fast matrix multiplication using coherent configurations

• Henry Cohn
• Chris Umans

We introduce a relaxation of the notion of tensor rank, called s-rank, and show that upper bounds on the s -rank of the matrix multiplication tensor imply upper bounds on the ordinary rank. In particular, if the “ s -rank exponent of matrix multiplication” equals 2, then ω = 2. This connection between the s -rank exponent and the ordinary exponent enables us to significantly generalize the group-theoretic approach of Cohn and Umans, from group algebras to general algebras. Embedding matrix multiplication into general algebra multiplication yields bounds on s -rank (not ordinary rank) and, prior to this paper, that had been a barrier to working with general algebras. We identify adjacency algebras of coherent configurations as a promising family of algebras in the generalized framework. Coherent configurations are combinatorial objects that generalize groups and group actions; adjacency algebras are the analogue of group algebras and retain many of their important features. As with groups, coherent configurations support matrix multiplication when a natural combinatorial condition is satisfied, involving triangles of points in their underlying geometry. Finally, we prove a closure property involving symmetric powers of adjacency algebras, which enables us to prove nontrivial bounds on ω using commutative coherent configurations and suggests that commutative coherent configurations may be sufficient to prove ω = 2. Altogether, our results show that bounds on ω can be established by embedding large matrix multiplication instances into small commutative coherent configurations.

SODA Conference 2010 Conference Paper

Inapproximability for VCG-Based Combinatorial Auctions

• David Buchfuhrer
• Shaddin Dughmi
• Hu Fu 0001
• Robert Kleinberg
• Elchanan Mossel
• Christos H. Papadimitriou
• Michael Schapira
• Yaron Singer

FOCS Conference 2009 Conference Paper

The Complexity of Rationalizing Network Formation

• Shankar Kalyanaraman
• Chris Umans

We study the complexity of rationalizing network formation. In this problem we fix an underlying model describing how selfish parties (the vertices) produce a graph by making individual decisions to form or not form incident edges. The model is equipped with a notion of stability (or equilibrium), and we observe a set of "snapshots" of graphs that are assumed to be stable. From this we would like to infer some unobserved data about the system: edge prices, or how much each vertex values short paths to each other vertex. We study two rationalization problems arising from the network formation model of Jackson and Wolinsky [14]. When the goal is to infer edge prices, we observe that the rationalization problem is easy. The problem remains easy even when rationalizing prices do not exist and we instead wish to find prices that maximize the stability of the system. In contrast, when the edge prices are given and the goal is instead to infer valuations of each vertex by each other vertex, we prove that the rationalization problem becomes NP-hard. Our proof exposes a close connection between rationalization problems and the Inequality-SAT (I-SAT) problem. Finally and most significantly, we prove that an approximation version of this NP-complete rationalization problem is NP-hard to approximate to within better than a 1/2 ratio. This shows that the trivial algorithm of setting everyone's valuations to infinity (which rationalizes all the edges present in the input graphs) or to zero (which rationalizes all the non-edges present in the input graphs) is the best possible assuming P? NP To do this we prove a tight (1/2 +?) -approximation hardness for a variant of I-SAT in which all coefficients are non-negative. This in turn follows from a tight hardness result for MAX-LlN R + (linear equations over the reals, with non-negative coefficients), which we prove by a (non-trivial) modification of the recent result of Guruswami and Raghavendra [10] which achieved tight hardness for this problem without the non-negativity constraint. Our technical contributions regarding the hardness of I-SAT and MAX-LIN R + may be of independent interest, given the generality of these problems.

FOCS Conference 2008 Conference Paper

Fast Modular Composition in any Characteristic

• Kiran S. Kedlaya
• Chris Umans

We give an algorithm for modular composition of degree n univariate polynomials over a finite field F q requiring n 1 + o(1) log 1 + o(1) q bit operations; this had earlier been achieved in characteristic n o(1) by Umans (2008). As an application, we obtain a randomized algorithm for factoring degree n polynomials over F q requiring (n 1. 5 + o(1) + n 1 + o(1) log q) log 1 + o(1) q bit operations, improving upon the methods of von zur Gathen & Shoup (1992) and Kaltofen & Shoup (1998). Our results also imply algorithms for irreducibility testing and computing minimal polynomials whose running times are best-possible, up to lower order terms. As in Umans (2008), we reduce modular composition to certain instances of multipoint evaluation of multivariate polynomials. We then give an algorithm that solves this problem optimally (up to lower order terms), in arbitrary characteristic. The main idea is to lift to characteristic 0, apply a small number of rounds of multimodular reduction, and finish with a small number of multidimensional FFTs. The final evaluations are then reconstructed using the Chinese Remainder Theorem. As a bonus, we obtain a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithm uses techniques which are commonly employed in practice, so it may be competitive for real problem sizes. This contrasts with previous asymptotically fast methods relying on fast matrix multiplication.

STOC Conference 2008 Conference Paper

Fast polynomial factorization and modular composition in small characteristic

• Chris Umans

STOC Conference 2007 Conference Paper

Low-end uniform hardness vs. randomness tradeoffs for AM

• Ronen Shaltiel
• Chris Umans

FOCS Conference 2006 Conference Paper

Better lossless condensers through derandomized curve samplers

• Amnon Ta-Shma
• Chris Umans

Lossless condensers are unbalanced expander graphs, with expansion close to optimal. Equivalently, they may be viewed as functions that use a short random seed to map a source on n bits to a source on many fewer bits while preserving all of the min-entropy. It is known how to build lossless condensers when the graphs are slightly unbalanced in the work of M. Capalbo et al. (2002). The highly unbalanced case is also important but the only known construction does not condense the source well. We give explicit constructions of lossless condensers with condensing close to optimal, and using near-optimal seed length. Our main technical contribution is a randomness-efficient method for sampling F D (where F is a field) with low-degree curves. This problem was addressed before in the works of E. Ben-Sasson et al. (2003) and D. Moshkovitz and R. Raz (2006) but the solutions apply only to degree one curves, i. e. , lines. Our technique is new and elegant. We use sub-sampling and obtain our curve samplers by composing a sequence of low-degree manifolds, starting with high-dimension, low-degree manifolds and proceeding through lower and lower dimension manifolds with (moderately) growing degrees, until we finish with dimension-one, low-degree manifolds, i. e. , curves. The technique may be of independent interest

FOCS Conference 2005 Conference Paper

Group-theoretic Algorithms for Matrix Multiplication

• Henry Cohn
• Robert Kleinberg
• Balázs Szegedy
• Chris Umans

We further develop the group-theoretic approach to fast matrix multiplication introduced by Cohn and Umans, and for the first time use it to derive algorithms asymptotically faster than the standard algorithm. We describe several families of wreath product groups that achieve matrix multiplication exponent less than 3, the asymptotically fastest of which achieves exponent 2. 41. We present two conjectures regarding specific improvements, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.

FOCS Conference 2003 Conference Paper

A Group-Theoretic Approach to Fast Matrix Multiplication

• Henry Cohn
• Chris Umans

We develop a new, group-theoretic approach to bounding the exponent of matrix multiplication. There are two components to this approach: (1) identifying groups G that admit a certain type of embedding of matrix multiplication into the group algebra /spl Copf/[G], and (2) controlling the dimensions of the irreducible representations of such groups. We present machinery and examples to support (1), including a proof that certain families of groups of order n/sup 2+o(1)/ support n /spl times/ n matrix multiplication, a necessary condition for the approach to yield exponent 2. Although we cannot yet completely achieve both (1) and (2), we hope that it may be possible, and we suggest potential routes to that result using the constructions in this paper.

STOC Conference 2002 Conference Paper

Pseudo-random generators for all hardnesses

• Chris Umans

STOC Conference 2001 Conference Paper

Loss-less condensers, unbalanced expanders, and extractors

• Amnon Ta-Shma
• Chris Umans
• David Zuckerman

An extractor is a procedure which extracts randomness from a detective random source using a few additional random bits. Explicit extractor constructions have numerous applications and obtaining such constructions is an important derandomization goal. Trevisan recently introduced an elegant extractor construction, but the number of truly random bits required is suboptimal when the input source has low-min-entropy. Significant progress toward overcoming this bottleneck has been made, but so far has required complicated recursive techniques that lose the simplicity of Trevisan's construction. We give a clean method for overcoming this bottleneck by constructing {\em loss-less condensers}. which compress the n -bit input source without losing any min-entropy, using O(\log n) additional random bits. Our condensers are built using a simple modification of Trevisan's construction, and yield the best extractor constructions to date. Loss-less condensers also produce unbalanced bipartite expander graphs with small (polylogarithmic) degree D and very strong expansion of (1-\epilon)D . We give other applications of our construction, including dispersers with entropy loss O(\log n) , depth two super-concentrators whose size is within a polylog of optimal, and an improved hardness of approximation result.

FOCS Conference 2001 Conference Paper

Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator

• Ronen Shaltiel
• Chris Umans

We present a simple, self-contained extractor construction that produces good extractors for all min-entropies (min-entropy measures the amount of randomness contained in a weak random source). Our construction is algebraic and builds on a new polynomial-based approach introduced by A. Ta-Shma et al. (2001). Using our improvements, we obtain, for example, an extractor with output length m=k/sup 1-/spl delta// and seed length O(log n). This matches the parameters of L. Trevisan's (1999) breakthrough result and additionally achieves those parameters for small min-entropies k. Our construction gives a much simpler and more direct solution to this problem. Applying similar ideas to the problem of building pseudo-random generators, we obtain a new pseudo-random generator construction that is not based on the NW generator (N. Nisan and A. Widgerson, 1994), and turns worst-case hardness directly into pseudo-randomness. The parameters of this generator are strong enough to obtain a new proof that P=BPP if E requires exponential size circuits. Essentially, the same construction yields a hitting set generator with optimal seed length that outputs s/sup /spl Omega/(1)/ bits when given a function that requires circuits of size s (for any s). This implies a hardness versus randomness trade off for RP and BPP that is optimal (up to polynomial factors), solving an open problem raised by R. Impagliazzo et al. (1999). Our generators can also be used to derandomize AM.

FOCS Conference 1999 Conference Paper

Hardness of Approximating Sigma 2 p Minimization Problems

• Chris Umans

We show that a number of natural optimization problems in the second level of the Polynomial Hierarchy are /spl Sigma//sub 2//sup p/-hard to approximate to within n/sup /spl epsiv// factors, for specific /spl epsiv/>0. The main technical tool is the use of explicit dispersers to achieve strong, direct inapproximability results. The problems we consider include Succinct Set Cover, Minimum Equivalent DNF, and other problems relating to DNF minimization. Under a slightly stronger complexity assumption, our method gives optimal n/sup 1-/spl epsiv// inapproximability results for some of these problems. We also prove inapproximability of a variant of an NP optimization problem, Monotone Minimum Satisfying Assignment, to within an n/sup /spl epsiv// factor using the same technique.

FOCS Conference 1998 Conference Paper

The Minimum Equivalent DNF Problem and Shortest Implicants

• Chris Umans

We prove that the Minimum Equivalent DNF problem is /spl Sigma//sub 2//sup p/-complete, resolving a conjecture due to L. J. Stockmeyer (1976). The proof involves as an intermediate step a variant of a related problem in logic minimization, namely, that of finding the shortest implicant of a Boolean function. We also obtain certain results concerning the complexity of the shortest implicant problem that may be of independent interest. When the input is a formula, the shortest implicant problem is /spl Sigma//sub 2//sup p/-complete, and /spl Sigma//sub 2//sup p/-hard to approximate to within an n/sup 1/2-/spl epsiv// factor. When the input is a circuit, approximation is /spl Sigma//sub 2//sup p/-hard to within an n/sup 1-/spl epsiv// factor. However, when the input is a DNF formula, the shortest implicant problem cannot be /spl Sigma//sub 2//sup p/-complete unless /spl Sigma//sub 2//sup p/=NP[log/sup 2/n]/sup NP/.

FOCS Conference 1997 Conference Paper

Hamiltonian Cycles in Solid Grid Graphs

• Chris Umans
• William J. Lenhart

A grid graph is a finite node induced subgraph of the infinite two dimensional integer grid. A solid grid graph is a grid graph without holes. For general grid graphs, the Hamiltonian cycle problem is known to be NP complete. We give a polynomial time algorithm for the Hamiltonian cycle problem in solid grid graphs, resolving a longstanding open question posed by A. Itai et al. (1982). In fact, our algorithm can identify Hamiltonian cycles in quad quad graphs, a class of graphs that properly includes solid grid graphs.