31:
1065:
1070:
910:
283:
271:
1095:
1090:
657:
Carmosino, Marco L.; Impagliazzo, Russell; Kabanets, Valentine; Kolokolova, Antonina (2015). Garg, Naveen; Jansen, Klaus; Rao, Anup; Rolim, José D. P. (eds.).
1075:
1060:
684:
612:
265:
117:
30:
137:
48:
721:
478:
277:
896:
217:
903:
786:
Lokshtanov, Daniel; Marx, Dániel; Saurabh, Saket (October 2011). "Lower Bounds based on the
Exponential Time Hypothesis".
157:
1085:
857:
199:
cannot be solved in subexponential time in the number of variables, This hypothesis is used to deduce lower bounds on
192:
883:
814:
Hardness of Easy
Problems: Basing Hardness on Popular Conjectures such as the Strong Exponential Time Hypothesis
252:
Understanding which world we live in is still a key motivating question in complexity theory and cryptography.
121:
502:
663:
Approximation, Randomization, and
Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2015)
242:
1080:
791:
179:
796:
636:
Impagliazzo, Russell (2003-04-28). "Hardness as randomness: a survey of universal derandomization".
416:
970:
221:
133:
44:
941:
727:
637:
618:
565:
168:
812:
768:
717:
680:
608:
557:
518:
474:
439:
821:
758:
709:
670:
600:
549:
510:
466:
431:
235:
204:
161:
86:
1024:
949:
675:
501:
Beame, Paul; Impagliazzo, Russell; KrajĂÄŤek, Jan; Pitassi, Toniann; Pudlák, Pavel (1996).
360:
144:. He joined the faculty of UCSD in 1989, having been a postdoc there from 1989 to 1991.
820:. 10th International Symposium on Parameterized and Exact Computation. pp. 17–29.
391:
597:
Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97
1054:
953:
465:. Proceedings of IEEE 36th Annual Foundations of Computer Science. pp. 538–545.
175:
658:
622:
569:
962:
919:
731:
842:
985:
966:
826:
669:. Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik: 645–658.
141:
91:
701:
945:
599:. El Paso, Texas, USA: Association for Computing Machinery. pp. 220–229.
553:
458:
435:
772:
561:
522:
514:
470:
443:
415:
HĂ…stad, Johan; Impagliazzo, Russell; Levin, Leonid A.; Luby, Michael (1999).
1004:
1000:
538:"Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds"
537:
307:
200:
185:
his work on connections between computational hardness and de-randomization,
763:
746:
604:
76:
Pseudo-random
Generators for Probablistic Algorithms and for Cryptography
888:
878:
713:
584:
659:"Tighter Connections between Derandomization and Circuit Lower Bounds"
286:
for work on "heuristics, proof complexity, and algorithmic techniques"
35:
Russell
Impagliazzo at the DIMACS Workshop on Cryptography, July 2016.
1032:
Cygan, Nederlof, Pilipczuk, Pilipczuk, van Rooij, Onufry
Wojtaszczyk
331:
188:
and his work on the construction of multi-source seedless extractors.
105:
70:
503:"Lower Bounds on Hilbert's Nullstellensatz and Propositional Proofs"
361:"Russell Impagliazzo | Simons Institute for the Theory of Computing"
642:
234:
Pessiland: there are NP problems that are hard on average, but no
231:
Heuristica: P is not NP, but NP problems are tractable on average;
196:
174:
his proof of the exponential size lower bound for constant-depth
892:
463:
Proceedings of IEEE 36th Annual
Foundations of Computer Science
706:
45th Annual IEEE Symposium on
Foundations of Computer Science
665:. Leibniz International Proceedings in Informatics (LIPIcs).
216:
Impagliazzo is well-known for proposing the "five worlds" of
1038:
Bodlaender, Fomin, Lokshtanov, Penninkx, Saurabh, Thilikos
152:
Impagliazzo's contributions to complexity theory include:
308:"Russell Impagliazzo - The Mathematics Genealogy Project"
536:
Kabanets, Valentine; Impagliazzo, Russell (2004-12-01).
745:
Impagliazzo, Russell; Paturi, Ramamohan (2001-03-01).
702:"Extracting Randomness Using Few Independent Sources"
220:, reflecting possible states of the world around the
459:"Hard-core distributions for somewhat hard problems"
417:"A Pseudorandom Generator from any One-way Function"
583:Impagliazzo, Russell; Wigderson, Avi (1997-05-04).
101:
85:
69:
54:
40:
21:
884:UCSD Jacobs, School of Engineering faculty profile
700:Barak, B.; Impagliazzo, R.; Wigderson, A. (2004).
392:"Faculty Profile | Jacobs School of Engineering"
260:Impagliazzo has received the following awards:
507:Proceedings of the London Mathematical Society
272:Society for Industrial and Applied Mathematics
132:Impagliazzo received a BA in mathematics from
904:
858:"Which Computational Universe Do We Live In?"
8:
843:"A Personal View of Average-Case Complexity"
248:Cryptomania: public-key cryptography exists.
1066:University of California, San Diego faculty
911:
897:
889:
116:is a professor of computer science at the
58:Results in computational complexity theory
29:
18:
1071:University of California, Berkeley alumni
825:
795:
762:
674:
641:
1012:Marx, Chen, Liu, Lu, O’Sullivan, Razgon
355:
353:
351:
241:Minicrypt: one-way functions exist, but
1018:Calude, Jain, Khoussainov, Li, Stephan
841:Impagliazzo, Russell (April 17, 1995).
751:Journal of Computer and System Sciences
296:
270:2003 Outstanding Paper Award from the
676:10.4230/LIPIcs.APPROX-RANDOM.2015.645
7:
1096:20th-century American mathematicians
1091:21st-century American mathematicians
386:
384:
382:
380:
302:
300:
856:Klarreich, Erica (April 18, 2022).
266:Computational Complexity Conference
136:. He obtained a doctorate from the
118:University of California, San Diego
138:University of California, Berkeley
106:https://cseweb.ucsd.edu//~russell/
49:University of California, Berkeley
14:
278:Symposium on Theory of Computing
212:Five worlds of complexity theory
218:computational complexity theory
811:Williams, Virginia V. (2015).
593:requires exponential circuits"
1:
457:Impagliazzo, Russell (1995).
276:2003 Best Paper Award at the
158:pseudorandom number generator
1076:University of Toronto people
1061:American computer scientists
747:"On the Complexity of k-SAT"
827:10.4230/LIPIcs.IPEC.2015.17
193:exponential time hypothesis
16:American computer scientist
1112:
264:Best Paper Award from the
114:Russell Graham Impagliazzo
23:Russell Graham Impagliazzo
935:, Kabanets, Paturi, Zane
927:
554:10.1007/s00037-004-0182-6
436:10.1137/S0097539793244708
424:SIAM Journal on Computing
140:in 1992. His advisor was
97:
62:
28:
542:Computational Complexity
471:10.1109/SFCS.1995.492584
122:computational complexity
332:"Russell Impagliazzo's"
243:public-key cryptography
764:10.1006/jcss.2000.1727
515:10.1112/plms/s3-73.1.1
284:2004 Guggenheim fellow
156:the construction of a
788:Bulletin of the EATCS
605:10.1145/258533.258590
396:jacobsschool.ucsd.edu
228:Algorithmica: P = NP;
171:via "hard core sets",
988:, Grandoni, Kratsch
714:10.1109/FOCS.2004.29
708:. pp. 384–393.
180:pigeonhole principle
1086:Simons Investigator
994:Kratsch, Wahlström
879:Russell Impagliazzo
509:. s3-73 (1): 1–26.
365:simons.berkeley.edu
222:P versus NP problem
134:Wesleyan University
45:Wesleyan University
120:, specializing in
1048:
1047:
1041:
1035:
1029:
1021:
1015:
1009:
997:
991:
982:
976:
959:
938:
686:978-3-939897-89-7
614:978-0-89791-888-6
312:mathgenealogy.org
236:one-way functions
111:
110:
64:Scientific career
1103:
1039:
1033:
1027:
1019:
1013:
1007:
995:
989:
980:
974:
957:
936:
913:
906:
899:
890:
866:
865:
853:
847:
846:
838:
832:
831:
829:
819:
808:
802:
801:
799:
783:
777:
776:
766:
742:
736:
735:
697:
691:
690:
678:
654:
648:
647:
645:
633:
627:
626:
580:
574:
573:
533:
527:
526:
498:
492:
491:
489:
487:
454:
448:
447:
430:(4): 1364–1396.
421:
412:
406:
405:
403:
402:
388:
375:
374:
372:
371:
357:
346:
345:
343:
342:
328:
322:
321:
319:
318:
304:
205:computer science
162:one-way function
87:Doctoral advisor
81:
33:
19:
1111:
1110:
1106:
1105:
1104:
1102:
1101:
1100:
1051:
1050:
1049:
1044:
923:
917:
875:
870:
869:
855:
854:
850:
840:
839:
835:
817:
810:
809:
805:
797:10.1.1.942.6217
785:
784:
780:
744:
743:
739:
724:
699:
698:
694:
687:
656:
655:
651:
635:
634:
630:
615:
582:
581:
577:
535:
534:
530:
500:
499:
495:
485:
483:
481:
456:
455:
451:
419:
414:
413:
409:
400:
398:
390:
389:
378:
369:
367:
359:
358:
349:
340:
338:
336:cseweb.ucsd.edu
330:
329:
325:
316:
314:
306:
305:
298:
293:
258:
214:
169:Yao's XOR lemma
150:
130:
79:
41:Alma mater
36:
24:
17:
12:
11:
5:
1109:
1107:
1099:
1098:
1093:
1088:
1083:
1078:
1073:
1068:
1063:
1053:
1052:
1046:
1045:
1043:
1042:
1036:
1030:
1022:
1016:
1010:
998:
992:
983:
977:
960:
939:
928:
925:
924:
918:
916:
915:
908:
901:
893:
887:
886:
881:
874:
873:External links
871:
868:
867:
848:
833:
803:
778:
757:(2): 367–375.
737:
722:
692:
685:
649:
628:
613:
575:
528:
493:
479:
449:
407:
376:
347:
323:
295:
294:
292:
289:
288:
287:
280:
274:
268:
257:
254:
250:
249:
246:
239:
232:
229:
213:
210:
209:
208:
189:
186:
183:
178:proofs of the
172:
165:
149:
146:
129:
126:
109:
108:
103:
99:
98:
95:
94:
89:
83:
82:
73:
67:
66:
60:
59:
56:
55:Known for
52:
51:
42:
38:
37:
34:
26:
25:
22:
15:
13:
10:
9:
6:
4:
3:
2:
1108:
1097:
1094:
1092:
1089:
1087:
1084:
1082:
1081:Living people
1079:
1077:
1074:
1072:
1069:
1067:
1064:
1062:
1059:
1058:
1056:
1037:
1031:
1026:
1023:
1017:
1011:
1006:
1002:
999:
993:
987:
984:
978:
972:
968:
964:
961:
955:
951:
947:
943:
940:
934:
930:
929:
926:
921:
914:
909:
907:
902:
900:
895:
894:
891:
885:
882:
880:
877:
876:
872:
863:
859:
852:
849:
844:
837:
834:
828:
823:
816:
815:
807:
804:
798:
793:
789:
782:
779:
774:
770:
765:
760:
756:
752:
748:
741:
738:
733:
729:
725:
723:0-7695-2228-9
719:
715:
711:
707:
703:
696:
693:
688:
682:
677:
672:
668:
664:
660:
653:
650:
644:
639:
632:
629:
624:
620:
616:
610:
606:
602:
598:
594:
592:
588:
579:
576:
571:
567:
563:
559:
555:
551:
547:
543:
539:
532:
529:
524:
520:
516:
512:
508:
504:
497:
494:
482:
480:0-8186-7183-1
476:
472:
468:
464:
460:
453:
450:
445:
441:
437:
433:
429:
425:
418:
411:
408:
397:
393:
387:
385:
383:
381:
377:
366:
362:
356:
354:
352:
348:
337:
333:
327:
324:
313:
309:
303:
301:
297:
290:
285:
281:
279:
275:
273:
269:
267:
263:
262:
261:
255:
253:
247:
244:
240:
237:
233:
230:
227:
226:
225:
223:
219:
211:
206:
202:
198:
194:
190:
187:
184:
181:
177:
173:
170:
167:his proof of
166:
163:
159:
155:
154:
153:
148:Contributions
147:
145:
143:
139:
135:
127:
125:
123:
119:
115:
107:
104:
100:
96:
93:
90:
88:
84:
77:
74:
72:
68:
65:
61:
57:
53:
50:
46:
43:
39:
32:
27:
20:
956:, Santhanam
952:, Hermelin,
932:
920:Nerode Prize
861:
851:
836:
813:
806:
787:
781:
754:
750:
740:
705:
695:
666:
662:
652:
631:
596:
590:
586:
578:
545:
541:
531:
506:
496:
484:. Retrieved
462:
452:
427:
423:
410:
399:. Retrieved
395:
368:. Retrieved
364:
339:. Retrieved
335:
326:
315:. Retrieved
311:
259:
251:
215:
191:stating the
151:
131:
113:
112:
75:
63:
1003:, Yuster,
973:, Thilikos
933:Impagliazzo
548:(1): 1–46.
142:Manuel Blum
92:Manuel Blum
1055:Categories
979:Björklund
971:Hajiaghayi
942:Bodlaender
643:cs/0304040
401:2021-08-30
370:2021-08-30
341:2021-08-30
317:2021-08-30
291:References
201:algorithms
1025:Courcelle
931:Calabro,
922:laureates
792:CiteSeerX
790:: 41–71.
773:0022-0000
562:1420-8954
523:1460-244X
486:30 August
444:0097-5397
245:does not;
160:from any
128:Education
623:18921599
570:12451799
282:named a
124:theory.
963:Demaine
954:Fortnow
950:Fellows
732:7063583
587:P = BPP
176:Hilbert
102:Website
1040:(2024)
1034:(2023)
1028:(2022)
1020:(2021)
1014:(2020)
1008:(2019)
996:(2018)
990:(2017)
981:(2016)
975:(2015)
958:(2014)
946:Downey
937:(2013)
862:Quanta
794:
771:
730:
720:
683:
621:
611:
568:
560:
521:
477:
442:
256:Awards
80:(1992)
78:
71:Thesis
1005:Zwick
986:Fomin
967:Fomin
818:(PDF)
728:S2CID
638:arXiv
619:S2CID
566:S2CID
420:(PDF)
197:3-SAT
195:that
1001:Alon
769:ISSN
718:ISBN
681:ISBN
609:ISBN
558:ISSN
519:ISSN
488:2021
475:ISBN
440:ISSN
822:doi
759:doi
710:doi
671:doi
601:doi
589:if
550:doi
511:doi
467:doi
432:doi
203:in
1057::
969:,
965:,
948:,
944:,
860:.
767:.
755:62
753:.
749:.
726:.
716:.
704:.
679:.
667:40
661:.
617:.
607:.
595:.
564:.
556:.
546:13
544:.
540:.
517:.
505:.
473:.
461:.
438:.
428:28
426:.
422:.
394:.
379:^
363:.
350:^
334:.
310:.
299:^
224:.
47:;
912:e
905:t
898:v
864:.
845:.
830:.
824::
800:.
775:.
761::
734:.
712::
689:.
673::
646:.
640::
625:.
603::
591:E
585:"
572:.
552::
525:.
513::
490:.
469::
446:.
434::
404:.
373:.
344:.
320:.
238:;
207:.
182:,
164:,
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.
