alt text 

Rad Niazadeh (راد نیازاده)

Motwani Postdoctoral Researcher,
Department of Computer Science,
Stanford University,
Address: Gates 484, 353 Serra Mall, Stanford, CA 94305.
Email: rad at cs.stanford.edu.

[J] Journals (published & under-review)

  1. “Optimal Auctions vs. Anonymous Pricing”,
    with Saeed Alaei, Jason Hartline, Yang Yuan, and Manolis Pountourakis,
    to appear in the special issue on selected papers from STOC/FOCS/SODA, Games and Economic Behavior (GEB), 2018.
    [arXiv][link]

  2. “Fast Core Pricing for Rich Advertising Auctions”,
    with Jason Hartline, Mohammad Reza Khani, Nicole Immorlica, and Brendan Lucier,
    revise & resubmit from Operations Research (OR), 2018.
    [arXiv]

  3. “Multi-scale Online Learning and its Applications to Online Auctions”,
    with Sébastien Bubeck, Nikhil Devanur and Zhiyi Huang,
    revise & resubmit from the Journal of Machine Learning Research (JMLR), 2018.
    [arXiv]

  4. “Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization”,
    with Tim Roughgarden and Joshua Wang,
    under-review in the Journal of Machine Learning Research (JMLR).
    [arXiv]

  5. “Bernoulli Factories and Black-Box Reductions in Mechanism Design”,
    with Shaddin Dughmi, Jason Hartline and Bobby Kleinberg,
    under-review in the Journal of the ACM (JACM).
    [arXiv]

  6. “Mechanism Design for Value Maximizers”,
    with Chris Wilkens, Ruggiero Cavallo, and Samuel Taggart,
    under-review in Operations Research (OR).
    [arXiv]

  7. “On The Achievability of Cramer-Rao Bound in Noisy Compressed Sensing”,
    with Massoud Babaie-Zadeh and Christian Jutten,
    IEEE Transactions on Signal Processing, Volume 60, Issue 1,
    [arXiv] [link].

  8. “ISI sparse channel estimation based on SL0 and its application in ML sequence-by-sequence equalization”,
    with Massoud Babaie-Zadeh, Sina Hamidi Ghalehjegh and Christian Jutten,
    Elsevier Journal of Signal Processing, Volume 92, Issue 8,
    [arXiv] [link].

[C] Conferences (in chronological order)

  1. “Optimal Algorithms for Continuous Non-monotone Submodular and DR-Submodular Maximization”,
    with Tim Roughgarden and Joshua Wang,
    in Proc. 32nd Conference on Neural Information Processing Systems (NIPS 2018)
    (among top 30 papers selected for oral presentation out of 4.8k+ submitted papers),
    to be also presented at INFORMS Annual Meeting 2018 in Phoenix (INFORMS 2018),
    [arXiv]

  2. “Hierarchical Clustering with Structural Constraints”,
    with Vaggos Chatziafratis and Moses Charikar,
    in Proc. 35th International Conference on Machine Learning (ICML 2018),
    [arXiv][link].

  3. “Fast Core Pricing for Rich Advertising Auctions”,
    with Jason Hartline, Mohammad Reza Khani, Nicole Immorlica, and Brendan Lucier,
    in Proc. 19th ACM conference on Economics and Computation (EC 2018),
    invited for presentation at INFORMS Annual Meeting 2018 in Phoenix (INFORMS 2018),
    [arXiv][link].

  4. “Bernoulli Factories and Black-Box Reductions in Mechanism Design”,
    with Shaddin Dughmi, Jason Hartline and Bobby Kleinberg,
    in Proc. 49th ACM Symposium on Theory of Computing (STOC 2017),
    also presented at 2017 INFORMS Annual Meeting (INFORMS 2017),
    [arXiv][link].

  5. “Online Auctions and Multi-scale Online Learning”,
    with Sébastien Bubeck, Nikhil Devanur and Zhiyi Huang,
    in Proc. 18th ACM conference on Economics and Computation (EC 2017),
    invited for presentation at INFORMS Annual Meeting 2018 in Phoenix (INFORMS 2018),
    [arXiv] [link].

  6. “Truth and Regret in Online Scheduling”,
    with Nikhil Devanur, Shuchi Chawla, and Janardhan Kulkarni,
    in Proc. 18th ACM conference on Economics and Computation (EC 2017),
    also presented at 2017 INFORMS Annual Meeting (INFORMS 2017),
    [arXiv] [link].

  7. “GSP - The Cinderella of Mechanism Design”,
    with Chris Wilkens and Ruggiero Cavallo,
    in Proc. 26th International World Wide Web Conference (WWW 2017),
    [arXiv] [link].

  8. “Competitive Equilibria for Non-quasilinear Bidders in Combinatorial Auctions”,
    with Chris Wilkens,
    in Proc. 12th Conference on Web and Internet Economics (WINE 2016),
    [arXiv] [link].

  9. “Optimal Auctions vs. Anonymous Pricing”,
    with Saeed Alaei, Jason Hartline, Yang Yuan, and Manolis Pountourakis,
    conference version appeared in Proc. 56th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2015),
    also presented at 5th World Congress of the Game Theory Society (GAMES 2016),
    [arXiv] [link].

  10. “Secretary Problems with Non-Uniform Arrival Order”,
    with Thomas Kesselheim and Bobby Kleinberg,
    in Proc. 47th ACM Symposium on Theory of Computing (STOC 2015),
    invited for presentation at INFORMS International 2016,
    also presented at 1st Highlights of Algorithms (HALG 2016),
    [arXiv] [link].

  11. “Simple and Near-Optimal Mechanisms For Market Intermediation”,
    with Yang Yuan and Bobby Kleinberg,
    in Proc. 10th Conference on Web and Internet Economics (WINE 2014),
    [arXiv] [link].

  12. “A Unified Approach to Online Allocation Algorithms via Randomized Dual Fitting”,
    with Bobby Kleinberg,
    Technical Report (course material for CS 6820 at Cornell),
    [arXiv].

  13. “An Alternating Minimization Algorithm for Sparse Channel Estimation”,
    with Massoud Babaie-Zadeh and Christian Jutten,
    in Proc. of 9th International Conference on Latent Variable Analysis and Signal Separation (LVA-ICA 2010),
    [arXiv] [link].

  14. “Adaptive and Non-Adaptive ISI Sparse Channel Estimation Based on SL0 and Its Application in ML Sequence-by-Sequence Equalization”,
    with Masoud Babaie-Zadeh, Sina Hamidi Ghalehjegh and Christian Jutten,
    in Proc. of 9th International Conference on Latent Variable Analysis and Signal Separation (LVA-ICA 2010),
    [arXiv] [link].

  15. “Implementation and Optimization of Wavelet Modulation in Additive Gaussian Channels”,
    with Sahar Nassirpour and Mohammad B. Shamsollahi,
    in Proc. 11th International Conference on Advanced Communication Technology (ICACT 2009),
    [arXiv] [link].

[S] Surveys, Magazines and Theses

  1. a survey on “Bayesian Black-Box Reductions in Mechanism Design”,
    with Shaddin Dughmi, Jason Hartline and Bobby Kleinberg,
    in ACM SIGecom Exchanges letters, Vol. 16.1,

    [abstract] In this letter, we report on our work providing a polynomial time reduction from Bayesian incentive compatible mechanism design to Bayesian algorithm design for welfare maximization problems. Unlike prior results, our reduction achieves exact incentive compatibility for problems with multidimensional and continuous type spaces.
    [link]

  2. “Algorithms Versus Mechanisms: How to Cope with Strategic Input?”,
    in XRDS: Crossroads, The ACM Magazine for Students, Vol. 24 Issue 1, Fall 2017,

    [abstract] Online markets and platforms rely on human user decisions as inputs. This generates the challenge of managing user incentives and misbehaviors as strategic entities. Surprisingly, one can show that designers do not require much additional computational power to overcome this challenge
    [link]

  3. “Algorithms Vs. Mechanisms: Mechanism Design for Complex Environments”­,
    PhD Thesis (under Professor Robert Kleinberg), Cornell University, Summer 2017,
    [link].

[W] Working Papers and Manuscripts

  1. “Nearly Optimal Pricing Algorithms for Production Constrained and Laminar Bayesian Selection”,
    with Nima Anari, Amin Saberi and Ali Shameli.

    [abstract] We study online pricing algorithms for the Bayesian selection problem with production constraints and its generalization to the laminar matroid Bayesian online selection problem. Consider a firm producing (or receiving) multiple copies of different product types over time. The firm can offer the products to arriving buyers, where each buyer is interested in one product type and has a private valuation drawn independently from a possibly different but known distribution. Our goal is to find an adaptive pricing for serving the buyers that maximizes the expected social-welfare (or revenue) subject to two constraints. First, at any time the total number of sold items of each type is no more than the number of produced items. Second, the total number of sold items does not exceed the total shipping capacity. This problem is a special case of the well-known matroid Bayesian online selection problem studied in [Kleinberg and Weinberg, 2012], when the underlying matroid is laminar. We give the first Polynomial-Time Approximation Scheme (PTAS) for the above problem as well as its generalization to the laminar matroid Bayesian online selection problem when the depth of the laminar family is bounded by a constant. Our approach is based on rounding the solution of a hierarchy of linear programming relaxations that systematically strengthen the commonly used ex-ante linear programming formulation of these problems and approximate the optimum online solution with any degree of accuracy. Our rounding algorithm respects the relaxed constraints of higher-levels of the laminar tree only in expectation, and exploits the negative dependency of the selection rule of lower-levels to achieve the required concentration that guarantees the feasibility with high probability..
    [arXiv]

  2. “Hierarchical Clustering better than Average-Linkage”,
    with Vaggos Chatziafratis and Moses Charikar.

    [abstract] Hierarchical Clustering (HC) is a widely studied problem in exploratory data analysis, usually tackled by simple agglomerative procedures like average-linkage, single-linkage or complete-linkage. In this paper we focus on two objectives, introduced recently to give insight into the performance of average-linkage clustering: a similarity based HC objective proposed by Moseley and Wang (2017) and a dissimilarity based HC objective proposed by Cohen-Addad et al. (2018). In both cases, we present tight counterexamples showing that average-linkage cannot obtain better than 1/3 and 2/3 approximations respectively (in the worst-case), settling an open question raised in Moseley and Wang (2017). This matches the approximation ratio of a random solution, raising a natural question: can we beat average-linkage for these objectives? We answer this in the affirmative, giving two new algorithms based on semidefinite programming with provably better guarantees.
    [arXiv]

  3. “Persuasion and Incentives Through the Lens of Duality”,
    with Shaddin Dughmi, Alexander Psomas, and Matt Weinberg.

    [abstract] Lagrangian duality underlies both classical and modern mechanism design. In particular, the dual perspective often permits simple and detail-free characterizations of optimal and approximately optimal mechanisms. This paper applies this same methodology to a close cousin of traditional mechanism design, one which shares conceptual and technical elements with its more mature relative: the burgeoning field of persuasion. The dual perspective permits us to analyze optimal persuasion schemes both in settings which have been analyzed in prior work, as well as for natural generalizations which we are the first to explore in depth. Most notably, we permit combining persuasion policies with payments, which serve to augment the persuasion power of the scheme. In both single and multi-receiver settings, as well as under a variety of constraints on payments, we employ duality to obtain structural insights, as well as tractable and simple characterizations of optimal policies.


  4. “Prophet vs. Mortal: Ride-sharing Matching with Stochastic Riders”,
    with Amin Saberi.

  5. “Hierarchical Clustering on Geometric Data”,
    with Vaggos Chatziafratis, Moses Charikar and Grigory Yaroslavtsev .

  6. “Prophet Inequalities vs. Approximating Optimum Online”,
    with Ali Shameli and Amin Saberi.

  7. “Combinatorial Bernoulli Factories”,
    with Shaddin Dughmi and Bobby Kleinberg.