206:
Umans received an NSF CAREER award in 2004 and an Alfred P. Sloan
Fellowship in 2005. 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).
593:
416:
Blasiak, Jonah; Church, Thomas; Cohn, Henry; Grochow, Joshua A.; Umans, Christopher (2017). "Which groups are amenable to proving exponent two for matrix multiplication?".
191:
598:
175:
Umans' research centers broadly around algorithms and complexity. He has made notable contributions to varied areas within this space including
528:
251:
505:
Automata, Languages and
Programming: 35th International Colloquium, ICALP 2008, Reykjavik, Iceland, July 7-11, 2008, Proceedings, Part I
156:
124:
92:
43:
437:
Blasiak, Jonah; Cohn, Henry; Grochow, Joshua A.; Pratt, Kevin; Umans, Christopher (2023). "Matrix
Multiplication via Matrix Groups".
508:
534:
155:, where he completed a BA degree in Mathematics and Computer Science in 1996. He then received a PhD in Computer Science from
379:
Blasiak, Jonah; Church, Thomas; Cohn, Henry; Grochow, Joshua A.; Naslund, Eric; Sawin, William F.; Umans, Christopher (2017).
140:
61:
176:
588:
160:
136:
132:
104:
53:
184:
65:
187:. A notable example is his work on developing a group theoretic approach for matrix multiplication.
417:
388:
320:
283:
257:
229:
164:
524:
493:
463:
247:
190:
In 2008, Umans and his student Dave
Buchfuhrer settled a 1979 conjecture on the complexity of
516:
479:
442:
398:
361:
330:
293:
239:
152:
120:
99:
82:
39:
512:
224:
Cohn, H.; Umans, C. (2003), "A group-theoretic approach to fast matrix multiplication",
180:
549:
This won the Best Paper Award in Track A "Algorithms, Automata, Complexity and Games".
497:
582:
558:
261:
520:
447:
226:
44th Annual IEEE Symposium on
Foundations of Computer Science, 2003. Proceedings
484:
467:
334:
365:
243:
128:
57:
312:
349:
274:
Cohn, Henry; Kleinberg, Robert; Szegedy, Balász; Umans, Christopher (2005).
441:. Schloss Dagstuhl - Leibniz-Zentrum für Informatik. pp. 19:1–19:16.
280:
Proc. 46th Annual IEEE Symposium on
Foundations of Computer Science (FOCS)
297:
573:
439:
14th
Innovations in Theoretical Computer Science Conference (ITCS 2023)
381:"On cap sets and the group-theoretic approach to matrix multiplication"
275:
402:
288:
234:
422:
393:
380:
325:
317:
Proc. 24th Annual ACM-SIAM Symposium on
Discrete Algorithms (SODA)
195:
123:
in the
Computing and Mathematical Sciences Department at the
511:(LNCS) 5125. Vol. 5125. Berlin / Heidelberg, Germany:
29:
313:"Fast matrix multiplication using coherent configurations"
163:. Following his PhD, he was a postdoctoral researcher at
348:
Alon, Noga; Shpilka, Amir; Umans, Christopher (2013).
276:"Group-theoretic Algorithms for Matrix Multiplication"
490:
This is an extended version of the conference paper:
503:. In Luca Aceto; Ivan Damgård; et al. (eds.).
98:
88:
78:
49:
35:
25:
18:
468:"The complexity of Boolean formula minimization"
472:Journal of Computer and System Sciences (JCSS)
8:
594:California Institute of Technology faculty
15:
483:
446:
421:
392:
350:"On sunflowers and matrix multiplication"
324:
287:
233:
311:Cohn, Henry; Umans, Christopher (2013).
216:
194:; the result won a best paper award at
192:unbounded Boolean formula minimization
498:"Automata, Languages and Programming"
7:
574:Chris Umans professional home page
157:University of California, Berkeley
125:California Institute of Technology
93:California Institute of Technology
44:University of California, Berkeley
14:
509:Lecture Notes in Computer Science
599:Theoretical computer scientists
540:from the original on 2018-01-14
167:until joining Caltech in 2002.
1:
319:. SIAM. pp. 1074–1087.
521:10.1007/978-3-540-70575-8_3
448:10.4230/LIPIcs.ITCS.2023.19
615:
485:10.1016/j.jcss.2010.06.011
335:10.1137/1.9781611973105.77
282:. IEEE. pp. 379–388.
127:. He is known for work on
366:10.1007/s00037-013-0060-1
244:10.1109/SFCS.2003.1238217
141:hardness of approximation
110:
71:
62:hardness of approximation
354:Computational Complexity
177:random number generation
133:computational complexity
54:Computational complexity
161:Christos Papadimitriou
105:Christos Papadimitriou
185:matrix multiplication
183:, and algorithms for
66:matrix multiplication
298:10.1109/SFCS.2005.39
228:, pp. 438–449,
137:algebraic complexity
492:Buchfuhrer, David;
462:Buchfuhrer, David;
515:. pp. 24–35.
494:Umans, Christopher
464:Umans, Christopher
165:Microsoft Research
147:Academic biography
119:is a professor of
530:978-3-540-70574-1
385:Discrete Analysis
253:978-0-7695-2040-7
202:Awards and honors
151:Umans studied at
117:Christopher Umans
114:
113:
73:Scientific career
20:Christopher Umans
606:
561:
556:
550:
548:
546:
545:
539:
502:
489:
487:
466:(January 2011).
459:
453:
452:
450:
434:
428:
427:
425:
413:
407:
406:
403:10.19086/da.1245
396:
376:
370:
369:
345:
339:
338:
328:
308:
302:
301:
291:
271:
265:
264:
237:
221:
153:Williams College
121:Computer Science
100:Doctoral advisor
83:Computer Science
40:Williams College
16:
614:
613:
609:
608:
607:
605:
604:
603:
579:
578:
570:
565:
564:
557:
553:
543:
541:
537:
531:
513:Springer-Verlag
500:
491:
461:
460:
456:
436:
435:
431:
415:
414:
410:
378:
377:
373:
347:
346:
342:
310:
309:
305:
273:
272:
268:
254:
223:
222:
218:
213:
204:
173:
149:
36:Alma mater
21:
12:
11:
5:
612:
610:
602:
601:
596:
591:
581:
580:
577:
576:
569:
568:External links
566:
563:
562:
551:
529:
478:(1): 142–153.
454:
429:
408:
371:
360:(2): 219–243.
340:
303:
266:
252:
215:
214:
212:
209:
203:
200:
172:
169:
159:in 2000 under
148:
145:
112:
111:
108:
107:
102:
96:
95:
90:
86:
85:
80:
76:
75:
69:
68:
51:
50:Known for
47:
46:
37:
33:
32:
27:
23:
22:
19:
13:
10:
9:
6:
4:
3:
2:
611:
600:
597:
595:
592:
590:
589:Living people
587:
586:
584:
575:
572:
571:
567:
560:
559:Sloan Fellows
555:
552:
536:
532:
526:
522:
518:
514:
510:
506:
499:
495:
486:
481:
477:
473:
469:
465:
458:
455:
449:
444:
440:
433:
430:
424:
419:
412:
409:
404:
400:
395:
390:
386:
382:
375:
372:
367:
363:
359:
355:
351:
344:
341:
336:
332:
327:
322:
318:
314:
307:
304:
299:
295:
290:
285:
281:
277:
270:
267:
263:
259:
255:
249:
245:
241:
236:
231:
227:
220:
217:
210:
208:
201:
199:
197:
193:
188:
186:
182:
178:
170:
168:
166:
162:
158:
154:
146:
144:
142:
138:
134:
130:
126:
122:
118:
109:
106:
103:
101:
97:
94:
91:
87:
84:
81:
77:
74:
70:
67:
63:
59:
55:
52:
48:
45:
41:
38:
34:
31:
28:
24:
17:
554:
542:. Retrieved
504:
475:
471:
457:
438:
432:
411:
384:
374:
357:
353:
343:
316:
306:
289:math/0511460
279:
269:
235:math/0307321
225:
219:
205:
189:
174:
150:
116:
115:
89:Institutions
72:
26:Nationality
583:Categories
544:2018-01-14
423:1712.02302
394:1605.06702
211:References
129:algorithms
58:algorithms
326:1207.6528
181:expanders
535:Archived
496:(2008).
171:Research
30:American
262:5890100
527:
260:
250:
139:, and
79:Fields
538:(PDF)
501:(PDF)
418:arXiv
389:arXiv
321:arXiv
284:arXiv
258:S2CID
230:arXiv
196:ICALP
525:ISBN
248:ISBN
517:doi
480:doi
443:doi
399:doi
362:doi
331:doi
294:doi
240:doi
585::
533:.
523:.
507:.
476:77
474:.
470:.
397:.
387:.
383:.
358:22
356:.
352:.
329:.
315:.
292:.
278:.
256:,
246:,
238:,
198:.
179:,
143:.
135:,
131:,
64:,
60:,
56:,
42:,
547:.
519::
488:.
482::
451:.
445::
426:.
420::
405:.
401::
391::
368:.
364::
337:.
333::
323::
300:.
296::
286::
242::
232::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.