Items where Person is "Umans-C"

2019

Umans, Christopher (2019) Fast generalized DFTs for all finite groups. In: 2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, pp. 793-805. ISBN 978-1-7281-4952-3. https://resolver.caltech.edu/CaltechAUTHORS:20191115-133902016

Hsu, Chloe Ching-Yun and Umans, Chris (2019) A New Algorithm for Fast Generalized DFTs. ACM Transactions on Algorithms, 16 (1). Art. No. 4. ISSN 1549-6325. https://resolver.caltech.edu/CaltechAUTHORS:20191115-080137932

2018

Bläser, Markus and Kabanets, Valentine and Torán, Jacobo et al. (2018) Algebraic Methods in Computational Complexity. Dagstuhl Reports, 8 (9). pp. 133-153. ISSN 2192-5283. https://resolver.caltech.edu/CaltechAUTHORS:20191115-154547839

Hsu, Chloe Ching-Yun and Umans, Chris (2018) A fast generalized DFT for finite groups of Lie type. In: Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms. Society for Industrial and Applied Mathematics , Philadelphia, PA, pp. 1047-1059. ISBN 978-1-6119-7503-1. https://resolver.caltech.edu/CaltechAUTHORS:20180410-153010180

2017

Blasiak, Jonah and Church, Thomas and Cohn, Henry et al. (2017) Which groups are amenable to proving exponent two for matrix multiplication? . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20191118-072853843

Umans, Chris (2017) FOCS 2017 Preface. In: 2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). IEEE , Piscataway, NJ, xiii. ISBN 978-1-5386-3464-6. https://resolver.caltech.edu/CaltechAUTHORS:20191118-123714214

Hsu, Chloe Ching-Yun and Umans, Chris (2017) On Multidimensional and Monotone k-SUM. In: 42nd International Symposium on Mathematical Foundations of Computer Science. Leibniz International Proceedings in Informatics. Dagstuhl Publishing , Wadern, Germany, Art. No. 50. ISBN 9783959770460. https://resolver.caltech.edu/CaltechAUTHORS:20191115-144427087

Hoza, William M. and Umans, Chris (2017) Targeted pseudorandom generators, simulation advice generators, and derandomizing logspace. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing - STOC 2017. ACM , New York, NY, pp. 629-640. ISBN 978-1-4503-4528-6. https://resolver.caltech.edu/CaltechAUTHORS:20170705-173204335

Blasiak, Jonah and Church, Thomas and Cohn, Henry et al. (2017) On cap sets and the group-theoretic approach to matrix multiplication. Discrete Analysis, 2017 (3). pp. 1-27. ISSN 2397-3129. https://resolver.caltech.edu/CaltechAUTHORS:20170531-152830870

2016

Kabanets, Valentine and Thierauf, Thomas and Torán, Jacobo et al. (2016) Algebraic and Combinatorial Methods in Computational Complexity. Dagstuhl Reports, 6 (10). pp. 13-32. ISSN 2192-5283. https://resolver.caltech.edu/CaltechAUTHORS:20191118-153821359

Fefferman, Bill and Umans, Christopher (2016) On the Power of Quantum Fourier Sampling. In: 11th Conference on the Theory of Quantum Computation, Communication and Cryptography (TQC 2016). Leibniz International Proceedings in Informatics. Dagstuhl Publishing , Wadern, Germany, Art. No. 1. ISBN 9783959770194. https://resolver.caltech.edu/CaltechAUTHORS:20191118-141357870

Guo, Zeyu and Narayanan, Anand Kumar and Umans, Chris (2016) Algebraic Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization over Finite Fields. In: 41st International Symposium on Mathematical Foundations of Computer Science (MFCS 2016). Leibniz International Proceedings in Informatics. Dagstuhl Publishing , Wadern, Germany, Art. No. 47. ISBN 9783959770163. https://resolver.caltech.edu/CaltechAUTHORS:20191118-103356388

2014

Agrawal, Manindra and Kabanets, Valentine and Thierauf, Thomas et al. (2014) Algebra in Computational Complexity. Dagstuhl Reports, 4 (9). pp. 85-105. ISSN 2192-5283. https://resolver.caltech.edu/CaltechAUTHORS:20191126-133603851

Umans, Christopher (2014) Special Issue “Conference on Computational Complexity 2013” Guest editor’s foreword. Computational Complexity, 23 (2). pp. 147-149. ISSN 1016-3328. https://resolver.caltech.edu/CaltechAUTHORS:20140701-090549753

2013

Fefferman, Bill and Shaltiel, Ronen and Umans, Christopher et al. (2013) On Beating the Hybrid Argument. Theory of Computing, 9 (1). pp. 809-843. ISSN 1557-2862. https://resolver.caltech.edu/CaltechAUTHORS:20191118-154821951

Alon, Noga and Shpilka, Amir and Umans, Christopher (2013) On sunflowers and matrix multiplication. Computational Complexity, 22 (2). pp. 219-243. ISSN 1016-3328. https://resolver.caltech.edu/CaltechAUTHORS:20130703-102109533

Cohn, Henry and Umans, Christopher (2013) Fast matrix multiplication using coherent configurations. In: Proceedings of the Twenty-Fourth Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM , Philadelphia, PA, pp. 1074-1087. ISBN 978-1-61197-251-1. https://resolver.caltech.edu/CaltechAUTHORS:20160913-165513831

2012

Immorlica, Nicole and Katz, Jonathan N. and Mitzenmacher, Michael et al. (2012) Special Section on the Forty-First Annual ACM Symposium on Theory of Computing (STOC 2009). SIAM Journal on Computing, 41 (6). pp. 1591-1592. ISSN 0097-5397. https://resolver.caltech.edu/CaltechAUTHORS:20191126-134942908

Agrawal, Manindra and Thierauf, Thomas and Umans, Christopher (2012) Algebraic and Combinatorial Methods in Computational Complexity. Dagstuhl Reports, 2 (10). pp. 60-78. ISSN 2192-5283. https://resolver.caltech.edu/CaltechAUTHORS:20191126-143839781

Ta-Shma, Amnon and Umans, Christopher (2012) Better Condensers and New Extractors from Parvaresh-Vardy Codes. In: 2012 IEEE 27th Conference on Computational Complexity. IEEE , Piscataway, NJ, pp. 309-315. ISBN 9780769547084. https://resolver.caltech.edu/CaltechAUTHORS:20191126-140535982

Alon, Noga and Shpilka, Amir and Umans, Christopher (2012) On Sunflowers and Matrix Multiplication. In: 27th Annual IEEE Conference on Computational Complexity (CCC). Annual IEEE Conference on Computational Complexity . IEEE , Piscataway, NJ, pp. 214-223. ISBN 978-1-4673-1663-7. https://resolver.caltech.edu/CaltechAUTHORS:20130703-110037886

Fefferman, Bill and Shaltiel, Ronen and Umans, Christopher et al. (2012) On beating the hybrid argument. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference. Association for Computing Machinery (ACM) , New York, NY, pp. 468-483. ISBN 978-1-4503-1115-1. https://resolver.caltech.edu/CaltechAUTHORS:20120522-093532704

2011

Kedlaya, Kiran S. and Umans, Christopher (2011) Fast Polynomial Factorization and Modular Composition. SIAM Journal on Computing, 40 (6). pp. 1767-1802. ISSN 0097-5397. https://resolver.caltech.edu/CaltechAUTHORS:20120125-151548395

Alon, Noga and Shpilka, Amir and Umans, Christopher (2011) On Sunflowers and Matrix Multiplication. Electronic Colloquium on Computational Complexity, 2011 . Art. No. 67. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20191126-142038137

Buchfuhrer, David and Umans, Christopher (2011) The complexity of Boolean formula minimization. Journal of Computer and System Sciences, 77 (1). pp. 142-153. ISSN 0022-0000. https://resolver.caltech.edu/CaltechAUTHORS:20110422-100438828

2010

Fefferman, Bill and Umans, Christopher and Shaltiel, Ronen et al. (2010) On beating the hybrid argument. Electronic Colloquium on Computational Complexity, 2010 . Art. No. 186. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20191126-153323226

Fefferman, Bill and Umans, Chris (2010) Pseudorandom generators and the BQP vs. PH problem. . (Unpublished) https://resolver.caltech.edu/CaltechAUTHORS:20191118-130935010

Lee, James R. and Umans, Chris (2010) Special Section On Foundations of Computer Science. SIAM Journal on Computing, 39 (6). p. 2397. ISSN 0097-5397. https://resolver.caltech.edu/CaltechAUTHORS:20191126-150500984

Buchfuhrer, Dave and Dughmi, Shaddin and Fu, Hu et al. (2010) Inapproximability for VCG-Based Combinatorial Auctions. In: Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete Algorithms. Proceedings in Applied Mathematics . No.135. Association for Computing Machinery , New York, NY, pp. 518-536. ISBN 978-0-898717-01-3. https://resolver.caltech.edu/CaltechAUTHORS:20100824-073813316

2009

Kalyanaraman, Shankar and Umans, Christopher (2009) The Complexity of Rationalizing Network Formation. Electronic Colloquium on Computational Complexity, 2009 . Art. No. 145. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20191127-082201341

Dick, Kevin and Umans, Christopher (2009) Improved inapproximability factors for some Σ^p₂ minimization problems. Electronic Colloquium on Computational Complexity, 2009 . Art. No. 107. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20191127-080702908

Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas et al. (2009) Algebraic Methods in Computational Complexity. In: Algebraic Methods in Computational Complexity: 09421 Abstracts Collection. Dagstuhl Publishing , Wadern, Germany. https://resolver.caltech.edu/CaltechAUTHORS:20191127-075729203

Agrawal, Manindra and Fortnow, Lance and Thierauf, Thomas et al. (2009) Algebraic Methods in Computational Complexity. In: Algebraic Methods in Computational Complexity: 09421 Abstracts Collection. Dagstuhl Publishing , Wadern, Germany, Art. No. 2410. https://resolver.caltech.edu/CaltechAUTHORS:20191127-093701543

Kalyanaraman, Shankar and Umans, Christopher (2009) The Complexity of Rationalizing Network Formation. In: 50th Annual IEEE Symposium on Foundations of Computer Science, 2009. Annual IEEE Symposium on Foundations of Computer Science. IEEE , pp. 485-494. ISBN 978-1-4244-5116-6. https://resolver.caltech.edu/CaltechAUTHORS:20100707-095613286

Shaltiel, Ronen and Umans, Christopher (2009) Low-End Uniform Hardness versus Randomness Tradeoffs for AM. SIAM Journal on Computing, 39 (3). pp. 1006-1037. ISSN 0097-5397. https://resolver.caltech.edu/CaltechAUTHORS:20091023-111539349

Umans, Christopher (2009) Reconstructive Dispersers and Hitting Set Generators. Algorithmica, 55 (1). pp. 134-156. ISSN 0178-4617. https://resolver.caltech.edu/CaltechAUTHORS:20090901-145722580

Buchfuhrer, David and Umans, Christopher (2009) Limits on the Social Welfare of Maximal-In-Range Auction Mechanisms. Electronic Colloquium on Computational Complexity, 2009 . Art. No. 68. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20191127-082848396

Guruswami, Venkatesan and Umans, Christopher and Vadhan, Salil (2009) Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. Journal of the ACM, 56 (4). p. 20. ISSN 0004-5411. https://resolver.caltech.edu/CaltechAUTHORS:20090817-144815953

Asodi, Vera and Umans, Christopher (2009) The complexity of the matroid-greedoid partition problem. Theoretical Computer Science, 410 (8-10). pp. 859-866. ISSN 0304-3975. https://resolver.caltech.edu/CaltechAUTHORS:20090422-111344642

2008

Kalyanaraman, Shankar and Umans, Christopher (2008) The Complexity of Rationalizing Matchings. In: Algorithms and Computation. Lecture Notes in Computer Science. No.5369. Springer , Berlin, pp. 171-182. ISBN 978-3-540-92181-3. https://resolver.caltech.edu/CaltechAUTHORS:20191126-155702845

Kedlaya, Kiran S. and Umans, Christopher (2008) Fast Modular Composition in any Characteristic. In: 2008 49th Annual IEEE Symposium on Foundations of Computer Science. IEEE , Piscataway, NJ, pp. 146-155. ISBN 978-0-7695-3436-7. https://resolver.caltech.edu/CaltechAUTHORS:20191126-160438923

Fortnow, Lance and Impagliazzo, Russell and Kabanets, Valentine et al. (2008) On the Complexity of Succinct Zero-Sum Games. Computational Complexity, 17 (3). pp. 353-376. ISSN 1016-3328. https://resolver.caltech.edu/CaltechAUTHORS:FORcc08

Kedlaya, Kiran S. and Umans, Christopher (2008) Fast polynomial factorization and modular composition. In: Algebraic Methods in Computational Complexity: 08381 Abstracts Collection. Dagstuhl Publishing , Wadern, Germany, Art. No. 1777. https://resolver.caltech.edu/CaltechAUTHORS:20191127-094213132

Buchfuhrer, David and Umans, Christopher (2008) The Complexity of Boolean Formula Minimization. In: Automata, Languages and Programming. Lecture Notes in Computer Science. No.5125. Springer , Berlin, pp. 24-35. ISBN 978-3-540-70574-1. https://resolver.caltech.edu/CaltechAUTHORS:20191112-131623581

Umans, Christopher (2008) Fast polynomial factorization and modular composition in small characteristic. In: STOC '08 Proceedings of the fortieth annual ACM symposium on Theory of computing. ACM , New York, NY, pp. 481-490. ISBN 978-1-60558-047-0. https://resolver.caltech.edu/CaltechAUTHORS:20170103-171822942

Kalyanaraman, Shankar and Umans, Christopher (2008) The Complexity of Rationalizing Matchings. Electronic Colloquium on Computational Complexity . Art. No. 21. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20191127-084809601

2007

Kalyanaraman, Shankar and Umans, Christopher (2007) Algorithms for Playing Games with Limited Randomness. In: Algorithms – ESA 2007. Lecture Notes in Computer Science. No.4698. Springer Berlin Heidelberg , Berlin, Heidelberg, pp. 323-334. ISBN 9783540755197. https://resolver.caltech.edu/CaltechAUTHORS:20190828-102317126

Shaltiel, Ronen and Umans, Christopher (2007) Low-end uniform hardness vs. randomness tradeoffs for AM. In: STOC '07 Proceedings of the thirty-ninth annual ACM symposium on Theory of computing. ACM , New York, NY, pp. 430-439. ISBN 978-1-59593-631-8. https://resolver.caltech.edu/CaltechAUTHORS:20161219-151217993

Guruswami, Venkatesan and Umans, Christopher and Vadhan, Salil (2007) Unbalanced Expanders and Randomness Extractors from Parvaresh-Vardy Codes. In: Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07). IEEE , Piscataway, NJ, pp. 96-108. ISBN 0-7695-2780-9. https://resolver.caltech.edu/CaltechAUTHORS:20170426-160240908

2006

Kalyanaraman, Shankar and Umans, Christopher (2006) On Obtaining Pseudorandomness from Error-Correcting Codes. In: FSTTCS 2006: Foundations of Software Technology and Theoretical Computer Science. Lecture Notes in Computer Science. No.4337. Springer , Berlin, Heidelberg, pp. 105-116. ISBN 9783540499947. https://resolver.caltech.edu/CaltechAUTHORS:20190828-102318013

Shaltiel, Ronen and Umans, Christopher (2006) Pseudorandomness for Approximate Counting and Sampling. Computational Complexity, 15 (4). pp. 298-341. ISSN 1016-3328. https://resolver.caltech.edu/CaltechAUTHORS:20110811-085055181

Kalyanaraman, Shankar and Umans, Christopher (2006) On obtaining pseudorandomness from error-correcting codes. Electronic Colloquium on Computational Complexity, 2006 . TR06-128. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20190829-152850467

Ta-Shma, Amnon and Umans, Christopher (2006) Better lossless condensers through derandomized curve samplers. In: 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS'06). IEEE , Piscataway, NJ, pp. 177-186. ISBN 0-7695-2720-5. https://resolver.caltech.edu/CaltechAUTHORS:20170427-151755097

Umans, Christopher and Villa, Tiziano and Sangiovanni-Vincentelli, Alberto L. (2006) Complexity of two-level logic minimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25 (7). pp. 1230-1246. ISSN 0278-0070. https://resolver.caltech.edu/CaltechAUTHORS:UMAieeetcadics06

Umans, Christopher (2006) Group-theoretic algorithms for matrix multiplication. In: ISSAC '06 Proceedings of the 2006 international symposium on Symbolic and algebraic computation. ACM , New York, NY, p. 5. ISBN 1-59593-276-3. https://resolver.caltech.edu/CaltechAUTHORS:20170103-170341500

Umans, Christopher (2006) Optimization Problems in the Polynomial-Time Hierarchy. In: Theory and Applications of Models of Computation. Lecture Notes in Computer Science. No.3959. Springer , Berlin, pp. 345-355. ISBN 978-3-540-34021-8. https://resolver.caltech.edu/CaltechAUTHORS:20200127-140148446

2005

Shaltiel, Ronen and Umans, Christopher (2005) Simple extractors for all min-entropies and a new pseudorandom generator. Journal of the ACM, 52 (2). pp. 172-216. ISSN 0004-5411. https://resolver.caltech.edu/CaltechAUTHORS:20161219-150257214

Cohn, Henry and Kleinberg, Robert and Szegedy, Balázs et al. (2005) Group-theoretic Algorithms for Matrix Multiplication. In: 46th Annual IEEE Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science. IEEE , Los Alamitos, CA, pp. 379-388. ISBN 0-7695-2468-0. https://resolver.caltech.edu/CaltechAUTHORS:20110609-141427936

Umans, Christopher (2005) Reconstructive Dispersers and Hitting Set Generators. In: Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques. Lecture Notes in Computer Science. No.3624. Springer , Berlin, pp. 460-471. ISBN 978-3-540-28239-6. https://resolver.caltech.edu/CaltechAUTHORS:20200609-101642741

2003

Cohn, Henry and Umans, Christopher (2003) A Group-theoretic Approach to Fast Matrix Multiplication. In: 44th Annual IEEE Symposium on Foundations of Computer Science. IEEE , Los Alamitos, CA, pp. 438-449. ISBN 0-7695-2040-5. https://resolver.caltech.edu/CaltechAUTHORS:20111026-095124253

2002

Umans, Christopher (2002) Pseudo-Random Generators for All Hardnesses. In: 17th Annual Conference on Computational Complexity. Annual IEEE Conference on Computational Complexity. IEEE , Los Alamitos, CA, p. 7. ISBN 0-7695-1468-5. https://resolver.caltech.edu/CaltechAUTHORS:20111110-081820059

2001

Shaltiel, Ronen and Umans, Christopher (2001) Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator. In: 42nd Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, pp. 648-657. ISBN 0-7695-1390-5. https://resolver.caltech.edu/CaltechAUTHORS:20111121-092803461

Mossel, Elchanan and Umans, Christopher (2001) On the Complexity of Approximating the VC dimension. In: 16th Annual IEEE Conference on Computational Complexity Proceedings. Annual IEEE Conference on Computational Complexity. IEEE Computer Society , Los Alamitos, CA, pp. 220-225. ISBN 0-7695-1054-X. https://resolver.caltech.edu/CaltechAUTHORS:20111118-115638180

1999

Umans, Christopher (1999) Hardness of Approximating Σ^(p)_(2) Minimization Problems. In: 40th Annual Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, pp. 465-474. ISBN 0-7695-0409-4. https://resolver.caltech.edu/CaltechAUTHORS:20120109-142652598

1998

Umans, Christopher (1998) The Minimum Equivalent DNF Problem and Shortest Implicants. In: 39th Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, pp. 556-563. ISBN 0-8186-9172-7. https://resolver.caltech.edu/CaltechAUTHORS:20120119-070934161

1997

Umans, Christopher and Lenhart, William (1997) Hamiltonian cycles in solid grid graphs. In: 38th Annual Symposium on Foundations of Computer Science: Proceedings. Los Alamitos, CA , IEEE Computer Society Press, pp. 496-505. ISBN 0-8186-8197-7. https://resolver.caltech.edu/CaltechAUTHORS:20120126-092849476