default search action
Christopher Umans
Person information
- affiliation: California Institute of Technology, Pasadena, USA
Refine list
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
2020 – today
- 2024
- [j22]Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans:
Fast Multivariate Multipoint Evaluation over All Finite Fields. J. ACM 71(3): 22 (2024) - [i34]Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans:
Finite matrix multiplication algorithms from infinite groups. CoRR abs/2410.14905 (2024) - 2023
- [c40]Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans:
Matrix Multiplication via Matrix Groups. ITCS 2023: 19:1-19:16 - [i33]Emile Anand, Chris Umans:
Pseudorandomness of the Sticky Random Walk. CoRR abs/2307.11104 (2023) - 2022
- [j21]William M. Hoza, Chris Umans:
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. SIAM J. Comput. 51(2): 17-281 (2022) - [c39]Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans:
Fast Multivariate Multipoint Evaluation Over All Finite Fields. FOCS 2022: 221-232 - [i32]Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans:
Matrix multiplication via matrix groups. CoRR abs/2204.03826 (2022) - [i31]Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans:
Fast Multivariate Multipoint Evaluation Over All Finite Fields. CoRR abs/2205.00342 (2022) - [i30]Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans:
Fast Multivariate Multipoint Evaluation Over All Finite Fields. Electron. Colloquium Comput. Complex. TR22 (2022) - 2021
- [i29]Shuchi Chawla, Jelani Nelson, Chris Umans, David P. Woodruff:
Visions in Theoretical Computer Science: A Report on the TCS Visioning Workshop 2020. CoRR abs/2107.02846 (2021) - 2020
- [j20]Chloe Ching-Yun Hsu, Chris Umans:
A New Algorithm for Fast Generalized DFTs. ACM Trans. Algorithms 16(1): 4:1-4:20 (2020)
2010 – 2019
- 2019
- [c38]Chris Umans:
Fast Generalized DFTs for all Finite Groups. FOCS 2019: 793-805 - [i28]Chris Umans:
Fast generalized DFTs for all finite groups. CoRR abs/1901.02536 (2019) - 2018
- [c37]Chloe Ching-Yun Hsu, Chris Umans:
A fast generalized DFT for finite groups of Lie type. SODA 2018: 1047-1059 - [i27]Markus Bläser, Valentine Kabanets, Jacobo Torán, Christopher Umans:
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 18391). Dagstuhl Reports 8(9): 133-153 (2018) - 2017
- [c36]Chloe Ching-Yun Hsu, Chris Umans:
On Multidimensional and Monotone k-SUM. MFCS 2017: 50:1-50:13 - [c35]William M. Hoza, Chris Umans:
Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. STOC 2017: 629-640 - [e3]Chris Umans:
58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017. IEEE Computer Society 2017, ISBN 978-1-5386-3464-6 [contents] - [i26]Chloe Ching-Yun Hsu, Chris Umans:
A fast generalized DFT for finite groups of Lie type. CoRR abs/1707.00349 (2017) - [i25]Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans:
Which groups are amenable to proving exponent two for matrix multiplication? CoRR abs/1712.02302 (2017) - 2016
- [c34]Zeyu Guo, Anand Kumar Narayanan, Chris Umans:
Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. MFCS 2016: 47:1-47:14 - [c33]Bill Fefferman, Christopher Umans:
On the Power of Quantum Fourier Sampling. TQC 2016: 1:1-1:19 - [e2]Klaus Jansen, Claire Mathieu, José D. P. Rolim, Chris Umans:
Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX/RANDOM 2016, September 7-9, 2016, Paris, France. LIPIcs 60, Schloss Dagstuhl - Leibniz-Zentrum für Informatik 2016, ISBN 978-3-95977-018-7 [contents] - [i24]Jonah Blasiak, Thomas Church, Henry Cohn, Joshua A. Grochow, Chris Umans:
On cap sets and the group-theoretic approach to matrix multiplication. CoRR abs/1605.06702 (2016) - [i23]Zeyu Guo, Anand Kumar Narayanan, Chris Umans:
Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. CoRR abs/1606.04592 (2016) - [i22]William M. Hoza, Chris Umans:
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. CoRR abs/1610.01199 (2016) - [i21]Valentine Kabanets, Thomas Thierauf, Jacobo Torán, Christopher Umans:
Algebraic Methods in Computational Complexity (Dagstuhl Seminar 16411). Dagstuhl Reports 6(10): 13-32 (2016) - 2015
- [i20]Bill Fefferman, Chris Umans:
The Power of Quantum Fourier Sampling. CoRR abs/1507.05592 (2015) - 2014
- [j19]Christopher Umans:
Special Issue "Conference on Computational Complexity 2013" Guest editor's foreword. Comput. Complex. 23(2): 147-149 (2014) - [i19]Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, Christopher Umans:
Algebra in Computational Complexity (Dagstuhl Seminar 14391). Dagstuhl Reports 4(9): 85-105 (2014) - 2013
- [j18]Noga Alon, Amir Shpilka, Christopher Umans:
On sunflowers and matrix multiplication. Comput. Complex. 22(2): 219-243 (2013) - [j17]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On Beating the Hybrid Argument. Theory Comput. 9: 809-843 (2013) - [c32]Henry Cohn, Christopher Umans:
Fast matrix multiplication using coherent configurations. SODA 2013: 1074-1087 - 2012
- [j16]Nicole Immorlica, Jonathan Katz, Michael Mitzenmacher, Rocco A. Servedio, Chris Umans:
Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009). SIAM J. Comput. 41(6): 1591-1592 (2012) - [c31]Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication. CCC 2012: 214-223 - [c30]Amnon Ta-Shma, Christopher Umans:
Better Condensers and New Extractors from Parvaresh-Vardy Codes. CCC 2012: 309-315 - [c29]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On beating the hybrid argument. ITCS 2012: 468-483 - [i18]Henry Cohn, Christopher Umans:
Fast matrix multiplication using coherent configurations. CoRR abs/1207.6528 (2012) - [i17]Manindra Agrawal, Thomas Thierauf, Christopher Umans:
Algebraic and Combinatorial Methods in Computational Complexity (Dagstuhl Seminar 12421). Dagstuhl Reports 2(10): 60-78 (2012) - 2011
- [j15]David Buchfuhrer, Christopher Umans:
The complexity of Boolean formula minimization. J. Comput. Syst. Sci. 77(1): 142-153 (2011) - [j14]Kiran S. Kedlaya, Christopher Umans:
Fast Polynomial Factorization and Modular Composition. SIAM J. Comput. 40(6): 1767-1802 (2011) - [i16]Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [j13]James R. Lee, Christopher Umans:
Special Section On Foundations of Computer Science. SIAM J. Comput. 39(6): 2397 (2010) - [c28]David Buchfuhrer, Shaddin Dughmi, Hu Fu, Robert Kleinberg, Elchanan Mossel, Christos H. Papadimitriou, Michael Schapira, Yaron Singer, Christopher Umans:
Inapproximability for VCG-Based Combinatorial Auctions. SODA 2010: 518-536 - [i15]Bill Fefferman, Christopher Umans:
Pseudorandom generators and the BQP vs. PH problem. CoRR abs/1007.0305 (2010) - [i14]Bill Fefferman, Ronen Shaltiel, Christopher Umans, Emanuele Viola:
On beating the hybrid argument. Electron. Colloquium Comput. Complex. TR10 (2010)
2000 – 2009
- 2009
- [j12]Christopher Umans:
Reconstructive Dispersers and Hitting Set Generators. Algorithmica 55(1): 134-156 (2009) - [j11]Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM 56(4): 20:1-20:34 (2009) - [j10]Ronen Shaltiel, Christopher Umans:
Low-End Uniform Hardness versus Randomness Tradeoffs for AM. SIAM J. Comput. 39(3): 1006-1037 (2009) - [j9]Vera Asodi, Christopher Umans:
The complexity of the matroid-greedoid partition problem. Theor. Comput. Sci. 410(8-10): 859-866 (2009) - [c27]Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Network Formation. FOCS 2009: 485-494 - [e1]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
Algebraic Methods in Computational Complexity, 11.10. - 16.10.2009. Dagstuhl Seminar Proceedings 09421, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Germany 2009 [contents] - [i13]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
09421 Abstracts Collection - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2009 - [i12]Manindra Agrawal, Lance Fortnow, Thomas Thierauf, Christopher Umans:
09421 Executive Summary - Algebraic Methods in Computational Complexity. Algebraic Methods in Computational Complexity 2009 - [i11]David Buchfuhrer, Christopher Umans:
Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms. Electron. Colloquium Comput. Complex. TR09 (2009) - [i10]Kevin Dick, Christopher Umans:
Improved inapproximability factors for some Sigma2p minimization problems. Electron. Colloquium Comput. Complex. TR09 (2009) - [i9]Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Network Formation. Electron. Colloquium Comput. Complex. TR09 (2009) - 2008
- [j8]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. Comput. Complex. 17(3): 353-376 (2008) - [c26]Kiran S. Kedlaya, Christopher Umans:
Fast Modular Composition in any Characteristic. FOCS 2008: 146-155 - [c25]David Buchfuhrer, Christopher Umans:
The Complexity of Boolean Formula Minimization. ICALP (1) 2008: 24-35 - [c24]Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Matchings. ISAAC 2008: 171-182 - [c23]Christopher Umans:
Fast polynomial factorization and modular composition in small characteristic. STOC 2008: 481-490 - [i8]Kiran S. Kedlaya, Christopher Umans:
Fast polynomial factorization and modular composition. Computational Complexity of Discrete Problems 2008 - [i7]Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Matchings. Electron. Colloquium Comput. Complex. TR08 (2008) - 2007
- [j7]Amnon Ta-Shma, Christopher Umans, David Zuckerman:
Lossless Condensers, Unbalanced Expanders, And Extractors. Comb. 27(2): 213-240 (2007) - [c22]Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. CCC 2007: 96-108 - [c21]Shankar Kalyanaraman, Christopher Umans:
Algorithms for Playing Games with Limited Randomness. ESA 2007: 323-334 - [c20]Ronen Shaltiel, Christopher Umans:
Low-end uniform hardness vs. randomness tradeoffs for AM. STOC 2007: 430-439 - [i6]Shankar Kalyanaraman, Christopher Umans:
Algorithms for Playing Games with Limited Randomness. Electron. Colloquium Comput. Complex. TR07 (2007) - [i5]Ronen Shaltiel, Christopher Umans:
Low-end uniform hardness vs. randomness tradeoffs for AM. Electron. Colloquium Comput. Complex. TR07 (2007) - 2006
- [j6]Ronen Shaltiel, Christopher Umans:
Pseudorandomness for Approximate Counting and Sampling. Comput. Complex. 15(4): 298-341 (2006) - [j5]Christopher Umans, Tiziano Villa, Alberto L. Sangiovanni-Vincentelli:
Complexity of two-level logic minimization. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst. 25(7): 1230-1246 (2006) - [c19]Amnon Ta-Shma, Christopher Umans:
Better lossless condensers through derandomized curve samplers. FOCS 2006: 177-186 - [c18]Shankar Kalyanaraman, Christopher Umans:
On Obtaining Pseudorandomness from Error-Correcting Codes. FSTTCS 2006: 105-116 - [c17]Christopher Umans:
Group-theoretic algorithms for matrix multiplication. ISSAC 2006: 5 - [c16]Christopher Umans:
Optimization Problems in the Polynomial-Time Hierarchy. TAMC 2006: 345-355 - [i4]Venkatesan Guruswami, Christopher Umans, Salil P. Vadhan:
Extractors and condensers from univariate polynomials. Electron. Colloquium Comput. Complex. TR06 (2006) - [i3]Shankar Kalyanaraman, Christopher Umans:
On obtaining pseudorandomness from error-correcting codes.. Electron. Colloquium Comput. Complex. TR06 (2006) - 2005
- [j4]Ronen Shaltiel, Christopher Umans:
Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM 52(2): 172-216 (2005) - [c15]Christopher Umans:
Reconstructive Dispersers and Hitting Set Generators. APPROX-RANDOM 2005: 460-471 - [c14]Ronen Shaltiel, Christopher Umans:
Pseudorandomness for Approximate Counting and Sampling. CCC 2005: 212-226 - [c13]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the Complexity of Succinct Zero-Sum Games. CCC 2005: 323-332 - [c12]Henry Cohn, Robert D. Kleinberg, Balázs Szegedy, Christopher Umans:
Group-theoretic Algorithms for Matrix Multiplication. FOCS 2005: 379-388 - 2004
- [i2]Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans:
On the complexity of succinct zero-sum games. Electron. Colloquium Comput. Complex. TR04 (2004) - [i1]Ronen Shaltiel, Christopher Umans:
Pseudorandomness for Approximate Counting and Sampling. Electron. Colloquium Comput. Complex. TR04 (2004) - 2003
- [j3]Christopher Umans:
Pseudo-random generators for all hardnesses. J. Comput. Syst. Sci. 67(2): 419-440 (2003) - [c11]Henry Cohn, Christopher Umans:
A Group-Theoretic Approach to Fast Matrix Multiplication. FOCS 2003: 438-449 - 2002
- [j2]Elchanan Mossel, Christopher Umans:
On the complexity of approximating the VC dimension. J. Comput. Syst. Sci. 65(4): 660-671 (2002) - [c10]Christopher Umans:
Pseudo-Random Generators for All Hardnesses. CCC 2002: 11 - [c9]Christopher Umans:
Pseudo-random generators for all hardnesses. STOC 2002: 627-634 - 2001
- [j1]Christopher Umans:
The Minimum Equivalent DNF Problem and Shortest Implicants. J. Comput. Syst. Sci. 63(4): 597-611 (2001) - [c8]Elchanan Mossel, Christopher Umans:
On the Complexity of Approximating the VC Dimension. CCC 2001: 220-225 - [c7]Ronen Shaltiel, Christopher Umans:
Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator. FOCS 2001: 648-657 - [c6]Amnon Ta-Shma, Christopher Umans, David Zuckerman:
Loss-less condensers, unbalanced expanders, and extractors. STOC 2001: 143-152
1990 – 1999
- 1999
- [c5]Christopher Umans:
Hardness of Approximating Sigma2p Minimization Problems. FOCS 1999: 465-474 - [c4]Christopher Umans:
On the Complexity and Inapproximability of Shortest Implicant Problems. ICALP 1999: 687-696 - 1998
- [c3]Christopher Umans:
The Minimum Equivalent DNF Problem and Shortest Implicants. FOCS 1998: 556-563 - [c2]Polina Golland, Ron Kikinis, Christopher Umans, Michael Halle, Martha Elizabeth Shenton, Jens A. Richolt:
AnatomyBrowser: A Framework for Integration of Medical Information. MICCAI 1998: 720-731 - 1997
- [c1]Christopher Umans, William J. Lenhart:
Hamiltonian Cycles in Solid Grid Graphs. FOCS 1997: 496-505
Coauthor Index
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
Unpaywalled article links
Add open access links from to the list of external document links (if available).
Privacy notice: By enabling the option above, your browser will contact the API of unpaywall.org to load hyperlinks to open access articles. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Unpaywall privacy policy.
Archived links via Wayback Machine
For web page which are no longer available, try to retrieve content from the of the Internet Archive (if available).
Privacy notice: By enabling the option above, your browser will contact the API of archive.org to check for archived content of web pages that are no longer available. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Internet Archive privacy policy.
Reference lists
Add a list of references from , , and to record detail pages.
load references from crossref.org and opencitations.net
Privacy notice: By enabling the option above, your browser will contact the APIs of crossref.org, opencitations.net, and semanticscholar.org to load article reference information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the Crossref privacy policy and the OpenCitations privacy policy, as well as the AI2 Privacy Policy covering Semantic Scholar.
Citation data
Add a list of citing articles from and to record detail pages.
load citations from opencitations.net
Privacy notice: By enabling the option above, your browser will contact the API of opencitations.net and semanticscholar.org to load citation information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the OpenCitations privacy policy as well as the AI2 Privacy Policy covering Semantic Scholar.
OpenAlex data
Load additional information about publications from .
Privacy notice: By enabling the option above, your browser will contact the API of openalex.org to load additional information. Although we do not have any reason to believe that your call will be tracked, we do not have any control over how the remote server uses your data. So please proceed with care and consider checking the information given by OpenAlex.
last updated on 2024-12-01 01:10 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint