Michael Saks (matematiker)

Michael Ezra Saks är en amerikansk matematiker. Han är för närvarande institutionsordförande för Mathematics Department vid Rutgers University (2017–) och var från 2006 till 2010 chef för Mathematics Graduate Program vid Rutgers University . Saks fick sin Ph.D. från Massachusetts Institute of Technology 1980 efter att ha avslutat sin avhandling med titeln Duality Properties of Finite Set Systems under hans rådgivare Daniel J. Kleitman .

En lista över hans publikationer och samarbeten finns på DBLP .

2016 blev han Fellow i Association for Computing Machinery .

Forskning

Saks forskning inom beräkningskomplexitetsteori , kombinatorik och grafteori har bidragit till studiet av nedre gränser för ordningsteori , randomiserad beräkning och avvägning mellan rum och tid .

1984 visade Saks och Jeff Kahn att det finns en snäv informationsteoretisk nedre gräns för sortering under partiellt ordnad information upp till en multiplikativ konstant.

I [1] bevisades den första superlinjära nedre gränsen för det brusiga sändningsproblemet. I en bullrig sändningsmodell tilldelas $n+1$ processorer ${\displaystyle P_{0},P_{1},\ldots ,P_{n}} en$ lokal ingångsbit $x_{i}$ . Varje processor kan utföra en brusig sändning till alla andra processorer där de mottagna bitarna kan vändas oberoende med en fast sannolikhet. Problemet är för processor $P_{0}$ att bestämma $f(x_{1},x_{2},\ldots ,x_{n })$ för någon funktion $f$ . Saks et al. visade att ett befintligt protokoll från Gallager verkligen var optimalt genom en reduktion från ett generaliserat bullrigt beslutsträd och gav en $\Omega (n\log(n))$ nedre gräns för djupet av trädet som lär sig input.

År 2003 publicerade P. Beame, Saks, X. Sun och E. Vee den första avvägningen mellan tid och rumsgräns för randomiserad beräkning av beslutsproblem.

Positioner

Saks har befattningar i följande tidskriftsredaktioner:

• SIAM Journal on Computing , biträdande redaktör
• Combinatorica , ledamot i redaktionen
• Journal of Graph Theory , Ledamot i redaktionen
• Diskret tillämpad matematik , ledamot i redaktionen

Utvalda publikationer

•    Borodin, Allan; Linial, Nathan; Saks, Michael E. (1992-10-01). "En optimal onlinealgoritm för metriska uppgiftssystem" . Journal of the ACM . 39 (4): 745–763. doi : 10.1145/146585.146588 . ISSN 0004-5411 . S2CID 18783826 .
•    Fredman, M.; Saks, M. (1989-02-01). "Cellprobens komplexitet av dynamiska datastrukturer" . Proceedings of the Twenty-first annual ACM Symposium on Theory of Computing . STOC '89. New York, NY, USA: Association for Computing Machinery: 345–354. doi : 10.1145/73007.73040 . ISBN 978-0-89791-307-2 . S2CID 13470414 .
•   Paturi, Ramamohan; Pudlák, Pavel; Saks, Michael E.; Zane, Francis (2005-05-01). "En förbättrad exponentiell tidsalgoritm för k-SAT" . Journal of the ACM . 52 (3): 337–364. doi : 10.1145/1066100.1066101 . ISSN 0004-5411 .
•   Goldberg, Andrew V.; Hartline, Jason D.; Karlin, Anna R.; Saks, Michael; Wright, Andrew (2006-05-01). "Konkurrenskraftiga auktioner" . Spel och ekonomiskt beteende . Mini Special Issue: Electronic Market Design. 55 (2): 242–269. doi : 10.1016/j.geb.2006.02.003 . ISSN 0899-8256 .
•   Saks, Michael; Zaharoglou, Fotios (2000-01-01). "Väntefritt k-setavtal är omöjligt: ​​topologin för offentlig kunskap" . SIAM Journal on Computing . 29 (5): 1449–1483. doi : 10.1137/S0097539796307698 . ISSN 0097-5397 .
•    Saks, Michael; Wigderson, Avi (oktober 1986). "Probabilistiska booleska beslutsträd och komplexiteten i att utvärdera spelträd" . 27th Annual Symposium on Foundations of Computer Science (SFCS 1986) : 29–38. doi : 10.1109/SFCS.1986.44 . ISBN 0-8186-0740-8 . S2CID 6130392 .
•    Saks, Michael; Yu, Lan (2005-06-05). "Svag monotoni räcker för sanning på konvexa domäner" . Proceedings of the 6th ACM Conference on Electronic Commerce . EM '05. New York, NY, USA: Association for Computing Machinery: 286–293. doi : 10.1145/1064009.1064040 . ISBN 978-1-59593-049-1 . S2CID 2135397 .

externa länkar

• Michael Ezra Saks vid Mathematics Genealogy Project