# Christopher Umans

According to our database

Collaborative distances:

^{1}, Christopher Umans authored at least 58 papers between 1997 and 2018.Collaborative distances:

## Timeline

#### Legend:

Book In proceedings Article PhD thesis Other## Links

#### Homepages:

#### On csauthors.net:

## Bibliography

2018

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391).

Dagstuhl Reports, 2018

A fast generalized DFT for finite groups of Lie type.

Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, 2018

2017

Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace.

Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, 2017

On Multidimensional and Monotone k-SUM.

Proceedings of the 42nd International Symposium on Mathematical Foundations of Computer Science, 2017

2016

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).

Dagstuhl Reports, 2016

On the Power of Quantum Fourier Sampling.

Proceedings of the 11th Conference on the Theory of Quantum Computation, 2016

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

Proceedings of the 41st International Symposium on Mathematical Foundations of Computer Science, 2016

2014

Algebra in Computational Complexity (Dagstuhl Seminar 14391).

Dagstuhl Reports, 2014

Special Issue "Conference on Computational Complexity 2013" Guest editor's foreword.

Computational Complexity, 2014

2013

Fast matrix multiplication using coherent configurations.

Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms, 2013

2012

Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009).

SIAM J. Comput., 2012

Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421).

Dagstuhl Reports, 2012

On beating the hybrid argument.

Proceedings of the Innovations in Theoretical Computer Science 2012, 2012

Better Condensers and New Extractors from Parvaresh-Vardy Codes.

Proceedings of the 27th Conference on Computational Complexity, 2012

On Sunflowers and Matrix Multiplication.

Proceedings of the 27th Conference on Computational Complexity, 2012

2010

Special Section On Foundations of Computer Science.

SIAM J. Comput., 2010

Inapproximability for VCG-Based Combinatorial Auctions.

Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, 2010

2009

The complexity of the matroid-greedoid partition problem.

Theor. Comput. Sci., 2009

Low-End Uniform Hardness versus Randomness Tradeoffs for AM.

SIAM J. Comput., 2009

Electronic Colloquium on Computational Complexity (ECCC), 2009

Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms.

Electronic Colloquium on Computational Complexity (ECCC), 2009

The Complexity of Rationalizing Network Formation.

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

09421 Executive Summary - Algebraic Methods in Computational Complexity.

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

09421 Abstracts Collection - Algebraic Methods in Computational Complexity.

Proceedings of the Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009, 2009

2008

Fast polynomial factorization and modular composition in small characteristic.

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008

The Complexity of Rationalizing Matchings.

Proceedings of the Algorithms and Computation, 19th International Symposium, 2008

The Complexity of Boolean Formula Minimization.

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

Fast Modular Composition in any Characteristic.

Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science, 2008

Fast polynomial factorization and modular composition.

Proceedings of the Computational Complexity of Discrete Problems, 14.09. - 19.09.2008, 2008

2007

Lossless Condensers, Unbalanced Expanders, And Extractors.

Combinatorica, 2007

Low-end uniform hardness vs. randomness tradeoffs for AM.

Proceedings of the 39th Annual ACM Symposium on Theory of Computing, 2007

Algorithms for Playing Games with Limited Randomness.

Proceedings of the Algorithms, 2007

Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes.

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Complexity of two-level logic minimization.

IEEE Trans. on CAD of Integrated Circuits and Systems, 2006

On obtaining pseudorandomness from error-correcting codes..

Electronic Colloquium on Computational Complexity (ECCC), 2006

Extractors and condensers from univariate polynomials.

Electronic Colloquium on Computational Complexity (ECCC), 2006

Optimization Problems in the Polynomial-Time Hierarchy.

Proceedings of the Theory and Applications of Models of Computation, 2006

Group-theoretic algorithms for matrix multiplication.

Proceedings of the Symbolic and Algebraic Computation, International Symposium, 2006

On Obtaining Pseudorandomness from Error-Correcting Codes.

Proceedings of the FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science, 2006

Better lossless condensers through derandomized curve samplers.

Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 2006

2005

Simple extractors for all min-entropies and a new pseudorandom generator.

J. ACM, 2005

Group-theoretic Algorithms for Matrix Multiplication.

Proceedings of the 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2005), 2005

Pseudorandomness for Approximate Counting and Sampling.

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

On the Complexity of Succinct Zero-Sum Games.

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

Reconstructive Dispersers and Hitting Set Generators.

Proceedings of the Approximation, 2005

2004

Pseudorandomness for Approximate Counting and Sampling

Electronic Colloquium on Computational Complexity (ECCC), 2004

On the complexity of succinct zero-sum games

Electronic Colloquium on Computational Complexity (ECCC), 2004

2003

A Group-Theoretic Approach to Fast Matrix Multiplication.

Proceedings of the 44th Symposium on Foundations of Computer Science (FOCS 2003), 2003

2002

Pseudo-random generators for all hardnesses.

Proceedings of the Proceedings on 34th Annual ACM Symposium on Theory of Computing, 2002

Pseudo-Random Generators for All Hardnesses.

Proceedings of the 17th Annual IEEE Conference on Computational Complexity, 2002

2001

Loss-less condensers, unbalanced expanders, and extractors.

Proceedings of the Proceedings on 33rd Annual ACM Symposium on Theory of Computing, 2001

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

Proceedings of the 42nd Annual Symposium on Foundations of Computer Science, 2001

On the Complexity of Approximating the VC Dimension.

Proceedings of the 16th Annual IEEE Conference on Computational Complexity, 2001

1999

On the Complexity and Inapproximability of Shortest Implicant Problems.

Proceedings of the Automata, 1999

Proceedings of the 40th Annual Symposium on Foundations of Computer Science, 1999

1998

AnatomyBrowser: A Framework for Integration of Medical Information.

Proceedings of the Medical Image Computing and Computer-Assisted Intervention, 1998

The Minimum Equivalent DNF Problem and Shortest Implicants.

Proceedings of the 39th Annual Symposium on Foundations of Computer Science, 1998

1997

Hamiltonian Cycles in Solid Grid Graphs.

Proceedings of the 38th Annual Symposium on Foundations of Computer Science, 1997