Omid
Etesami
I
am an associate professor at the Institute for
Research in Fundamental Sciences (IPM), in the Combinatorics and Computing group.
I
studied as an undergraduate at Sharif
University of Technology, got PhD in Computer Science at University of California at Berkeley at the
CS Theory group under the
supervision of Luca Trevisan, and then was a post-doc at EPFL under the supervision of Amin Shokrollahi.
I
am interested in the theory of computation and its interplay with randomness,
probability theory, and information theory.
Publications
Computational
Concentration of Measure: Optimal Bounds, Reductions, and More, with Mohammad Mahmoody, Saeed Mahloujifar, SODA
2020
On
the [1,k]-domination Number of Graphs, with Pouyeh Sharifani, Narges Ghareghani, Michel Habib, Mohammadreza
Houshmand, Reza Naserasr, Theoretical
Computer Science 2019
Convex
Ramsey Matrices and Non-amenability of Automorphism
Groups of Generic Structures, with Zaniar Ghadernezhad, Manuscript
Complete Classification of Generalized Santha-Vazirani Sources, with Salman Beigi, Andrej Bogdanov, Siyao Guo, RANDOM 2018
Deterministic Randomness Extraction from Generalized and
Distributed Santha-Vazirani Sources, with Salman Beigi, Amin Gohari, SIAM Journal
on Computing 2017
The Value of Help Bits in Randomized and Average-case
Complexity, with Salman Beigi, Amin Gohari, Computational Complexity 2016
Maximal Rank Correlation, with Amin
Gohari, IEEE Communication Letters 2016
Deterministic
Randomness Extraction from Generalized and Distributed Santha-Vazirani
Sources with Salman Beigi, Amin Gohari,
International Colloquium on Automata, Languages, and Programming (ICALP) 2015
The
Value of Information-Theoretic Content of Help Bits for Computation, with Salman
Beigi, Amin Gohari,
Workshop on Communication and Information Theory (IWCIT) 2015
On the One-way Function Candidate
Proposed by Goldreich
with James Cook, Rachel Miller, Luca Trevisan, ACM
Transactions on Computation Theory 2014 (selected as a Best of 2014 article
by ACM Computing Reviews)
(The above journal version
extends the results and corrects a bug in the conference version and the part of my thesis concerning it.)
Irregular Product Codes with Masoud Alipour, Ghid Maatouk, Amin Shokrollahi, Information Theory Workshop (ITW) 2012
Pseudorandomness against Depth-2 Circuits and Analysis
of Goldreich’s Candidate One-Way Function, PhD
thesis, University of California at Berkeley 2010
Improved Pseudorandom Generators for Depth-2
Circuits with Anindya De, Luca Trevisan, Madhur Tulsiani, International Workshop on Randomization and
Computation (RANDOM) 2010
Goldreich’s One-Way Function Candidate and Myopic
Backtracking Algorithms, with James Cook, Rachel Miller, Luca Trevisan, Theory of Cryptography Conference (TCC) 2009
Mafia: A Theoretical Study of Players and Coalition in a
Partial Information Environment with Mark Braverman,
Elchanan Mossel, Annals of
Applied Probability 2008
Dynamics of Bid Optimization in Online Advertisement Auctions
with Christian Borgs, Jennifer Chayes, Nicole Immorlica, Kamal Jain, Mohammad Mahdian,
International World Wide Web (WWW) Conference 2007
On Rainbow Cycles in Edge Colored Complete Graphs with
Saeed Akbari, Hamid Mahini, Mohammad Mahmoody, Australian Journal of Combinatorics 2007
Raptor Codes on Binary Memoryless Symmetric Channels with
Amin Shokrollahi, IEEE Transactions on Information
Theory 2006
Latin Transversal in Long Rectangular Arrays with
Saeed Akbari, Hamid Mahini, Ali Sharifi,
Discrete Mathematics 2006
Raptor
Codes on Symmetric Channels, with Mehdi Molkaraie,
Amin Shokrollahi, International Symposium on
Information Theory (ISIT) 2004
Relations between Belief Propagation on Erasure and Symmetric
Channels, International Symposium on Information Theory (ISIT) 2004
Lecture Notes
These are a short set of lecture notes concerning
Discrete Probability for Analysis of Algorithms in Persian:
Lecture 1 Lecture 2 Lecture 3 Lecture 4 Lecture 5 Lecture
6