Michael Saks (mathematician)

Michael Saks (mathematician)

Michael Ezra Saks is a professor and was (2006–2010) director of the Mathematics Graduate Program at Rutgers University. Saks received his Ph.D from the Massachusetts Institute of Technology in 1980 after completing his dissertation entitled Duality Properties of Finite Set Systems [1] under his advisor Daniel J. Kleitman.

A list of his publications and collaborations may be found at.[2]

Contents

Research

Saks research in computational complexity theory, combinatorics, and graph theory has contributed to the study of lower bounds in order theory, randomized computation, and space-time tradeoff.

In,[3] it was shown there exist a tight information-theoretical lower bound for sorting under partially ordered information up to a multiplicative constant.

In,[4] the first super-linear lower bound for the noisy broadcast problem was proved. In a noisy broadcast model, n + 1 processors P0,P1,...,Pn are assigned a local input bit xi. Each processor may perform a noisy broadcast to all other processors where the received bits may be independently flipped with a fixed probability. The problem is for processor P0 to determined f(x1,x2,...xn) for some function f. Saks et al. showed that an existing protocol by Gallager [5] was indeed optimal by a reduction from a generalized noisy decision tree and produced a Ω(nlog(n)) lower bound on the depth of the tree that learns the input.

In,[6] the first time-space lower bound trade-off for randomized computation of decision problems was proved.

Other Positions

Saks holds positions in the following journal editorial boards:

  • SIAM J. on Computing, Associate Editor
  • Combinatorica, Editorial Board member
  • Journal of Graph Theory, Editorial Board member
  • Discrete Applied Mathematics, Editorial Board member

References

External links


Wikimedia Foundation. 2010.

Нужна помощь с курсовой?

Look at other dictionaries:

  • Michael Saks — may refer to: Michael J. Saks, professor of law at the Sandra Day O Connor College of Law at Arizona State University Michael Saks (mathematician), professor at Rutgers University This disambiguation page lists articles associated with the same… …   Wikipedia

  • Prix Gödel — Nommé en l honneur du logicien Kurt Gödel, le prix Gödel a été créé en 1992 par l European Association for Theoretical Computer Science (EATCS), l Association for Computing Machinery (ACM) et le groupe de l ACM sur l algorithmique et la théorie… …   Wikipédia en Français

  • Madhu Sudan — Naissance 12 septembre 1966 Chennai (Indie) Domicile États Unis Champs Informatique théorique Institution Microsoft Research, Massachusetts Institute of Technology Diplômé de …   Wikipédia en Français

  • Daniel Spielman — Naissance mars 1970 Domicile États Unis Nationalité …   Wikipédia en Français

  • Géraud Sénizergues — est professeur d informatique à l Université de Bordeaux et membre du Laboratoire bordelais de recherche en informatique. Récipiendaire du Prix Gödel en 2002 pour avoir démontré la décidabilité de l égalité des langages reconnus par des automates …   Wikipédia en Français

  • Johan Håstad — Johan Håstad, né en 1960, est un informaticien théorique suédois connu particulièrement pour son travail sur la complexité algorithmique. Il a reçu le Prix Gödel en 1994 et 2011 et le Doctoral Dissertation Award de l Association for Computing… …   Wikipédia en Français

  • László Lovász — (9 mars 1948, à Budapest ) est un mathématicien connu pour ses travaux en combinatoire et dans la théorie des graphes. Sommaire …   Wikipédia en Français

  • Manindra Agrawal — (hindi : मणीन्द्र अग्रवाल) (20 mai 1966 à Allâhâbâd ) est un mathématicien indien et professeur à l Institut indien de technologie de Kanpur. C est un des auteurs du test de primalité AKS. Lien externe Page personnelle (en) …   Wikipédia en Français

  • Mario Szegedy — Márió Szegedy (23 octobre 1960 ) est un mathématicien et informaticien hongrois. Il est professeur à l université Rutgers et a obtenu son doctorat de l université de Chicago. Liens externes Page personnelle (en) Publications de Mario …   Wikipédia en Français

  • Peter Shor — Peter Williston Shor, né le 14 août 1959, est un mathématicien américain. Il est connu pour son travail sur le calcul quantique, en particulier pour l algorithme de Shor. Il est professeur au MIT et membre du CSAIL. En 1998, il reçoit le prix… …   Wikipédia en Français

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”