719:
772:
72:, with applications in diverse fields such as matching algorithms, geometric algorithms, mathematical programming, statistics, physics-inspired applications, and dynamical systems. This work has been highly influential in theoretical computer science and was recognised with the
76:
in 1996. A refinement of these methods led to a fully polynomial-time randomised approximation algorithm for computing the permanent, for which Jerrum and his co-authors received the
853:
269:
838:
809:
756:
868:
848:
262:
843:
696:
858:
255:
863:
233:
158:
50:
802:
749:
637:
609:
173:
143:
442:
97:
795:
742:
325:
65:
422:
69:
38:
833:
549:
27:
400:
533:
215:
670:
828:
700:
686:
718:
575:
660:
589:
484:
293:
545:
450:
335:
89:
57:
779:
726:
613:
470:
392:
297:
122:
46:
37:
in computer science 'On the complexity of evaluating multivariate polynomials' in 1981 from
692:
599:
553:
498:
438:
432:
309:
242:
177:
88:
Jerrum does not own a television, but has confessed to colleagues that he enjoys watching
77:
664:
539:
315:
189:
623:
603:
494:
404:
374:
351:
341:
278:
73:
42:
210:
822:
631:
619:
557:
529:
512:
504:
488:
464:
416:
384:
378:
321:
301:
23:
627:
585:
579:
508:
478:
474:
460:
408:
396:
305:
238:
61:
100:. He does admit, however, that only the first season of COPS is good television.
682:
428:
412:
388:
345:
170:
674:
643:
565:
561:
446:
357:
593:
571:
456:
139:
209:
Frieze, A., Jerrum, M., Molloy M., Robinson, R., & Wormald, N. (1996).
771:
247:
678:
126:
229:
154:
34:
778:
This article on a computer specialist of the United
Kingdom is a
211:
Generating and counting
Hamilton cycles in random regular graphs
251:
93:
119:
On the complexity of evaluating multivariate polynomials
783:
730:
653:
522:
367:
286:
60:, Jerrum investigated the mixing behaviour of
803:
750:
263:
8:
854:Academics of Queen Mary University of London
725:This article about a British scientist is a
810:
796:
757:
743:
270:
256:
248:
109:
196:, December 2006, volume 53, number 11.
839:Alumni of the University of Edinburgh
7:
768:
766:
715:
713:
782:. You can help Knowledge (XXG) by
729:. You can help Knowledge (XXG) by
68:for counting problems such as the
14:
869:British computer specialist stubs
770:
717:
234:Queen Mary, University of London
159:Queen Mary, University of London
51:Queen Mary, University of London
849:Theoretical computer scientists
16:Theoretical computer scientist
1:
190:2006 Fulkerson Prize citation
144:Mathematics Genealogy Project
844:British computer scientists
885:
765:
712:
41:under the supervision of
241:publications indexed by
176:12 February 2017 at the
66:approximation algorithms
864:British scientist stubs
70:computing the permanent
39:University of Edinburgh
26:computer scientist and
28:computational theorist
859:Gödel Prize laureates
230:Mark Jerrum home page
216:Journal of Algorithms
117:Mark, Jerrum (1981).
45:. He is professor of
171:Gödel Prize citation
33:Jerrum received his
204:Select publications
20:Mark Richard Jerrum
243:Microsoft Academic
194:Notices of the AMS
791:
790:
738:
737:
710:
709:
58:Alistair Sinclair
56:With his student
22:(born 1955) is a
876:
812:
805:
798:
774:
767:
759:
752:
745:
721:
714:
272:
265:
258:
249:
197:
187:
181:
168:
162:
152:
146:
137:
131:
130:
114:
47:pure mathematics
884:
883:
879:
878:
877:
875:
874:
873:
819:
818:
817:
816:
764:
763:
711:
706:
649:
518:
363:
282:
276:
226:
206:
201:
200:
188:
184:
178:Wayback Machine
169:
165:
153:
149:
138:
134:
116:
115:
111:
106:
96:and previously
86:
78:Fulkerson Prize
17:
12:
11:
5:
882:
880:
872:
871:
866:
861:
856:
851:
846:
841:
836:
831:
821:
820:
815:
814:
807:
800:
792:
789:
788:
775:
762:
761:
754:
747:
739:
736:
735:
722:
708:
707:
705:
704:
701:Vaikuntanathan
690:
668:
657:
655:
651:
650:
648:
647:
641:
635:
617:
607:
597:
583:
569:
543:
537:
526:
524:
520:
519:
517:
516:
502:
492:
482:
468:
454:
436:
426:
420:
382:
371:
369:
365:
364:
362:
361:
355:
349:
339:
329:
319:
313:
290:
288:
284:
283:
277:
275:
274:
267:
260:
252:
246:
245:
236:
225:
224:External links
222:
221:
220:
219:, 21, 176–198.
205:
202:
199:
198:
182:
163:
155:Personnel page
147:
132:
108:
107:
105:
102:
85:
82:
43:Leslie Valiant
15:
13:
10:
9:
6:
4:
3:
2:
881:
870:
867:
865:
862:
860:
857:
855:
852:
850:
847:
845:
842:
840:
837:
835:
834:Living people
832:
830:
827:
826:
824:
813:
808:
806:
801:
799:
794:
793:
787:
785:
781:
776:
773:
769:
760:
755:
753:
748:
746:
741:
740:
734:
732:
728:
723:
720:
716:
702:
698:
694:
691:
688:
684:
680:
676:
672:
669:
666:
662:
659:
658:
656:
652:
645:
642:
639:
636:
633:
629:
625:
621:
618:
615:
611:
608:
605:
601:
598:
595:
591:
587:
584:
581:
577:
573:
570:
567:
563:
559:
555:
551:
550:Papadimitriou
547:
544:
541:
538:
535:
531:
528:
527:
525:
521:
514:
510:
506:
503:
500:
496:
493:
490:
486:
483:
480:
476:
472:
469:
466:
462:
458:
455:
452:
448:
444:
440:
437:
434:
430:
427:
424:
421:
418:
414:
410:
406:
402:
398:
394:
390:
386:
383:
380:
376:
373:
372:
370:
366:
359:
356:
353:
350:
347:
343:
340:
337:
333:
330:
327:
323:
320:
317:
314:
311:
307:
303:
299:
295:
292:
291:
289:
285:
280:
273:
268:
266:
261:
259:
254:
253:
250:
244:
240:
237:
235:
231:
228:
227:
223:
218:
217:
212:
208:
207:
203:
195:
191:
186:
183:
179:
175:
172:
167:
164:
160:
156:
151:
148:
145:
141:
136:
133:
128:
124:
120:
113:
110:
103:
101:
99:
95:
91:
84:Personal Life
83:
81:
79:
75:
71:
67:
64:to construct
63:
62:Markov chains
59:
54:
52:
48:
44:
40:
36:
31:
29:
25:
21:
784:expanding it
777:
731:expanding it
724:
331:
326:Szelepcsényi
214:
193:
185:
166:
150:
135:
118:
112:
87:
55:
32:
19:
18:
829:1955 births
554:Roughgarden
546:Koutsoupias
423:SĂ©nizergues
279:Gödel Prize
239:Mark Jerrum
140:Mark Jerrum
74:Gödel Prize
823:Categories
451:Zaharoglou
393:Goldwasser
298:Goldwasser
127:1842/12296
121:(Thesis).
104:References
693:Brakerski
665:G. Tardos
558:É. Tardos
513:Wigderson
281:laureates
80:in 2006.
687:Richerby
624:McSherry
600:Spielman
576:Franklin
534:Mitchell
505:Reingold
499:Spielman
485:Razborov
433:Schapire
336:Sinclair
322:Immerman
174:Archived
671:Bulatov
614:O'Hearn
610:Brookes
471:Agrawal
465:Szegedy
439:Herlihy
417:Szegedy
405:Motwani
342:Halpern
310:Rackoff
180:, 1996.
142:at the
24:British
703:(2022)
697:Gentry
689:(2021)
667:(2020)
646:(2019)
640:(2018)
634:(2017)
628:Nissim
616:(2016)
606:(2015)
596:(2014)
582:(2013)
568:(2012)
542:(2011)
540:HĂĄstad
536:(2010)
515:(2009)
509:Vadhan
501:(2008)
491:(2007)
489:Rudich
481:(2006)
479:Saxena
467:(2005)
461:Matias
453:(2004)
447:Shavit
435:(2003)
429:Freund
425:(2002)
419:(2001)
401:Lovász
381:(2000)
379:Wolper
360:(1999)
354:(1998)
348:(1997)
338:(1996)
332:Jerrum
328:(1995)
318:(1994)
316:HĂĄstad
312:(1993)
302:Micali
661:Moser
654:2020s
644:Dinur
638:Regev
632:Smith
620:Dwork
590:Lotem
586:Fagin
572:Boneh
566:Ronen
562:Nisan
530:Arora
523:2010s
475:Kayal
413:Sudan
409:Safra
389:Feige
385:Arora
375:Vardi
368:2000s
346:Moses
306:Moran
294:Babai
287:1990s
35:Ph.D.
780:stub
727:stub
683:Dyer
679:Chen
604:Teng
594:Naor
580:Joux
495:Teng
457:Alon
443:Saks
397:Lund
358:Shor
352:Toda
90:COPS
675:Cai
232:at
157:,
123:hdl
98:WCW
94:WWE
49:at
825::
699:/
695:/
685:/
681:/
677:/
673:/
663:/
630:/
626:/
622:/
612:/
602:/
592:/
588:/
578:/
574:/
564:/
560:/
556:/
552:/
548:/
532:/
511:/
507:/
497:/
487:/
477:/
473:/
463:/
459:/
449:/
445:/
441:/
431:/
415:/
411:/
407:/
403:/
399:/
395:/
391:/
387:/
377:/
344:/
334:/
324:/
308:/
304:/
300:/
296:/
213:.
192:,
92:,
53:.
30:.
811:e
804:t
797:v
786:.
758:e
751:t
744:v
733:.
271:e
264:t
257:v
161:.
129:.
125::
Text is available under the Creative Commons Attribution-ShareAlike License. Additional terms may apply.