Christopher Umans

CoRR, 2023

Matrix Multiplication via Matrix Groups.

[BibT_eX]

[DOI]

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

2022

Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace.

[BibT_eX]

[DOI]

William M. Hoza

SIAM J. Comput., 2022

Fast Multivariate Multipoint Evaluation Over All Finite Fields.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2022

2021

Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020.

[BibT_eX]

[DOI]

CoRR, 2021

2020

A New Algorithm for Fast Generalized DFTs.

[BibT_eX]

[DOI]

Chloe Ching-Yun Hsu

ACM Trans. Algorithms, 2020

2019

Fast Generalized DFTs for all Finite Groups.

[BibT_eX]

[DOI]

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2018

A fast generalized DFT for finite groups of Lie type.

[BibT_eX]

[DOI]

Chloe Ching-Yun Hsu

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

2017

Which groups are amenable to proving exponent two for matrix multiplication?

[BibT_eX]

[DOI]

CoRR, 2017

On Multidimensional and Monotone k-SUM.

[BibT_eX]

[DOI]

Chloe Ching-Yun Hsu

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

2016

Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2016

On cap sets and the group-theoretic approach to matrix multiplication.

[BibT_eX]

[DOI]

CoRR, 2016

On the Power of Quantum Fourier Sampling.

[BibT_eX]

[DOI]

Bill Fefferman

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.

[BibT_eX]

[DOI]

Zeyu Guo

Anand Kumar Narayanan

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

2014

Algebra in Computational Complexity (Dagstuhl Seminar 14391).

[BibT_eX]

[DOI]

Dagstuhl Reports, 2014

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

[BibT_eX]

[DOI]

Comput. Complex., 2014

2013

On Beating the Hybrid Argument.

[BibT_eX]

[DOI]

Theory Comput., 2013

On sunflowers and matrix multiplication.

[BibT_eX]

[DOI]

Noga Alon

Amir Shpilka

Comput. Complex., 2013

Fast matrix multiplication using coherent configurations.

[BibT_eX]

[DOI]

Henry Cohn

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

[BibT_eX]

[DOI]

SIAM J. Comput., 2012

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

[BibT_eX]

[DOI]

Manindra Agrawal

Thomas Thierauf

Dagstuhl Reports, 2012

Better Condensers and New Extractors from Parvaresh-Vardy Codes.

[BibT_eX]

[DOI]

Proceedings of the 27th Conference on Computational Complexity, 2012

2011

Fast Polynomial Factorization and Modular Composition.

[BibT_eX]

[DOI]

Kiran S. Kedlaya

SIAM J. Comput., 2011

The complexity of Boolean formula minimization.

[BibT_eX]

[DOI]

David Buchfuhrer

J. Comput. Syst. Sci., 2011

2010

Special Section On Foundations of Computer Science.

[BibT_eX]

[DOI]

James R. Lee

SIAM J. Comput., 2010

Pseudorandom generators and the BQP vs. PH problem

[BibT_eX]

[DOI]

Bill Fefferman

Christos H. Papadimitriou

CoRR, 2010

Inapproximability for VCG-Based Combinatorial Auctions.

[BibT_eX]

[DOI]

Michael Schapira

Yaron Singer

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

2009

The complexity of the matroid-greedoid partition problem.

[BibT_eX]

[DOI]

Vera Asodi

Theor. Comput. Sci., 2009

Low-End Uniform Hardness versus Randomness Tradeoffs for AM.

[BibT_eX]

[DOI]

SIAM J. Comput., 2009

Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Salil P. Vadhan

J. ACM, 2009

The Complexity of Rationalizing Network Formation.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2009

Improved inapproximability factors for some Sigma2p minimization problems.

[BibT_eX]

[DOI]

Kevin Dick

Electron. Colloquium Comput. Complex., 2009

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

[BibT_eX]

[DOI]

David Buchfuhrer

Electron. Colloquium Comput. Complex., 2009

Reconstructive Dispersers and Hitting Set Generators.

[BibT_eX]

[DOI]

Algorithmica, 2009

09421 Executive Summary - Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

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

09421 Abstracts Collection - Algebraic Methods in Computational Complexity.

[BibT_eX]

[DOI]

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

2008

The Complexity of Rationalizing Matchings.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2008

On the Complexity of Succinct Zero-Sum Games.

[BibT_eX]

[DOI]

Comput. Complex., 2008

Fast polynomial factorization and modular composition in small characteristic.

[BibT_eX]

[DOI]

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

Fast Modular Composition in any Characteristic.

[BibT_eX]

[DOI]

Kiran S. Kedlaya

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

2007

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Algorithms for Playing Games with Limited Randomness.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2007

Lossless Condensers, Unbalanced Expanders, And Extractors.

[BibT_eX]

[DOI]

David Zuckerman

Comb., 2007

2006

Complexity of two-level logic minimization.

[BibT_eX]

[DOI]

Alberto L. Sangiovanni-Vincentelli

Tiziano Villa

IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 2006

On obtaining pseudorandomness from error-correcting codes..

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2006

Extractors and condensers from univariate polynomials.

[BibT_eX]

[DOI]

Venkatesan Guruswami

Salil P. Vadhan

Electron. Colloquium Comput. Complex., 2006

Pseudorandomness for Approximate Counting and Sampling.

[BibT_eX]

[DOI]

Comput. Complex., 2006

Optimization Problems in the Polynomial-Time Hierarchy.

[BibT_eX]

[DOI]

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

Group-theoretic algorithms for matrix multiplication.

[BibT_eX]

[DOI]

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

Better lossless condensers through derandomized curve samplers.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

J. ACM, 2005

Group-theoretic Algorithms for Matrix Multiplication.

[BibT_eX]

[DOI]

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

2003

Pseudo-random generators for all hardnesses.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2003

A Group-Theoretic Approach to Fast Matrix Multiplication.

[BibT_eX]

[DOI]

Henry Cohn

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

2002

On the complexity of approximating the VC dimension.

[BibT_eX]

[DOI]

Elchanan Mossel

J. Comput. Syst. Sci., 2002

2001

The Minimum Equivalent DNF Problem and Shortest Implicants.

[BibT_eX]

[DOI]

J. Comput. Syst. Sci., 2001

Loss-less condensers, unbalanced expanders, and extractors.

[BibT_eX]

[DOI]

David Zuckerman

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.

[BibT_eX]

[DOI]

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

1999

On the Complexity and Inapproximability of Shortest Implicant Problems.

[BibT_eX]

[DOI]

Proceedings of the Automata, 1999

Hardness of Approximating Sigma2p Minimization Problems.

[BibT_eX]

[DOI]

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

1998

AnatomyBrowser: A Framework for Integration of Medical Information.

[BibT_eX]

[DOI]

Martha Elizabeth Shenton

Jens A. Richolt

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

1997

Hamiltonian Cycles in Solid Grid Graphs.

[BibT_eX]

[DOI]