![](https://dblp.uni-trier.de/img/logo.ua.320x120.png)
![](https://dblp.uni-trier.de/img/dropdown.dark.16x16.png)
![](https://dblp.uni-trier.de/img/peace.dark.16x16.png)
Остановите войну!
for scientists:
![search dblp search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
![search dblp](https://dblp.uni-trier.de/img/search.dark.16x16.png)
default search action
Christopher Umans
Person information
- affiliation: California Institute of Technology, Pasadena, USA
Refine list
![note](https://dblp.uni-trier.de/img/note-mark.dark.12x12.png)
refinements active!
zoomed in on ?? of ?? records
view refined list in
export refined list as
Journal Articles
- 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) - 2022
- [j21]William M. Hoza
, Chris Umans:
Targeted Pseudorandom Generators, Simulation Advice Generators, and Derandomizing Logspace. SIAM J. Comput. 51(2): 17-281 (2022) - 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) - 2014
- [j19]Christopher Umans:
Special Issue "Conference on Computational Complexity 2013" Guest editor's foreword. Comput. Complex. 23(2): 147-149 (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) - 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) - 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) - 2010
- [j13]James R. Lee, Christopher Umans:
Special Section On Foundations of Computer Science. SIAM J. Comput. 39(6): 2397 (2010) - 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) - 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) - 2007
- [j7]Amnon Ta-Shma
, Christopher Umans, David Zuckerman:
Lossless Condensers, Unbalanced Expanders, And Extractors. Comb. 27(2): 213-240 (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) - 2005
- [j4]Ronen Shaltiel, Christopher Umans:
Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM 52(2): 172-216 (2005) - 2003
- [j3]Christopher Umans:
Pseudo-random generators for all hardnesses. J. Comput. Syst. Sci. 67(2): 419-440 (2003) - 2002
- [j2]Elchanan Mossel
, Christopher Umans:
On the complexity of approximating the VC dimension. J. Comput. Syst. Sci. 65(4): 660-671 (2002) - 2001
- [j1]Christopher Umans:
The Minimum Equivalent DNF Problem and Shortest Implicants. J. Comput. Syst. Sci. 63(4): 597-611 (2001)
Conference and Workshop Papers
- 2023
- [c40]Jonah Blasiak, Henry Cohn, Joshua A. Grochow, Kevin Pratt, Chris Umans:
Matrix Multiplication via Matrix Groups. ITCS 2023: 19:1-19:16 - 2022
- [c39]Vishwas Bhargava
, Sumanta Ghosh, Zeyu Guo
, Mrinal Kumar, Chris Umans:
Fast Multivariate Multipoint Evaluation Over All Finite Fields. FOCS 2022: 221-232 - 2019
- [c38]Chris Umans:
Fast Generalized DFTs for all Finite Groups. FOCS 2019: 793-805 - 2018
- [c37]Chloe Ching-Yun Hsu, Chris Umans:
A fast generalized DFT for finite groups of Lie type. SODA 2018: 1047-1059 - 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 - 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 - 2013
- [c32]Henry Cohn, Christopher Umans:
Fast matrix multiplication using coherent configurations. SODA 2013: 1074-1087 - 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 - 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 - 2009
- [c27]Shankar Kalyanaraman, Christopher Umans:
The Complexity of Rationalizing Network Formation. FOCS 2009: 485-494 - 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 - 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 - 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 - 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 - 2003
- [c11]Henry Cohn, Christopher Umans:
A Group-Theoretic Approach to Fast Matrix Multiplication. FOCS 2003: 438-449 - 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
- [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 - 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
Editorship
- 2017
- [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] - 2016
- [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] - 2009
- [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]
Informal and Other Publications
- 2023
- [i33]Emile Anand, Chris Umans:
Pseudorandomness of the Sticky Random Walk. CoRR abs/2307.11104 (2023) - 2022
- [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) - 2019
- [i28]Chris Umans:
Fast generalized DFTs for all finite groups. CoRR abs/1901.02536 (2019) - 2018
- [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
- [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
- [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
- [i19]Manindra Agrawal, Valentine Kabanets, Thomas Thierauf, Christopher Umans:
Algebra in Computational Complexity (Dagstuhl Seminar 14391). Dagstuhl Reports 4(9): 85-105 (2014) - 2012
- [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
- [i16]Noga Alon, Amir Shpilka, Christopher Umans:
On Sunflowers and Matrix Multiplication. Electron. Colloquium Comput. Complex. TR11 (2011) - 2010
- [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) - 2009
- [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
- [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
- [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
- [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) - 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)
Coauthor Index
![](https://dblp.uni-trier.de/img/cog.dark.24x24.png)
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-08-05 21:15 CEST by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint