Jump to content

Chris Umans: Difference between revisions

Add links
From Wikipedia, the free encyclopedia
Browse history interactively
← Previous edit
Content deleted Content added
VisualWikitext
No edit summary
Citation bot (talk | contribs)
Bots
5,392,451 edits
Altered pages. Add: doi-access, pages, issue, volume. Removed URL that duplicated identifier. Formatted dashes. | Use this bot. Report bugs. | Suggested by Headbomb | Linked from Wikipedia:WikiProject_Academic_Journals/Journals_cited_by_Wikipedia/Sandbox2 | #UCB_webform_linked 365/1051
 
(10 intermediate revisions by 9 users not shown)
Line 1: Line 1:
{{Infobox scientist
{{Infobox scientist
| boxwidth =
| boxwidth =
| name = Christopher Umans
| name = Christopher Umans
| image =
| image =
| image_size =
| image_size =
| alt =
| alt =
| caption =
| caption =
| birth_date =
| birth_date =
| birth_place =
| birth_place =
| residence =
| residence =
| nationality = {{flagicon|US}} [[US|American]]
| nationality = [[US|American]]
| fields = [[Computer Science]]
| fields = [[Computer Science]]
| workplaces = [[California Institute of Technology]]
| workplaces = [[California Institute of Technology]]
| alma_mater = [[Williams College]], [[University of California, Berkeley]]
| alma_mater = [[Williams College]], [[University of California, Berkeley]]
| doctoral_advisor = [[Christos Papadimitriou]]
| doctoral_advisor = [[Christos Papadimitriou]]
| academic_advisors =
| academic_advisors =
| doctoral_students =
| doctoral_students =
| notable_students =
| notable_students =
| known_for = [[Analysis of algorithms|Computational complexity]], [[Algorithms]], [[Hardness of approximation]], [[Matrix Multiplication]]
| known_for = [[Analysis of algorithms|Computational complexity]], [[algorithms]], [[hardness of approximation]], [[matrix multiplication]]
| awards =
| awards =
}}
}}


Line 27: Line 27:


==Research==
==Research==
Umans' research centers broadly around algorithms and complexity. He has made notable contributions to varied areas within this space including [[random number generation]], [[expander graph|expanders]], and algorithms for [[matrix multiplication]]. A notable example is his work on developing a group theoretic approach for matrix multiplication.<ref name="C1"/>
Umans' research centers broadly around algorithms and complexity. He has made notable contributions to varied areas within this space including [[random number generation]], [[expander graph|expanders]], and algorithms for [[matrix multiplication]]. A notable example is his work on developing a group theoretic approach for matrix multiplication.<ref name="C1"/><ref name="M2" /><ref name="M3" /><ref name="ASU" /><ref name="M4" /><ref name="M5" /><ref name="M6" />


In 2008, Umans and his student Dave Buchfuhrer settled a 1979 conjecture on the complexity of [[Circuit minimization for Boolean functions|unbounded Boolean formula minimization]]; the result won a best paper award at [[ICALP]].
In 2008, Umans and his student Dave Buchfuhrer settled a 1979 conjecture on the complexity of [[Circuit minimization for Boolean functions|unbounded Boolean formula minimization]]; the result won a best paper award at [[ICALP]].<ref name="Buchfuhrer_2011"/>
<ref name="Buchfuhrer_2011"/>


==Awards and honors==
==Awards and honors==

Umans received an NSF CAREER award in 2004 and an Alfred P. Sloan Fellowship in 2005.<ref name="C2"/> Additionally, his work has received "Best Paper" awards at the International Conference on Automata, Languages, and Programming (ICALP) and the IEEE Conference on Computational Complexity (CCC).
Umans received an NSF CAREER award in 2004 and an Alfred P. Sloan Fellowship in 2005.<ref name="C2"/> Additionally, his work has received "Best Paper" awards at the International Conference on Automata, Languages, and Programming (ICALP) and the IEEE Conference on Computational Complexity (CCC).


==References==
==References==
{{Reflist|refs=
{{Reflist|refs=
<ref name="C1">{{citation |doi=10.1109/SFCS.2003.1238217 |chapter=A group-theoretic approach to fast matrix multiplication|arxiv=math/0307321|title=44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings|pages=438–449|year=2003|last1=Cohn|first1=H.|last2=Umans|first2=C.|isbn=978-0-7695-2040-7}}</ref>
<ref name="C1">{{citation |doi=10.1109/SFCS.2003.1238217 |chapter=A group-theoretic approach to fast matrix multiplication|arxiv=math/0307321|title=44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings|pages=438–449|year=2003|last1=Cohn|first1=H.|last2=Umans|first2=C.|isbn=978-0-7695-2040-7|s2cid=5890100 }}</ref>
<ref name="C2">[http://www.sloan.org/sloan-research-fellowships/ Sloan Fellows]</ref>
<ref name="C2">[http://www.sloan.org/sloan-research-fellowships/ Sloan Fellows]</ref>
<ref name="Buchfuhrer_2011">{{cite journal |doi=10.1016/j.jcss.2010.06.011 |title=The complexity of Boolean formula minimization |journal=Journal of Computer and System Sciences (JCSS) |volume=77 |issue=1 |pages=142–153 |date=January 2011 |location=Computer Science Department, [[California Institute of Technology]], Pasadena, CA, USA |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans |publisher=[[Elsevier Inc.]] |url=https://ac.els-cdn.com/S0022000010000954/1-s2.0-S0022000010000954-main.pdf?_tid=045f1450-f937-11e7-ae63-00000aab0f26&acdnat=1515940215_dae38335610ea5f94fd299e5e7c95ffb}} This is an extended version of the conference paper: {{cite book |doi=10.1007/978-3-540-70575-8_3 |chapter=The Complexity of Boolean Formula Minimization |title=Proceedings of Automata, Languages and Programming |location=35th International Colloquium (ICALP) |volume=5125 |pages=24–35 |publisher=[[Springer-Verlag]] |publication-place=Berlin / Heidelberg, Germany |series=[[Lecture Notes in Computer Science]] (LNCS) |date=2008 |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans |isbn=978-3-540-70574-1 |chapter-url=http://users.cms.caltech.edu/~umans/papers/BU07.pdf |access-date=2018-01-14 |url-status=live |archive-url=https://web.archive.org/web/20180114141842/http://users.cms.caltech.edu/~umans/papers/BU07.pdf |archive-date=2018-01-14}} This won the Best Paper Award in Track A "Algorithms, Automata, Complexity and Games".</ref>
<ref name="Buchfuhrer_2011">{{cite journal |doi=10.1016/j.jcss.2010.06.011 |doi-access=free |title=The complexity of Boolean formula minimization |journal=Journal of Computer and System Sciences (JCSS) |volume=77 |issue=1 |pages=142–153 |date=January 2011 |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |author-link2=Christopher Umans}} This is an extended version of the conference paper: {{cite conference |doi=10.1007/978-3-540-70575-8_3 |chapter=The Complexity of Boolean Formula Minimization |book-title=Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I |editor=Luca Aceto |editor2=Ivan Damgård |display-editors=etal |pages=24–35 |publisher=[[Springer-Verlag]] |location=Berlin / Heidelberg, Germany |series=[[Lecture Notes in Computer Science]] (LNCS) 5125 |date=2008 |author-last1=Buchfuhrer |author-first1=David |author-last2=Umans |author-first2=Christopher |title=Automata, Languages and Programming |volume=5125 |author-link2=Christopher Umans |isbn=978-3-540-70574-1 |url=http://users.cms.caltech.edu/~umans/papers/BU07.pdf |access-date=2018-01-14 |url-status=live |archive-url=https://web.archive.org/web/20180114141842/http://users.cms.caltech.edu/~umans/papers/BU07.pdf |archive-date=2018-01-14}} This won the Best Paper Award in Track A "Algorithms, Automata, Complexity and Games".</ref>
<ref name="M2">{{cite conference|last1=Cohn|first1=Henry|last2=Kleinberg|first2=Robert|last3=Szegedy|first3=Balász|last4=Umans|first4=Christopher|title=Group-theoretic Algorithms for Matrix Multiplication|url=https://doi.org/10.1109/SFCS.2005.39|publisher=IEEE|book-title=Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS)|date=2005|pages=379–388|doi=10.1109/SFCS.2005.39|arxiv=math/0511460}}</ref>
<ref name="M3">{{cite conference|last1=Cohn|first1=Henry|last2=Umans|first2=Christopher|title=Fast matrix multiplication using coherent configurations|url=https://doi.org/10.1137/1.9781611973105.77|publisher=SIAM|book-title=Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)|date=2013|pages=1074–1087|doi=10.1137/1.9781611973105.77|arxiv=1207.6528}}</ref>
<ref name="M4">{{cite journal|last1=Blasiak|first1=Jonah|last2=Church|first2=Thomas|last3=Cohn|first3=Henry|last4=Grochow|first4=Joshua A.|last5=Naslund|first5=Eric|last6=Sawin|first6=William F.|last7=Umans|first7=Christopher|title=On cap sets and the group-theoretic approach to matrix multiplication|journal=Discrete Analysis|year=2017|url=https://doi.org/10.19086/da.1245|doi=10.19086/da.1245|arxiv=1605.06702}}</ref>
<ref name="M5">{{cite arXiv |last1=Blasiak|first1=Jonah|last2=Church|first2=Thomas|last3=Cohn|first3=Henry|last4=Grochow|first4=Joshua A.|last5=Umans|first5=Christopher|date=2017|title=Which groups are amenable to proving exponent two for matrix multiplication?|eprint=1712.02302 |class=math.GR}}</ref>
<ref name="M6">{{cite conference|last1=Blasiak|first1=Jonah|last2=Cohn|first2=Henry|last3=Grochow|first3=Joshua A.|last4=Pratt|first4=Kevin|last5=Umans|first5=Christopher|title=Matrix Multiplication via Matrix Groups|publisher=Schloss Dagstuhl - Leibniz-Zentrum für Informatik|book-title=14th Innovations in Theoretical Computer Science Conference (ITCS 2023)|date=2023|pages=19:1–19:16|doi=10.4230/LIPIcs.ITCS.2023.19|doi-access=free }}</ref>
<ref name="ASU">{{cite journal|last1=Alon|first1=Noga|last2=Shpilka|first2=Amir|last3=Umans|first3=Christopher|title=On sunflowers and matrix multiplication|journal=Computational Complexity|year=2013|volume=22 |issue=2 |pages=219–243 |url=https://doi.org/10.1007/s00037-013-0060-1|doi=10.1007/s00037-013-0060-1}}</ref>
}}
}}


Latest revision as of 21:22, 28 July 2024

Christopher Umans
NationalityAmerican
Alma materWilliams College, University of California, Berkeley
Known forComputational complexity, algorithms, hardness of approximation, matrix multiplication
Scientific career
FieldsComputer Science
InstitutionsCalifornia Institute of Technology
Doctoral advisorChristos Papadimitriou

Christopher Umans is a professor of Computer Science in the Computing and Mathematical Sciences Department at the California Institute of Technology. He is known for work on algorithms, computational complexity, algebraic complexity, and hardness of approximation.

Academic biography

[edit]

Umans studied at Williams College, where he completed a BA degree in Mathematics and Computer Science in 1996. He then received a PhD in Computer Science from University of California, Berkeley in 2000 under Christos Papadimitriou. Following his PhD, he was a postdoctoral researcher at Microsoft Research until joining Caltech in 2002.

Research

[edit]

Umans' research centers broadly around algorithms and complexity. He has made notable contributions to varied areas within this space including random number generation, expanders, and algorithms for matrix multiplication. A notable example is his work on developing a group theoretic approach for matrix multiplication.[1][2][3][4][5][6][7]

In 2008, Umans and his student Dave Buchfuhrer settled a 1979 conjecture on the complexity of unbounded Boolean formula minimization; the result won a best paper award at ICALP.[8]

Awards and honors

[edit]

Umans received an NSF CAREER award in 2004 and an Alfred P. Sloan Fellowship in 2005.[9] Additionally, his work has received "Best Paper" awards at the International Conference on Automata, Languages, and Programming (ICALP) and the IEEE Conference on Computational Complexity (CCC).

References

[edit]
  1. ^ Cohn, H.; Umans, C. (2003), "A group-theoretic approach to fast matrix multiplication", 44th Annual IEEE Symposium on Foundations of Computer Science, 2003. Proceedings, pp. 438–449, arXiv:math/0307321, doi:10.1109/SFCS.2003.1238217, ISBN 978-0-7695-2040-7, S2CID 5890100
  2. ^ Cohn, Henry; Kleinberg, Robert; Szegedy, Balász; Umans, Christopher (2005). "Group-theoretic Algorithms for Matrix Multiplication". Proc. 46th Annual IEEE Symposium on Foundations of Computer Science (FOCS). IEEE. pp. 379–388. arXiv:math/0511460. doi:10.1109/SFCS.2005.39.
  3. ^ Cohn, Henry; Umans, Christopher (2013). "Fast matrix multiplication using coherent configurations". Proc. 24th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM. pp. 1074–1087. arXiv:1207.6528. doi:10.1137/1.9781611973105.77.
  4. ^ Alon, Noga; Shpilka, Amir; Umans, Christopher (2013). "On sunflowers and matrix multiplication". Computational Complexity. 22 (2): 219–243. doi:10.1007/s00037-013-0060-1.
  5. ^ Blasiak, Jonah; Church, Thomas; Cohn, Henry; Grochow, Joshua A.; Naslund, Eric; Sawin, William F.; Umans, Christopher (2017). "On cap sets and the group-theoretic approach to matrix multiplication". Discrete Analysis. arXiv:1605.06702. doi:10.19086/da.1245.
  6. ^ Blasiak, Jonah; Church, Thomas; Cohn, Henry; Grochow, Joshua A.; Umans, Christopher (2017). "Which groups are amenable to proving exponent two for matrix multiplication?". arXiv:1712.02302 [math.GR].
  7. ^ Blasiak, Jonah; Cohn, Henry; Grochow, Joshua A.; Pratt, Kevin; Umans, Christopher (2023). "Matrix Multiplication via Matrix Groups". 14th Innovations in Theoretical Computer Science Conference (ITCS 2023). Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 19:1–19:16. doi:10.4230/LIPIcs.ITCS.2023.19.
  8. ^ Buchfuhrer, David; Umans, Christopher (January 2011). "The complexity of Boolean formula minimization". Journal of Computer and System Sciences (JCSS). 77 (1): 142–153. doi:10.1016/j.jcss.2010.06.011. This is an extended version of the conference paper: Buchfuhrer, David; Umans, Christopher (2008). "Automata, Languages and Programming" (PDF). In Luca Aceto; Ivan Damgård; et al. (eds.). Automata, Languages and Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I. Lecture Notes in Computer Science (LNCS) 5125. Vol. 5125. Berlin / Heidelberg, Germany: Springer-Verlag. pp. 24–35. doi:10.1007/978-3-540-70575-8_3. ISBN 978-3-540-70574-1. Archived (PDF) from the original on 2018-01-14. Retrieved 2018-01-14. This won the Best Paper Award in Track A "Algorithms, Automata, Complexity and Games".
  9. ^ Sloan Fellows
[edit]
Retrieved from "https://en.wikipedia.org/enwiki/w/index.php?title=Chris_Umans&oldid=1237248195"