- Fefferman, Bill and Umans, Chris (2019) Pseudorandom
generators and the BQP vs. PH problem; 10.48550/arXiv.1007.0305
- Blasiak, Jonah; Church, Thomas; et el. (2019) Which
groups are amenable to proving exponent two for matrix
multiplication?; 10.48550/arXiv.1712.02302
- Hsu, Chloe Ching-Yun and Umans, Chris (2019) A
New Algorithm for Fast Generalized DFTs; ACM Transactions on
Algorithms; Vol. 16; No. 1; Art. No. 4; 10.1145/3301313
- Umans, Christopher (2019) Fast
generalized DFTs for all finite groups; ISBN 978-1-7281-4952-3; 2019
IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS);
IEEE: Piscataway, NJ; 793-805; 10.1109/FOCS.2019.00052
- Bläser, Markus; Kabanets, Valentine; et el. (2018) Algebraic
Methods in Computational Complexity; Dagstuhl Reports; Vol. 8;
No. 9; 133-153; 10.4230/DagRep.8.9.133
- Hsu, Chloe Ching-Yun and Umans, Chris (2018) A
fast generalized DFT for finite groups of Lie type; ISBN
978-1-6119-7503-1; Proceedings of the Twenty-Ninth Annual ACM-SIAM
Symposium on Discrete Algorithms; Society for Industrial and Applied
Mathematics: Philadelphia, PA; 1047-1059; 10.48550/arXiv.1707.00349
- Umans, Chris (2017) FOCS
2017 Preface; ISBN 978-1-5386-3464-6; 2017 IEEE 58th Annual
Symposium on Foundations of Computer Science (FOCS); IEEE: Piscataway,
NJ; xiii; 10.1109/FOCS.2017.5
- Hsu, Chloe Ching-Yun and Umans, Chris (2017) On
Multidimensional and Monotone k-SUM; ISBN 9783959770460; 42nd
International Symposium on Mathematical Foundations of Computer Science;
Dagstuhl Publishing: Wadern, Germany; Art. No. 50; 10.4230/LIPIcs.MFCS.2017.50
- Hoza, William M. and Umans, Chris (2017) Targeted
pseudorandom generators, simulation advice generators, and derandomizing
logspace; ISBN 978-1-4503-4528-6; Proceedings of the 49th Annual ACM
SIGACT Symposium on Theory of Computing - STOC 2017; ACM: New York, NY;
629-640; 10.1145/3055399.3055414
- Blasiak, Jonah; Church, Thomas; et el. (2017) On
cap sets and the group-theoretic approach to matrix multiplication;
Discrete Analysis; Vol. 2017; No. 3; 1-27; 10.19086/da.1245
- Kabanets, Valentine; Thierauf, Thomas; et el. (2016) Algebraic
and Combinatorial Methods in Computational Complexity; Dagstuhl
Reports; Vol. 6; No. 10; 13-32; 10.4230/DagRep.6.10.13
- Fefferman, Bill and Umans, Christopher (2016) On
the Power of Quantum Fourier Sampling; ISBN 9783959770194; 11th
Conference on the Theory of Quantum Computation, Communication and
Cryptography (TQC 2016); Dagstuhl Publishing: Wadern, Germany; Art.
No. 1; 10.4230/LIPIcs.TQC.2016.1
- Guo, Zeyu; Narayanan, Anand Kumar; et el. (2016) Algebraic
Problems Equivalent to Beating Exponent 3/2 for Polynomial Factorization
over Finite Fields; ISBN 9783959770163; 41st International Symposium
on Mathematical Foundations of Computer Science (MFCS 2016); Dagstuhl
Publishing: Wadern, Germany; Art. No. 47; 10.4230/LIPIcs.MFCS.2016.47
- Agrawal, Manindra; Kabanets, Valentine; et el. (2014) Algebra
in Computational Complexity; Dagstuhl Reports; Vol. 4; No. 9;
85-105; 10.4230/DagRep.4.9.85
- Umans, Christopher (2014) Special
Issue “Conference on Computational Complexity 2013” Guest editor’s
foreword; Computational Complexity; Vol. 23; No. 2; 147-149; 10.1007/s00037-014-0088-x
- Fefferman, Bill; Shaltiel, Ronen; et el. (2013) On
Beating the Hybrid Argument; Theory of Computing; Vol. 9; No. 1;
809-843; 10.4086/toc.2013.v009a026
- Alon, Noga; Shpilka, Amir; et el. (2013) On
sunflowers and matrix multiplication; Computational Complexity; Vol.
22; No. 2; 219-243; 10.1007/s00037-013-0060-1
- Cohn, Henry and Umans, Christopher (2013) Fast
matrix multiplication using coherent configurations; ISBN
978-1-61197-251-1; Proceedings of the Twenty-Fourth Annual ACM-SIAM
Symposium on Discrete Algorithms; SIAM: Philadelphia, PA; 1074-1087; 10.1137/1.9781611973105.77
- Immorlica, Nicole; Katz, Jonathan N.; et el. (2012) Special
Section on the Forty-First Annual ACM Symposium on Theory of Computing
(STOC 2009); SIAM Journal on Computing; Vol. 41; No. 6; 1591-1592;
10.1137/120973305
- Agrawal, Manindra; Thierauf, Thomas; et el. (2012) Algebraic
and Combinatorial Methods in Computational Complexity; Dagstuhl
Reports; Vol. 2; No. 10; 60-78; 10.4230/DagRep.2.10.60
- Ta-Shma, Amnon and Umans, Christopher (2012) Better
Condensers and New Extractors from Parvaresh-Vardy Codes; ISBN
9780769547084; 2012 IEEE 27th Conference on Computational Complexity;
IEEE: Piscataway, NJ; 309-315; 10.1109/ccc.2012.25
- Alon, Noga; Shpilka, Amir; et el. (2012) On
Sunflowers and Matrix Multiplication; ISBN 978-1-4673-1663-7; 27th
Annual IEEE Conference on Computational Complexity (CCC); IEEE:
Piscataway, NJ; 214-223; 10.1109/CCC.2012.26
- Fefferman, Bill; Shaltiel, Ronen; et el. (2012) On
beating the hybrid argument; ISBN 978-1-4503-1115-1; Proceedings of
the 3rd Innovations in Theoretical Computer Science Conference;
Association for Computing Machinery (ACM): New York, NY; 468-483; 10.1145/2090236.2090273
- Kedlaya, Kiran S. and Umans, Christopher (2011) Fast
Polynomial Factorization and Modular Composition; SIAM Journal on
Computing; Vol. 40; No. 6; 1767-1802; 10.1137/08073408X
- Alon, Noga; Shpilka, Amir; et el. (2011) On
Sunflowers and Matrix Multiplication; Electronic Colloquium on
Computational Complexity; Vol. 2011; Art. No. 67
- Buchfuhrer, David and Umans, Christopher (2011) The
complexity of Boolean formula minimization; Journal of Computer and
System Sciences; Vol. 77; No. 1; 142-153; 10.1016/j.jcss.2010.06.011
- Fefferman, Bill; Umans, Christopher; et el. (2010) On
beating the hybrid argument; Electronic Colloquium on Computational
Complexity; Vol. 2010; Art. No. 186
- Lee, James R. and Umans, Chris (2010) Special
Section On Foundations of Computer Science; SIAM Journal on
Computing; Vol. 39; No. 6; 2397-2397; 10.1137/smjcat000039000006002397000001
- Buchfuhrer, Dave; Dughmi, Shaddin; et el. (2010) Inapproximability
for VCG-Based Combinatorial Auctions; ISBN 978-0-898717-01-3;
Proceedings of the Twenty-first Annual ACM-SIAM Symposium on Discrete
Algorithms; Association for Computing Machinery: New York, NY;
518-536
- Kalyanaraman, Shankar and Umans, Christopher (2009) The
Complexity of Rationalizing Network Formation; Electronic Colloquium
on Computational Complexity; Vol. 2009; Art. No. 145
- Dick, Kevin and Umans, Christopher (2009) Improved
inapproximability factors for some Σ^p₂ minimization problems;
Electronic Colloquium on Computational Complexity; Vol. 2009; Art.
No. 107
- Agrawal, Manindra; Fortnow, Lance; et el. (2009) Algebraic
Methods in Computational Complexity
- Agrawal, Manindra; Fortnow, Lance; et el. (2009) Algebraic
Methods in Computational Complexity
- Kalyanaraman, Shankar and Umans, Christopher (2009) The
Complexity of Rationalizing Network Formation; ISBN
978-1-4244-5116-6; 50th Annual IEEE Symposium on Foundations of Computer
Science, 2009; IEEE; 485-494; 10.1109/FOCS.2009.48
- Shaltiel, Ronen and Umans, Christopher (2009) Low-End
Uniform Hardness versus Randomness Tradeoffs for AM; SIAM Journal on
Computing; Vol. 39; No. 3; 1006-1037; 10.1137/070698348
- Umans, Christopher (2009) Reconstructive
Dispersers and Hitting Set Generators; Algorithmica; Vol. 55; No. 1;
134-156; 10.1007/s00453-008-9266-z
- Buchfuhrer, David and Umans, Christopher (2009) Limits
on the Social Welfare of Maximal-In-Range Auction Mechanisms;
Electronic Colloquium on Computational Complexity; Vol. 2009; Art.
No. 68
- Guruswami, Venkatesan; Umans, Christopher; et el. (2009) Unbalanced
expanders and randomness extractors from Parvaresh-Vardy codes;
Journal of the ACM; Vol. 56; No. 4; 20; 10.1145/1538902.1538904
- Asodi, Vera and Umans, Christopher (2009) The
complexity of the matroid-greedoid partition problem; Theoretical
Computer Science; Vol. 410; No. 8-10; 859-866; 10.1016/j.tcs.2008.11.019
- Kalyanaraman, Shankar and Umans, Christopher (2008) The
Complexity of Rationalizing Matchings; ISBN 978-3-540-92181-3;
Algorithms and Computation; Springer: Berlin; 171-182; 10.1007/978-3-540-92182-0_18
- Kedlaya, Kiran S. and Umans, Christopher (2008) Fast
Modular Composition in any Characteristic; ISBN 978-0-7695-3436-7;
2008 49th Annual IEEE Symposium on Foundations of Computer Science;
IEEE: Piscataway, NJ; 146-155; 10.1109/focs.2008.13
- Fortnow, Lance; Impagliazzo, Russell; et el. (2008) On the
Complexity of Succinct Zero-Sum Games; Computational Complexity;
Vol. 17; No. 3; 353-376; 10.1007/s00037-008-0252-2
- Kedlaya, Kiran S. and Umans, Christopher (2008) Fast
polynomial factorization and modular composition
- Buchfuhrer, David and Umans, Christopher (2008) The
Complexity of Boolean Formula Minimization; ISBN 978-3-540-70574-1;
Automata, Languages and Programming; Springer: Berlin; 24-35; 10.1007/978-3-540-70575-8_3
- Umans, Christopher (2008) Fast
polynomial factorization and modular composition in small
characteristic; ISBN 978-1-60558-047-0; STOC ’08 Proceedings of the
fortieth annual ACM symposium on Theory of computing; ACM: New York, NY;
481-490; 10.1145/1374376.1374445
- Kalyanaraman, Shankar and Umans, Christopher (2008) The
Complexity of Rationalizing Matchings; Electronic Colloquium on
Computational Complexity; Art. No. 21
- Kalyanaraman, Shankar and Umans, Christopher (2007) Algorithms
for Playing Games with Limited Randomness; ISBN 9783540755197;
Algorithms – ESA 2007; Springer Berlin Heidelberg: Berlin, Heidelberg;
323-334; 10.1007/978-3-540-75520-3_30
- Shaltiel, Ronen and Umans, Christopher (2007) Low-end
uniform hardness vs. randomness tradeoffs for AM; ISBN
978-1-59593-631-8; STOC ’07 Proceedings of the thirty-ninth annual ACM
symposium on Theory of computing; ACM: New York, NY; 430-439; 10.1145/1250790.1250854
- Guruswami, Venkatesan; Umans, Christopher; et el. (2007) Unbalanced
Expanders and Randomness Extractors from Parvaresh-Vardy Codes; ISBN
0-7695-2780-9; Twenty-Second Annual IEEE Conference on Computational
Complexity (CCC’07); IEEE: Piscataway, NJ; 96-108; 10.1109/CCC.2007.38
- Kalyanaraman, Shankar and Umans, Christopher (2006) On
Obtaining Pseudorandomness from Error-Correcting Codes; ISBN
9783540499947; FSTTCS 2006: Foundations of Software Technology and
Theoretical Computer Science; Springer: Berlin, Heidelberg; 105-116; 10.1007/11944836_12
- Shaltiel, Ronen and Umans, Christopher (2006) Pseudorandomness
for Approximate Counting and Sampling; Computational Complexity;
Vol. 15; No. 4; 298-341; 10.1007/s00037-007-0218-9
- Kalyanaraman, Shankar and Umans, Christopher (2006) On
obtaining pseudorandomness from error-correcting codes; Electronic
Colloquium on Computational Complexity; Vol. 2006; TR06-128
- Ta-Shma, Amnon and Umans, Christopher (2006) Better
lossless condensers through derandomized curve samplers; ISBN
0-7695-2720-5; 47th Annual IEEE Symposium on Foundations of Computer
Science (FOCS’06); IEEE: Piscataway, NJ; 177-186; 10.1109/FOCS.2006.18
- Umans, Christopher; Villa, Tiziano; et el. (2006) Complexity
of two-level logic minimization; IEEE Transactions on Computer-Aided
Design of Integrated Circuits and Systems; Vol. 25; No. 7; 1230-1246; 10.1109/TCAD.2005.855944
- Umans, Christopher (2006) Group-theoretic
algorithms for matrix multiplication; ISBN 1-59593-276-3; ISSAC ’06
Proceedings of the 2006 international symposium on Symbolic and
algebraic computation; ACM: New York, NY; 5; 10.1145/1145768.1145772
- Umans, Christopher (2006) Optimization
Problems in the Polynomial-Time Hierarchy; ISBN 978-3-540-34021-8;
Theory and Applications of Models of Computation; Springer: Berlin;
345-355; 10.1007/11750321_33
- Shaltiel, Ronen and Umans, Christopher (2005) Simple
extractors for all min-entropies and a new pseudorandom generator;
Journal of the ACM; Vol. 52; No. 2; 172-216; 10.1145/1059513.1059516
- Cohn, Henry; Kleinberg, Robert; et el. (2005) Group-theoretic
Algorithms for Matrix Multiplication; ISBN 0-7695-2468-0; 46th
Annual IEEE Symposium on Foundations of Computer Science; IEEE: Los
Alamitos, CA; 379-388; 10.1109/SFCS.2005.39
- Umans, Christopher (2005) Reconstructive
Dispersers and Hitting Set Generators; ISBN 978-3-540-28239-6;
Approximation, Randomization and Combinatorial Optimization. Algorithms
and Techniques; Springer: Berlin; 460-471; 10.1007/11538462_39
- Cohn, Henry and Umans, Christopher (2003) A
Group-theoretic Approach to Fast Matrix Multiplication; ISBN
0-7695-2040-5; 44th Annual IEEE Symposium on Foundations of Computer
Science; IEEE: Los Alamitos, CA; 438-449; 10.1109/SFCS.2003.1238217
- Umans, Christopher (2002) Pseudo-Random
Generators for All Hardnesses; ISBN 0-7695-1468-5; 17th Annual
Conference on Computational Complexity; IEEE: Los Alamitos, CA; 7-7; 10.1109/CCC.2002.1004326
- Shaltiel, Ronen and Umans, Christopher (2001) Simple
Extractors for All Min-Entropies and a New Pseudo-Random Generator;
ISBN 0-7695-1390-5; 42nd Annual Symposium on Foundations of Computer
Science; IEEE Computer Society: Los Alamitos, CA; 648-657; 10.1109/SFCS.2001.959941
- Mossel, Elchanan and Umans, Christopher (2001) On
the Complexity of Approximating the VC dimension; ISBN
0-7695-1054-X; 16th Annual IEEE Conference on Computational Complexity
Proceedings; IEEE Computer Society: Los Alamitos, CA; 220-225; 10.1109/CCC.2001.933889
- Umans, Christopher (1999) Hardness
of Approximating Σ^(p)_(2) Minimization Problems; ISBN
0-7695-0409-4; 40th Annual Symposium on Foundations of Computer Science;
IEEE Computer Society: Los Alamitos, CA; 465-474; 10.1109/SFFCS.1999.814619
- Umans, Christopher (1998) The
Minimum Equivalent DNF Problem and Shortest Implicants; ISBN
0-8186-9172-7; 39th Annual Symposium on Foundations of Computer Science;
IEEE Computer Society: Los Alamitos, CA; 556-563; 10.1109/SFCS.1998.743506
- Umans, Christopher and Lenhart, William (1997) Hamiltonian
cycles in solid grid graphs; ISBN 0-8186-8197-7; 38th Annual
Symposium on Foundations of Computer Science: Proceedings; Los Alamitos,
CA: IEEE Computer Society Press; 496-505; 10.1109/SFCS.1997.646138