New additions to Theory group

The Northwestern Theory group is excited to announce that we have several folks joining us at the beginning of this academic year! We have Hedyeh Beyhaghi as a postdoc joining from Cornell, Shravas Rao as a postdoc joining from NYU, Sumedha Uniyal as a visiting postdoc from Aalto University, Finland; Pattara Sukprasert as a new grad student transferring from the University of Maryland College Park; Saba Ahmadi and Sheng Yang, visiting grad students from the University of Maryland College Park.

Hedyeh Beyhaghi. Dr. Beyhaghi’s research interests are in Algorithm Design, with an emphasis on Algorithmic Game Theory and Mechanism Design. Her research mainly focuses on Auction Design, Online Stochastic Optimization, and Matching Markets. She obtained her Ph.D. at Cornell University, under the supervision of Eva Tardos.This text is only to create extra space for good indentation. Kudos to you if you found this text! Have a nice day. This text is only to create extra space for good indentation. Kudos to you if you found this text! Have a nice day.

 

Shravas Rao. Dr. Rao’s research interests are in theoretical computer science, with an emphasis on derandomization and pseudorandomness. He completed his Ph.D. at New York University advised by Oded Regev.This text is only to create extra space for good indentation. Kudos to you if you found this text! Have a nice day. This text is only to create extra space for good indentation. Kudos to you if you found this text!

 

Sumedha Uniyal. Dr. Uniyal is a postdoctoral researcher (Oct’17-Present) in the group of Prof. Parinya Chalermsook at Aalto University, Finland. She did her Ph.D. (Apr’13-Oct’17) at IDSIA, University of Lugano, Switzerland; under the supervision of Prof. Fabrizio Grandoni. She is broadly interested in approximation algorithms and algorithmic graph theory. During her Ph.D., she has worked on developing approximation algorithms for connectivity problems, clustering problems, and submodular optimization. Recently, she is also interested in structural graph theory and its implications in algorithms. She will be a visiting scholar at Northwestern till Dec’19 working with Prof. Samir Khuller.

 

Pattara Sukprasert. Pattara is a third-year Ph.D. student advised by Prof. Samir Khuller. He transferred from the University of Maryland College Park, where he spent his first two Ph.D. years and received a Master’s degree. Before that, he lived mostly in Thailand and got another Master’s degree from Kasetsart University advised by Prof. Jittat Fakcharoenphol. He is interested in approximation algorithms and graph theory, and has worked on network design problems, network flow problems, and some structural graph theory problems. Recently, he has also developed some interests in fast (up to sub-cubic) approximation algorithms.

 

Saba Ahmadi. Saba is a fifth year PhD student at the University of Maryland College Park visiting Northwestern, and she is advised by Prof. Samir Khuller. She is mainly interested in designing approximation algorithms. She is also interested in the topic of fairness and its relevance to combinatorial optimization. She finds problems at the intersection of AI and combinatorial optimization very interesting, one example is how to have diversity in the matching markets.

 

Sheng Yang. Sheng is a fifth year PhD student at University of Maryland, College Park advised by Prof. Samir Khuller. Currently, he is visiting Northwestern as a pre-doctoral visiting scholar. He is broadly interested in approximation algorithms. He has worked on graph theory topics related to connected dominating set and induced subgraph counting. Currently, he is mainly working on various scheduling problems, classical and new challenges originating from cloud computing.

Northwestern CS Theory group @ FCRC 2019

The Northwestern CS Theory group cumulatively had eight papers at conferences held as part of the ACM Federated Computing Research Conference(FCRC) 2019, which took place recently in Phoenix, AZ. We had two papers in COLT, four in EC, and one each in SPAA and STOC. Members of the group who attended include Professors Jason Hartline, Samir Khuller, Konstantin Makarychev, and Aravindan Vijayaraghavan, postdoc Xue Chen, PhD students Yiding Feng, Aleck Johnsen, Yingkai Li, and Aravind Reddy. Also in attendance were CS Prof. Jessica Hullman and Econ PhD student Modibo Camara.

Conference on Learning Theory(COLT):

TCS postdoc Xue Chen presented a joint paper “Active Regression via Linear-Sample Sparsification” with Eric Price (UT Austin). This paper gives an efficient algorithm with an optimal sample complexity for the classical problem of linear regression. Its techniques yield improved results for the non-linear sparse Fourier transform setting.

TCS Ph.D. student Yingkai Li presented a joint paper with Yining Wang (CMU) and Yuan Zhou (UIUC). The paper “Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits” obtained almost tight dependence on the time horizon for regret minimization in linear bandits. One of the main results is to show that there is an extra sqrt(log T) factor in the lower bound, revealing a regret scaling quite different from classical multi-armed bandits. Our proof techniques include variable confidence levels and a careful analysis of layer sizes of SupLinUCB on the upper bound side, and delicately constructed adversarial sequences showing the tightness of elliptical potential lemmas on the lower bound side.

Economics and Computation(EC):

TCS Ph.D. alumnus Sam Taggart (Assist. Prof. Oberlin College) presented a joint paper with TCS Prof. Jason Hartline in the joint session of EC and STOC.  The paper, “Sample Complexity for Non-truthful Mechanisms“, describes a family of winner-pays-bid and all-pay (i.e., non-truthful) mechanisms that can be optimized from past bid data from the same market.  Most mechanisms in practice are non-truthful and, for example, the winner-pays-bid format is especially common.  The literature on sample complexity in mechanism design is well established, however, this paper is the first to consider non-truthful mechanisms.

TCS Prof. Jason Hartline presented a joint paper with TCS Ph.D. student Aleck Johnsen, Dennis Nekipelov (UVA), and Onno Zoeter (Booking.com).  The paper, “Dashboard Mechanisms for Online Marketplaces” gives a theoretical model for how a bidding dashboard can both make it easier for bidders in an online marketplace to optimize their bids and for the designer to optimize the mechanism.  A key idea in the paper is that if bidders optimize their bids for the dashboard, which predicts the outcome that will be obtained for any bid, then the underlying preferences of the bidders can be easily inferred from the bids.  Link to Video.

TCS Ph.D. student Yingkai Li presented a joint paper with TCS Prof. Jason Hartline and TCS Ph.D. student Yiding Feng.  The paper, “Optimal Auctions vs. Anonymous Pricing: Beyond Linear Utility“, introduces a approximation framework which approximately reduces the analysis of anonymous pricing for agents with non-linear utility to agents with linear utility in revenue-maximization. Applying this framework, constant approximation guarantee of anonymous pricing is shown for agents with public-budget utility, private-budget utility, and (a special case of) risk-averse utility.  A key idea in the paper is to define a parameterization of the regularity property that extends to agents with non-linear utility. Link to Video.

TCS Ph.D. student Chenhao Zhang had a joint paper with Nick Gravin (Shanghai University of Finance and Economics), Yaonan Jin (Columbia University) and Pinyan Lu (Shanghai University of Finance and Economics). The paper “Optimal Budget-Feasible Mechanisms for Additive Valuations” obtained tight approximation guarantee for budget-feasible mechanisms with an additive buyer. The paper proposes two-stage mechanisms that composite price-posting schemes with a pruning mechanism which greedily excludes the items with low value-per-cost ratios. A tight 2-approximation against the Knapsack and a tight 3-approximation against the Fractional-Knapsack are obtained by the proposed randomized and deterministic mechanisms respectively. Link to Video.

Symposium on Parallelism in Algorithms and Architectures(SPAA):

TCS Prof. Samir Khuller had a joint paper with visiting TCS PhD student Sheng Yang(UMD), Mosharaf Chowdhury(UMich), Manish Purohit(Google), and Jie You(UMich). The paper “Near Optimal Coflow Scheduling in Networks” focuses on the coflow scheduling problem which studies scheduling and data communication inter and intra datacenters. The main result is a randomized 2 approximation algorithm, significantly improving prior work both in theory and in practice.

Symposium on the Theory of Computing(STOC):

TCS Prof. Konstantin Makarychev had a paper with Yury Makarychev(TTIC) and Ilya Razenshteyn (Microsoft Research). This paper, “Performance of Johnson-Lindenstrauss Transform for k-Means and k-Medians Clustering“, shows that the cost of the optimal solution for Euclidean k-means or k-medians clustering is preserved up to a factor of (1+ε) under a projection onto a random O(log(k/ε)/ε2)-dimensional subspace. For k-means, this result resolves an open problem posed by Cohen, Elder, Musco, Musco, and Persu (STOC 2015); for k-medians, it answers a question raised by Kannan.

Two Northwestern papers at FOCS 2017

The Northwestern CS Theory group had two papers at the 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), which was recently held in Berkeley, CA.

TCS Postdoc Huck Bennett had a joint paper with Alexander Golovnev (Columbia and Yahoo Research) and Noah Stephens-Davidowitz (Princeton). The paper, “On The Quantitative Hardness of CVP,” initiates the study of the fine-grained complexity of lattice problems, a study which is important to the rapidly developing field of lattice-based cryptography. As its main result, the paper shows strong hardness of the Closest Vector Problem (CVP) with certain parameters assuming the Strong Exponential Time Hypothesis (SETH).

TCS Prof. Aravindan Vijayaraghavan had a joint paper with Oded Regev
(NYU). The paper, “Learning Mixtures of Well-Separated Gaussians,”
studies the classic problem of learning a mixture of k spherical
Gaussian distributions. The paper tries to characterize the
minimum amount of separation needed between the components to
estimate the parameters (means) of the Gaussians, and presents lower
bounds and upper bounds towards this end.

 

 

Konstantin Makarychev joins Northwestern CS Theory Group!

makarychev-konstantinThe Computer Science Division at Northwestern University welcomes new faculty member Dr. Konstantin (Kostya) Makarychev as an Associate Professor, beginning immediately. Dr. Makarychev’s position is one of the ten new faculty lines in CS which were announced in June 2016.

Dr. Makarychev is a theoretical computer scientist working on approximation algorithms, beyond worst-case analysis, applications of high-dimension geometry to computer science, and combinatorial optimization for designing efficient algorithms for computationally hard problems.

Dr. Makarychev joins Northwestern from Microsoft Research in Redmond, WA (2012-2016) and IBM Research Labs in Yorktown Heights, NY (2007-2012). Further details of his background can be found on his personal webpage.

Please click here for details, and the announcement on Northwestern homepage.

“Teaching” Postdocs

The EECS Department has announced multiple postdoctoral fellowships in Computer Science.  These fellowships come with a mix of teaching and research responsibilities and a ideal for candidates who wish to strengthen both their teaching and research experience before going on the academic job market.  Successful candidates will teach one course per term and conduct independent research, collaborating as is most effective, with current Northwestern faculty and students.

One of the priority areas for these positions is algorithms.  The teaching component of this position would be the undergraduate algorithms or discrete math courses and an advanced elective in the fellow’s research area.

Postdoc Openings

The Northwestern Theory group seeks applications for 1-2 postdoctoral positions starting in September 2017. Applicants should be recent Ph.D.’s with interest in theoretical computer science. Research areas include but are not limited to algorithms, computational complexity, theoretical machine learning and optimization.  The postdoc will also be able to take advantage of the strong theory presence in the Chicago area overall. 
Applications will be accepted until the position is filled. However, applications need to be submitted by Jan 1st, 2017 to receive full consideration. Please see  http://theory.eecs.northwestern.edu/prospective-postdocs/ for details.

Prof. De’s research at FOCS 2016

TCS Prof. Anindya De had a joint paper with Michael Saks (Rutgers) and Sijian Tang (Rutgers) in 57th Annual IEEE Symposium on Foundations of Computer Science (FOCS 16). The paper “Noisy population recovery in polynomial time” addresses the problem of recovering an unknown distribution on binary strings under noise. This problem is related to well-studied problems in learning such as learning mixtures of spherical Gaussians and product distributions. A manuscript of the paper can be found here.

 

 

 

Abhratanu Dutta and Yiding Feng finish 1st in ACM-ICPC Midcentral Regional

Theory PhD students Abhratanu Dutta and Yiding Feng along with their teammate Ruohong Zhang finished first at the ACM-ICPC Midcentral Regional Programming Contest this year. They finished in 1st place out of 156 teams representing 56 different schools in total and have advanced to the ACM-ICPC World Finals in Rapid City, South Dakota from May 20-25, 2017.

The ACM-ICPC (Association for Computing Machinery – International Collegiate Programming Contest) is a multi-tier, team-based, programming competition. Headquartered at Baylor University, Texas, it operates according to the rules and regulations formulated by the ACM. The contest participants come from over 2,000 universities that are spread across 80 countries and six continents.

Details can be found here.

Eight at EC and GAMES

The 2016 ACM Conference on Economics and Computation and the World Congress of the Game Theory Society (GAMES 2016) were colocated at Maastricht University in the medieval town of Maastricht, Netherlands in late July.  The Northwestern theory group had an especially strong showing with seven papers presented and a public lecture!  Brief summaries are given below.

wgt004_websiteheader_090615

Ph.D. student Manolis Pountourakis presented two papers.  At GAMES, he presented his paper Optimal Auctions vs. Anonymous Pricing (joint with with coauthors Saeed Alaei, Northwestern Prof. Jason HartlineRad Niazadeh, and Yang Yuan).  The paper proves that eBay’s Auctions and Buy-It-Now (posted pricings) are within at least an e = 2.718 factor of the revenue optimal auction (which may be asymmetric and very complicated). This is a worst-case bound that is quite difficult to prove; in practice the eBay’s sales mechanisms likely do much better.  This paper previously appeared in FOCS 2015 and with this video of the talk.  At EC, he presented Procrastination with Variable Present Bias (joint with coauthors Nick Gravin, Nicole Immorlica, and Brendan Lucier).  Individuals attempting to complete a task often procrastinate, making plans and then failing to follow through. One well-known model of such behavioral anomalies is present-bias discounting: individuals over-weight present costs by a bias factor. This paper introduces a variant of this model where the bias factor varies across time, identifies a connection between the planning problem with variable present bias and optimal pricing, and uses this connection to bound the cost of procrastination.

Nima Haghpanah, a former Ph.D. student and now faculty member in the Economics Department at Penn State, presented two papers.  At GAMES he presented Multi-dimensional Virtual Values and Second-degree Price Discrimination (joint with Northwestern Prof. Jason Hartline).  This paper studies multi-dimensional mechanism design.  It develops a method for solving for multi-dimensional virtual values, the pointwise optimization of which gives the optimal mechanism.  It uses these virtual values to characterize the family of distributions where second-degree price discrimination (e.g., with a high- and low-quality version of a product) is not profitable.  At EC he presented  Sequential Mechanisms with ex-post Participation Guarantees (joint with Profs. Itai Ashlagi of Stanford and Constantinos Daskalakis).  The paper identifies optimal and approximately optimal mechanisms in dynamic setting in which a seller and a buyer interact repeatedly.  In contrast to standard settings, in this paper the outcomes of a mechanism must be acceptable to the buyer even after all uncertainty is resolved.

At the second Workshop on Algorithmic Game Theory and Data Science (a part of the EC program), Ph.D. student Sam Taggart presented Non-revelation Mechanism Design (joint with Northwestern Prof. Jason Hartline).  This paper shows how to better design Bayes-Nash mechanisms, e.g., with winner-pays-bid or all-pay semantics, in a repeated environment by “linking decisions” across the repetitions.  The designed mechanisms are asymptotically optimal with the number of repetitions that are linked.

At EC, Prof. Jason Hartline presented A/B Testing of Auctions (joint with Shuchi Chawla and Denis Nekipelov).  This paper shows how the counter factual revenue of a mechanism B can be estimated from the equilibrium bids in a mechanism C which is the convex combination of mechanism A and B.  For example, an auctioneer with multiple units can determine whether selling one unit or two units gives higher revenue by running the auction that probabilistically sells one or two units.  The methods applies generally to position auctions to both winner-pays-bid and all-pay semantics.

Adjunct Northwestern Prof. Nicole Immorlica presented two papers.  At the Workshop on Economics of Cloud Computing she presented On-demand or Spot? Selling the Cloud to Risk-averse Customers (joint with former Ph.D. student Darrell Hoy and Nikhil Devanur). In Amazon EC2, cloud resources are sold through a combination of the on-demand market, in which customers buy resources at a fixed price, and the spot market, in which customers bid for an uncertain supply of excess resources. This paper showed that such a dual market system improves upon key objectives when customers have heterogeneous risk attitudes: the welfare and revenue of its unique equilibrium is larger than that of spot markets alone and the efficiency is larger than only on-demand markets.

roy-small

A slide from “Market Design without Money”

At a GAMES affiliated evening soirée with the Brightlands Young Professionals network Prof. Immorlica gave a Roy-Lichtenstein-themed public lecture entitled “Market Design without Money”.  As a market-designer, a primary goal is to allocate resources to individuals in a way that maximizes the total value of the community for the allocation.  Selling the resources is a great way to achieve this: if someone is willing to pay a high price for something, then they must have a high value for it as well.  However, in many settings of interest, payments are infeasible.  This could be due to repugnance, as in the assignment of public schools to children or cadaver kidneys to patients.  Or perhaps the market technologies can not support financial transactions, e.g., users of an online review system like TripAdvisor may not have bank accounts linked to their user accounts.  This talk explored using alternative incentives including risk, waiting time, and social status, in place of money to help optimize markets in such scenarios.

Great work to the presenters and coauthors of these papers!

Sam Taggart wins Best TA award for 2016!

13350393_10153594297472826_6314011487591609603_oSam Taggart won the 2016 Northwestern EECS Best TA award for his work TAing EECS 336: Design and Analysis of Algorithms this Fall. The class tripped in size over the last couple years and Sam taught all 150 students in six discussion sessions. Even with this overwhelming workload he received incredibly high scores on the teaching evaluations with rave comments. Great work Sam!!

« Older posts