The Cohn-Umans (FOCS '03) group-theoretic framework for matrix multiplication produces fast matrix multiplication algorithms from three subsets of a finite group G satisfying a simple combinatorial condition (the Triple Product Property). The complexity of such an algorithm then depends on the representation theory of G. In this paper we extend the group-theoretic framework to the setting of infinite groups. In particular, this allows us to obtain constructions in Lie groups, with favorable parameters, that are provably impossible in finite groups of Lie type (Blasiak, Cohn, Grochow, Pratt, and Umans, ITCS '23). Previously the Lie group setting was investigated purely as an analogue of the finite group case; a key contribution in this paper is a fully developed framework for obtaining bona fide matrix multiplication algorithms directly from Lie group constructions. As part of this framework, we introduce "separating functions" as a necessary new design component, and show that when the underlying group is G = GL_n, these functions are polynomials with their degree being the key parameter. In particular, we show that a construction with "half-dimensional" subgroups and optimal degree would imply ω = 2. We then build up machinery that reduces the problem of constructing optimal-degree separating polynomials to the problem of constructing a single polynomial (and a corresponding set of group elements) in a ring of invariant polynomials determined by two out of the three subgroups that satisfy the Triple Product Property. This machinery combines border rank with the Lie algebras associated with the Lie subgroups in a critical way. We give several constructions illustrating the main components of the new framework, culminating in a construction in a special unitary group that achieves separating polynomials of optimal degree, meeting one of the key challenges. The subgroups in this construction have dimension approaching half the ambient dimension, but (just barely) too slowly. We argue that features of the classical Lie groups make it unlikely that constructions in these particular groups could produce nontrivial bounds on ω unless they prove ω = 2. One way to get ω = 2 via our new framework would be to lift our existing construction from the special unitary group to GL_n, and improve the dimension of the subgroups from (dim G)/2 - Θ(n) to (dim G)/2 - o(n).

Abstract. For any finite group [Formula: see text], we give an algebraic algorithm to compute the generalized discrete Fourier transform with respect to [Formula: see text], using [Formula: see text] operations, for any [Formula: see text]. Here, [Formula: see text] is the exponent of matrix multiplication.

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 \(\mathbb {F}\) that outputs the evaluations of an m -variate polynomial of degree less than d in each variable at N points in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) . A previous work of Kedlaya and Umans (FOCS 2008 and 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 and 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 . More specifically, our second algorithm solves the multivariate multipoint evaluation problem over a finite field \(\mathbb {F}\) in time, \(\begin{equation*} (d^m+N)^{1+o(1)}\cdot {{\sf poly}}(m,d,\log |\mathbb {F}|), \end{equation*}\) for all \(m\in \mathbb {N}\) and all sufficiently large \(d\in \mathbb {N}\) , provided that the size of the finite field \(\mathbb {F}\) is at most \((\exp (\exp (\exp (\cdots (\exp (d)))))\) , where the height of this tower of exponentials is fixed.

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.

Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this assumption that ${BPL} \subseteq \bigcap_{\alpha > 0} {DSPACE}(\log^{1 + \alpha} n)$. We strengthen the theorem to an equivalence by considering two generalizations of the concept of a pseudorandom generator against logspace. A targeted pseudorandom generator against logspace takes as input a short uniform random seed and a finite automaton; it outputs a long bitstring that looks random to that particular automaton. A simulation advice generator for logspace stretches a small uniform random seed into a long advice string; the requirement is that there is some logspace algorithm that, given a finite automaton and this advice string, simulates the automaton reading a long uniform random input. We prove that $\bigcap_{\alpha > 0} {promise}-{BPSPACE}(\log^{1 + \alpha} n) = \bigcap_{\alpha > 0} {promise}-{DSPACE}(\log^{1 + \alpha} n)$ if and only if for every targeted pseudorandom generator against logspace, there is a simulation advice generator for logspace with similar parameters. Finally, we observe that in a certain uniform setting (namely, if we only worry about sequences of automata that can be generated in logspace), targeted pseudorandom generators against logspace can be transformed into simulation advice generators with similar parameters.

We give an new arithmetic algorithm to compute the generalized Discrete Fourier Transform (DFT) over finite groups G . The new algorithm uses O (∣ G ∣ ω /2 + o (1) ) operations to compute the generalized DFT over finite groups of Lie type, including the linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups of Lie type. Here ω is the exponent of matrix multiplication, so the exponent ω/2 is optimal if ω = 2. Previously, “exponent one” algorithms were known for supersolvable groups and the symmetric and alternating groups. No exponent one algorithms were known, even under the assumption ω = 2, for families of linear groups of fixed dimension, and indeed the previous best-known algorithm for SL 2 (F q ) had exponent 4/3 despite being the focus of significant effort. We unconditionally achieve exponent at most 1.19 for this group and exponent one if ω = 2. Our algorithm also yields an improved exponent for computing the generalized DFT over general finite groups G , which beats the longstanding previous best upper bound for any ω. In particular, assuming ω = 2, we achieve exponent √ 2, while the previous best was 3/2.

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.

We give an arithmetic algorithm using O(|G|ω/2+o(1)) operations to compute the generalized Discrete Fourier Transform (DFT) over group G for finite groups of Lie type, including the linear, orthogonal, and symplectic families and their variants, as well as all finite simple groups of Lie type. Here ω is the exponent of matrix multiplication, so the exponent ω/2 is optimal if ω = 2. Previously, “exponent one” algorithms were known for supersolvable groups and the symmetric and alternating groups. No exponent one algorithms were known (even under the assumption ω = 2) for families of linear groups of fixed dimension, and indeed the previous best-known algorithm for SL2(Fq) had exponent 4/3 despite being the focus of significant effort. We unconditionally achieve exponent at most 1.19 for this group, and exponent one if ω = 2. We also show that ω = 2 implies a exponent for general finite groups G, which beats the longstanding previous best upper bound (assuming ω = 2) of 3/2.

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.

Assume that for every derandomization result for logspace algorithms, there is a pseudorandom generator strong enough to nearly recover the derandomization by iterating over all seeds and taking a majority vote. We prove under a precise version of this assumption that BPL ⊆ ∩α > 0 DSPACE(log1 + α n).

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.

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.

We present several variants of the sunflower conjecture of Erdős & Rado (J Lond Math Soc 35:85–90, 1960) and discuss the relations among them. We then show that two of these conjectures (if true) imply negative answers to the questions of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990) and Cohn et al. (2005) regarding possible approaches for obtaining fast matrix-multiplication algorithms. Specifically, we show that the Erdős–Rado sunflower conjecture (if true) implies a negative answer to the “no three disjoint equivoluminous subsets” question of Coppersmith & Winograd (J Symb Comput 9:251–280, 1990); we also formulate a “multicolored” sunflower conjecture in $${\mathbb{Z}_3^n}$$ and show that (if true) it implies a negative answer to the “strong USP” conjecture of Cohn et al. (2005) (although it does not seem to impact a second conjecture in Cohn et al. (2005) or the viability of the general group-theoretic approach). A surprising consequence of our results is that the Coppersmith–Winograd conjecture actually implies the Cohn et al. conjecture. The multicolored sunflower conjecture in $${\mathbb{Z}_3^n}$$ is a strengthening of the well-known (ordinary) sunflower conjecture in $${\mathbb{Z}_3^n}$$ , and we show via our connection that a construction from Cohn et al. (2005) yields a lower bound of (2.51 . . .) n on the size of the largest multicolored 3-sunflower-free set, which beats the current best-known lower bound of (2.21 . . . ) n Edel (2004) on the size of the largest 3-sunflower-free set in $${\mathbb{Z}_3^n}$$ .

We give a new construction of condensers based on Parvaresh-Vardy codes [1]. Our condensers have entropy rate (1-α) for subconstant α (in contrast to [2] which required constant α) and suffer only sublinear entropy loss. Known extractors can be applied to the output to extract all but a subconstant fraction of the minentropy. The resulting (k, ε) extractor E : {0, 1}n× {0, 1}d→ {0, 1}mhas output length m = (1- α)k with α = 1/poly log(n), and seed length d = O(log n), when ε ≥ 1/2logβn for any constant ß <; 1. Thus we achieve the same “world-record” extractor parameters as [3], with a more direct construction.

The hybrid argument allows one to relate the distinguishability of a distribution (from uniform) to the predictability of individual bits given a prefix. The argument incurs a loss of a factor k equal to the bit-length of the distributions: ε-distinguishability implies ε/k-predictability. This paper studies the consequences of avoiding this loss - what we call "beating the hybrid argument" -- and develops new proof techniques that circumvent the loss in certain natural settings. Specifically, we obtain the following results:

This issue of SICOMP contains nine specially selected papers from the Forty-first Annual ACM Symposium on the Theory of Computing, otherwise known as STOC 2009, held May 31 to June 2 in Bethesda, Maryland. The papers here were chosen to represent both the excellence and the broad range of the STOC program. The papers have been revised and extended by the authors, and subjected to the standard thorough reviewing process of SICOMP. The program committee consisted of Susanne Albers, Andris Ambainis, Nikhil Bansal, Paul Beame, Andrej Bogdanov, Ran Canetti, David Eppstein, Dmitry Gavinsky, Shafi Goldwasser, Nicole Immorlica, Anna Karlin, Jonathan Katz, Jonathan Kelner, Subhash Khot, Ravi Kumar, Leslie Ann Goldberg, Michael Mitzenmacher (Chair), Kamesh Munagala, Rasmus Pagh, Anup Rao, Rocco Servedio, Mikkel Thorup, Chris Umans, and Lisa Zhang. They accepted 77 papers out of 321 submissions. We briefly describe the papers that appear here. In “Bit-Probe Lower Bounds for Succinct Data Structures” Emanuele Viola considers lower bounds for representing lists of values where one also wants to be able to probe the structure that maintains the values in order to for example determine the $i$th value in the list efficiently. In “Homology Flows, Cohomology Cuts” Jeff Erickson, Erin Chambers, and Amir Nayyeri provide an algorithm to compute maximum flows in surface-embedded graphs in near-linear time. In “Approximating Edit Distance in Near-Linear Time” Alexandr Andoni and Krzysztof Onak give the first sub-polynomial approximation of the edit distance that runs in near-linear time. In “Online and Stochastic Survivable Network Design” Anupam Gupta, Ravishankar Krishnaswamy, and R. Ravi examine approximation algorithms for finding a subgraph of minimum cost that maintain given connectivity constraints, in a number of online and stochastic settings. In “Universally Utility-Maximizing Privacy Mechanisms” Arpita Ghosh, Tim Roughgarden, and Mukund Sundararajan study differential privacy mechanisms, giving an approach that is simultaneously expected loss-minimizing in terms of utility for all users subject to a differential privacy constraint. In “3-Query Locally Decodable Codes of Subexponential Length” Klim Efremenko provides the first unconditional construction for 3-query locally decodable codes with subexponential codeword length. In “Twice-Ramanujan Sparsifiers” Joshua Batson, Daniel Spielman, and Nikhil Srivastava provide a deterministic, polynomial time algorithm for determining a spectral sparsifier of a graph---that is, a graph with a linear number of edges that approximates the graph in terms of its Laplacian matrix. In “New Direct-Product Testers and 2-Query PCPs” Russell Impagliazzo, Valentine Kabanets, and Avi Wigderson present several new results for probabilistically checkable proofs (PCPs), including new 3-query tests and 2-query tests leading to novel 2-query PCPs. In “Max Cut and the Smallest Eigenvalue” Luca Trevisan develops an elegant new approximation algorithm for Max Cut based on spectral partitioning methods, where the approximation ratio is 0.531 generally, but it also performs particularly well when the optimal solution cuts a large fraction of the edges. We thank the authors and the program committee for their hard work, and especially thank the reviewers for their work in evaluating and improving the submitted papers.

We obtain randomized algorithms for factoring degree n univariate polynomials over $\mathbb{F}_q$ requiring $O(n^{1.5 + o(1)}\,{\rm log}^{1+o(1)} q+ n^{1 + o(1)}\,{\rm log}^{2+o(1)} q)$ bit operations. When ${\rm log}\, q < n$, this is asymptotically faster than the best previous algorithms [J. von zur Gathen and V. Shoup, Comput. Complexity, 2 (1992), pp. 187–224; E. Kaltofen and V. Shoup, Math. Comp., 67 (1998), pp. 1179–1197]; for ${\rm log}\, q \ge n$, it matches the asymptotic running time of the best known algorithms. The improvements come from new algorithms for modular composition of degree n univariate polynomials, which is the asymptotic bottleneck in fast algorithms for factoring polynomials over finite fields. The best previous algorithms for modular composition use $O(n^{(\omega + 1)/2})$ field operations, where $\omega$ is the exponent of matrix multiplication [R. P. Brent and H. T. Kung, J. Assoc. Comput. Mach., 25 (1978), pp. 581–595], with a slight improvement in the exponent achieved by employing fast rectangular matrix multiplication [X. Huang and V. Y. Pan, J. Complexity, 14 (1998), pp. 257–299]. We show that modular composition and multipoint evaluation of multivariate polynomials are essentially equivalent, in the sense that an algorithm for one achieving exponent $\alpha$ implies an algorithm for the other with exponent $\alpha + o(1)$, and vice versa. We then give two new algorithms that solve the problem near-optimally: an algebraic algorithm for fields of characteristic at most $n^{o(1)}$, and a nonalgebraic algorithm that works in arbitrary characteristic. The latter algorithm works by lifting to characteristic 0, applying a small number of rounds of multimodular reduction, and finishing with a small number of multidimensional FFTs. The final evaluations are reconstructed using the Chinese remainder theorem. As a bonus, this algorithm produces a very efficient data structure supporting polynomial evaluation queries, which is of independent interest. Our algorithms use techniques that are commonly employed in practice, in contrast to all previous subquadratic algorithms for these problems, which relied on fast matrix multiplication.

The existence of incentive-compatible, computationally-efficient mechanisms for combinatorial auctions with good approximation ratios is the paradigmatic problem in algorithmic mechanism design. It is believed that, in many cases, good approximations for combinatorial auctions may be unattainable due to an inherent clash between truthfulness and computational efficiency. In this paper, we prove the first computational-complexity inapproximability results for incentive-compatible mechanisms for combinatorial auctions. Our results are tight, hold for the important class of VCG-based mechanisms, and are based on the complexity assumption that NP has no polynomial-size circuits. We show two different techniques to obtain such lower bounds: one for deterministic mechanisms that attains optimal dependence on the number of players and number of items, and one that also applies to a class of randomized mechanisms and attains optimal dependence on the number of players. Both techniques are based on novel VC dimension machinery.

This special section comprises eight fully refereed papers whose extended abstracts were presented at the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2007) in Providence, Rhode Island, October 21–23, 2007. The unrefereed conference versions of these papers were published by IEEE in the FOCS 2007 proceedings. The regular conference program consisted of 63 papers chosen from among 302 submissions. These were selected by a program committee consisting of Dimitris Achlioptas, Timothy Chan, Julia Chuzhoy, Faith Ellen, Piotr Indyk, Kamal Jain, T. S. Jayram, Robert Kleinberg, James R. Lee, Anna Lysyanskaya, Daniele Micciancio, Gary Miller, Moni Naor, Alexander Razborov, Yaoyun Shi, Alistair Sinclair (chair), Luca Trevisan, Chris Umans, and Uri Zwick. The papers invited to this special section were also selected with the input of the program committee. The eight papers in this section span a broad range of topics, including algorithmic game theory, communication complexity, hardness of approximation, metric embeddings, proof complexity, pseudorandomness, and quantum algorithms. Each paper underwent an extensive refereeing process; we thank both the authors and the anonymous referees for their efforts. In addition, we would like to thank Eva Tardos, who was SICOMP's editor-in-chief during the course of this project, and SIAM staff members Mitch Chernoff and Cherie Trebisky for their help in preparing this special section.

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-LlNR+(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-LINR+may be of independent interest, given the generality of these problems.

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma et al. [2007] required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy [2005]. Our expanders can be interpreted as near-optimal “randomness condensers,” that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new, self-contained construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. [2003] and improving upon it when the error parameter is small (e.g., 1/poly(n)).

Impagliazzo and Wigderson [Proceedings of the 39th Annual IEEE Symposium on Foundations of Computer Science, IEEE Computer Society, Washington, DC, 1998, pp. 734–743] proved a hardness versus randomness tradeoff for BPP in the uniform setting, which was subsequently extended to give optimal tradeoffs for the full range of possible hardness assumptions (in slightly weaker settings). Gutfreund, Shaltiel, and Ta-Shma [Comput. Complexity, 12 (2003), pp. 85–130] proved a uniform hardness versus randomness tradeoff for AM, but that result worked only on the “high end” of possible hardness assumptions. In this work, we give uniform hardness versus randomness tradeoffs for AM that are near-optimal for the full range of possible hardness assumptions. Following Gutfreund, Shaltiel, and Ta-Shma, we do this by constructing a hitting-set-generator (HSG) for AM with “resilient reconstruction.” Our construction is a recursive variant of the Miltersen–Vinodchandran HSG [Comput. Complexity, 14 (2005), pp. 256–279], the only known HSG construction with this required property. The main new idea is to have the reconstruction procedure operate implicitly and locally on superpolynomially large objects, using tools from PCPs (low-degree testing, self-correction) together with a novel use of extractors that are built from Reed–Muller codes for a sort of locally computable error-reduction. As a consequence we obtain gap theorems for AM (and AM $\cap$ coAM) that state, roughly, that either AM (or AM $\cap$ coAM) protocols running in time $t(n)$ can simulate all of EXP (“Arthur–Merlin games are powerful”) or else all of AM (or AM $\cap$ coAM) can be simulated in nondeterministic time $s(n)$ (“Arthur–Merlin games can be derandomized”) for a near-optimal relationship between $t(n)$ and $s(n)$. As in Gutfreund, Shatiel, and Ta-Shma, the case of AM $\cap$ coAM yields a particularly clean theorem that is of special interest due to the wide array of cryptographic and other problems that lie in this class.

We give an algorithm for modular composition of degree n univariate polynomials over a finite field Fqrequiring n1+o(1)log1+o(1)q bit operations; this had earlier been achieved in characteristic no(1)by Umans (2008). As an application, we obtain a randomized algorithm for factoring degree n polynomials over Fqrequiring (n1.5+o(1)+ n1+o(1)log q) log1+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.

We obtain randomized algorithms for factoring degree n univariate polynomials over F_q that use O(n1.5 + o(1) + n1 + o(1)log q) field operations, when the characteristic is at most no(1). When log q < n, this is asymptotically faster than the best previous algorithms (von zur Gathen & Shoup (1992) and Kaltofen & Shoup (1998)); for log q ≥ n, it matches the asymptotic running time of the best known algorithms.

We study the complexity of solving succinct zero-sum games, i.e., the games whose payoff matrix M is given implicitly by a Boolean circuit C such that M(i,j) = C(i,j). We complement the known EXP-hardness of computing the exact value of a succinct zero-sum game by several results on approximating the value. (1) We prove that approximating the value of a succinct zero-sum game to within an additive error is complete for the class promise- $$S^{p}_{2}$$ , the “promise” version of $$S^{p}_{2}$$ . To the best of our knowledge, it is the first natural problem shown complete for this class. (2) We describe a ZPP NP algorithm for constructing approximately optimal strategies, and hence for approximating the value, of a given succinct zero-sum game. As a corollary, we obtain, in a uniform fashion, several complexity-theoretic results, e.g., a ZPP NP algorithm for learning circuits for SAT (Bshouty et al., JCSS, 1996) and a recent result by Cai (JCSS, 2007) that $$S^{p}_{2} \subseteq$$ ZPP NP . (3) We observe that approximating the value of a succinct zero-sum game to within a multiplicative factor is in PSPACE, and that it cannot be in promise- $$S^{p}_{2}$$ unless the polynomial-time hierarchy collapses. Thus, under a reasonable complexity-theoretic assumption, multiplicative-factor approximation of succinct zero-sum games is strictly harder than additive-error approximation.

We give an improved explicit construction of highly unbalanced bipartite expander graphs with expansion arbitrarily close to the degree (which is polylogarithmic in the number of vertices). Both the degree and the number of right-hand vertices are polynomially close to optimal, whereas the previous constructions of Ta-Shma, Umans, and Zuckerman (STOC "01) required at least one of these to be quasipolynomial in the optimal. Our expanders have a short and self-contained description and analysis, based on the ideas underlying the recent list-decodable error-correcting codes of Parvaresh and Vardy (FOCS "05). Our expanders can be interpreted as near-optimal "randomness condensers," that reduce the task of extracting randomness from sources of arbitrary min-entropy rate to extracting randomness from sources of min-entropy rate arbitrarily close to 1, which is a much easier task. Using this connection, we obtain a new construction of randomness extractors that is optimal up to constant factors, while being much simpler than the previous construction of Lu et al. (STOC "03) and improving upon it when the error parameter is small (e.g. 1/poly(n)).

In 1998, Impagliazzo and Wigderson [18] proved a hardnessvs. randomness tradeoff for BPP in the uniform setting,which was subsequently extended to give optimal tradeoffs for thefull range of possible hardness assumptions by Trevisan and Vadhan [29] (in a slightly weaker setting). In 2003, Gutfreund,Shaltiel and Ta-Shma [11] proved a uniform hardness vs. randomness tradeoff for AM, but that result only worked on the "high-end" of possible hardness assumptions.

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 FD(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

The exponent of matrix multiplication is the smallest real number ω such that for all ε>0, O(nω+ε) arithmetic operations suffice to multiply two n×n matrices. The standard algorithm for matrix multiplication shows that ω≤3. Strassen's remarkable result [5] shows that ω≤2.81, and a sequence of further works culminating in the work of Coppersmith and Winograd [4] have improved this upper bound to ω≤2.376 (see [1] for a full history). Most researchers believe that in fact ω=2, but there have been no further improvements in the known upper bounds for the past fifteen years.It is known that several central linear algebra problems (for example, computing determinants, solving systems of equations, inverting matrices, computing LUP decompositions) have the same exponent as matrix multiplication, which makes ω a fundamental number for understanding algorithmic linear algebra. In addition, there are non-algebraic algorithms whose complexity is expressed in terms of ω.In this talk I will describe a new "group-theoretic" approach, proposed in [3], to devising algorithms for fast matrix multiplication. The basic idea is to reduce matrix multiplication to group algebra multiplication with respect to a suitable non-abelian group. The group algebra multiplication is performed in the Fourier domain, and then using this scheme recursively yields upper bounds on ω.This general framework produces nontrivial matrix multiplication algorithms if one can construct finite groups with certain properties. In particular, a very natural embedding of matrix multiplication into C[G]-multiplication is possible when group G has three subgroups H1, H2, H3 that satisfy the triple product property. I'll define this property and describe a construction that satisfies the triple product property with parameters that are necessary (but not yet sufficient) to achieve ω=2.In the next part of the talk I'll describe demands on the representation theory of the groups in order for the overall approach to yield non-trivial bounds on ω, namely, that the character degrees must be "small." Constructing families of groups together with subgroups satisfying the triple product property and for which the character degrees are sufficiently small has turned out to be quite challenging.In [2], we succeed in constructing groups meeting both requirements, resulting in non-trivial algorithms for matrix multiplication in this framework. I'll outline the basic construction, together with more sophisticated variants that achieve the bounds ω<2.48 and ω<2.41.In the final part of the talk I'll present two appealing conjectures, one combinatorial and the other algebraic. Either one would imply that the exponent of matrix multiplication is 2.

We study computational procedures that use both randomness and nondeterminism. Examples are Arthur-Merlin games and approximate counting and sampling of NP-witnesses. The goal of this paper is to derandomize such procedures under the weakest possible assumptions. Our main technical contribution allows one to "boost" a given hardness assumption. One special case is a proof that EXP /spl nsube/ NP/poly /spl rArr/ EXP /spl nsube/ P/sub /spl par///sup NP//poly. In words, if there is a problem in EXP that cannot be computed by poly-size nondeterministic circuits then there is one which cannot be computed by poly-size circuits that make non-adaptive NP oracle queries. This in particular shows that the various assumptions used over the last few years by several authors to derandomize Arthur-Merlin games (i.e., show AM = NP) are in fact all equivalent. In addition to simplifying the framework of AM derandomization, we show that this "unified assumption" suffices to de-randomize several other probabilistic procedures. For these results we define two new primitives that we regard as the natural pseudorandom objects associated with approximate counting and sampling of NP-witnesses. We use the "boosting" theorem and hashing techniques to construct these primitives using an assumption that is no stronger than that used to derandomize AM. As a consequence, under this assumption, there are deterministic polynomial time algorithms that use non-adaptive NP-queries and perform the following tasks: 1) approximate counting of NP-witnesses: given a Boolean circuit A, output r such that (1 - /spl epsi/)|A/sup -1/(1)| /spl les/ r les; |A/sup -1/(1)|. 2) pseudorandom sampling of NP-witnesses: given a Boolean circuit A, produce a polynomial-size sample space that is computationally indistinguishable from the uniform distribution over A/sup -1/(1). We also present applications. For example, we observe that Cai's proof that S/sub 2//sup p/ /spl sube/ ZPP/sup NP/ and the learning algorithm of Bshouty et al. can be seen as reductions to sampling that are not probabilistic. As a consequence they can be derandomized under the assumption stated above, which is weaker than the assumption that was previously known to suffice.

The complexity of two-level logic minimization is a topic of interest to both computer-aided design (CAD) specialists and computer science theoreticians. In the logic synthesis community, two-level logic minimization forms the foundation for more complex optimization procedures that have significant real-world impact. At the same time, the computational complexity of two-level logic minimization has posed challenges since the beginning of the field in the 1960s; indeed, some central questions have been resolved only within the last few years, and others remain open. This recent activity has classified some logic optimization problems of high practical relevance, such as finding the minimal sum-of-products (SOP) form and maximal term expansion and reduction. This paper surveys progress in the field with self-contained expositions of fundamental early results, an account of the recent advances, and some new classifications. It includes an introduction to the relevant concepts and terminology from computational complexity, as well a discussion of the major remaining open problems in the complexity of logic minimization

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.

A “randomness extractor” is an algorithm that given a sample from a distribution with sufficiently high min-entropy and a short random seed produces an output that is statistically indistinguishable from uniform. (Min-entropy is a measure of the amount of randomness in a distribution.) We present a simple, self-contained extractor construction that produces good extractors for all min-entropies. Our construction is algebraic and builds on a new polynomial-based approach introduced by Ta-Shma et al. [2001b]. Using our improvements, we obtain, for example, an extractor with output length m = k /(log n ) O (1/α) and seed length (1 + α)log n for an arbitrary 0 < α ≤ 1, where n is the input length, and k is the min-entropy of the input distribution.A “pseudorandom generator” is an algorithm that given a short random seed produces a long output that is computationally indistinguishable from uniform. Our technique also gives a new way to construct pseudorandom generators from functions that require large circuits. Our pseudorandom generator construction is not based on the Nisan-Wigderson generator [Nisan and Wigderson 1994], and turns worst-case hardness directly into pseudorandomness. The parameters of our generator match those in Impagliazzo and Wigderson [1997] and Sudan et al. [2001] and in particular are strong enough to obtain a new proof that P = BPP if E requires exponential size circuits.Our construction also gives the following improvements over previous work:---We construct an optimal “hitting set generator” that stretches O (log n ) random bits into s Ω(1) pseudorandom bits when given a function on log n bits that requires circuits of size s . This yields a quantitatively optimal hardness versus randomness tradeoff for both RP and BPP and solves an open problem raised in Impagliazzo et al. [1999].---We give the first construction of pseudorandom generators that fool nondeterministic circuits when given a function that requires large nondeterministic circuits. This technique also give a quantitatively optimal hardness versus randomness tradeoff for AM and the first hardness amplification result for nondeterministic circuits.

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.

(MATH) We construct the first pseudo-random generators with logarithmic seed length that convert s bits of hardness into sΩ(1) bits of 2-sided pseudo-randomness for any s}. This improves [8] and gives a direct proof of the optimal hardness vs. randomness tradeoff in [15]. A key element in our construction is an augmentation of the standard low-degree extension encoding that exploits the field structure of the underlying space in a new way.

We study the complexity of approximating the VC dimension of a collection of sets, when the sets are encoded succinctly by a small circuit. We show that this problem is: /spl Sigma//sub 3//sup p/-hard to approximate to within a factor 2-/spl epsiv/ for any /spl epsiv/>0; approximable in A/spl Mscr/ to within a factor 2; and A/spl Mscr/-hard to approximate to within a factor N/sup /spl epsiv// for some constant /spl epsiv/>0. To obtain the /spl Sigma//sub 3//sup 9/-hardness results we solve a randomness extraction problem using list-decodable binary codes; for the positive results we utilize the Sauer-Shelah(-Perles) Lemma. The exact value of /spl epsiv/ in the A/spl Mscr/-hardness result depends on the degree achievable by explicit disperser constructions.

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.

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 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.

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/.

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.