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