Title: Efficient Algorithms for Unknown Markets
Abstract: The concept of market equilibrium is central in economics and
fair, stable, and efficient outcomes in competitive allocation scenarios. Most
results in general equilibrium theory for computing and analyzing equilibria rely on
knowledge of buyers' information such as their preferences, while in reality we
face unknown markets without this information. This gives rise to the following
question: Can we design efficient algorithms that are oblivious to market
other words, are there efficient algorithms for unknown markets?
In this talk, I will survey our recent research on designing efficient algorithms to compute the market equilibrium in different classes of markets, even if one has no information about the number of agents, their individual preferences and endowments, but can only observe the aggregated demands of goods with regard to proposed prices. As a main result, we design a simple ascending-price algorithm to compute an approximate equilibrium in exchange markets with weak gross substitute (WGS) property. It is the first efficient algorithm for this broad class of markets which is easy to implement and avoids heavy machinery such as the ellipsoid method. Moreover, we show several extensions of our technique – the first efficient algorithm to compute an exact equilibrium for markets with spending constraint utilities, and the first efficient algorithm for Fisher markets with budget-additive utilities.
Bio:Xiaohui Bei is currently a Nanyang Assistant Professor at Nanyang Technological University. He got his Ph.D. from Institute for Interdisciplinary Information Sciences of Tsinghua University at Beijing in 2012. Then he spent two years as a research fellow at Nanyang Technological University, and one year at Max Planck Institute for Informatics. His research interests include topics in computational economics, social networks analysis and general algorithm design.
Title: Randomness Extractors beyond the Classical Setting
Abstract:Randomness extractors are deterministic procedures that extract
almost-uniform random sources from certain weak sources of randomness.
Since their invention, various notions of randomness extractors have
found wide range of applications in theoretical computer science.
In this talk, I will present our recent progress on several variants
of this notion “beyond the classical settings,” which grant the
extractor access to untrusted physical (non-classical) devices, and/or
require the extracted randomness to be looked uniform from
non-classical adversaries. In particular, I will highlight our recent
work on the notion of no-signaling secure physical randomness
extractors, which extract randomness against "no-signaling
adversaries" without any independence or structural assumptions, and
its physics implications.
Bio:Kai-Min Chung is an associate research fellow at Institute of Information Science (IIS), Academia Sinica in Taiwan. Prior to joining IIS, he was a postdoc at Cornell University supported by Simons Postdoctoral Fellowship in 2010-2013, and received his Ph.D. in computer science at Harvard University. His research interests are in the fields of cryptography, complexity theory, and quantum cryptography with recent focus on developing cryptographic solutions suitable for cloud environments, and techniques for post-quantum cryptography against quantum side information. He has served on the program committees of cryptography conferences including CRYPTO, TCC, and Asiacrypt.
Title: Algorithm Frameworks Based on Structure Preserving Sampling
Abstract: Sampling, or computing on a subset of the data, is a simple yet effective method for designing efficient algorithms. Such routines produce sparse approximates of either dense inputs, or dense intermediate objects that arise during computation. They play central roles in many recent developments in linear system solvers,combinatorial optimization, and numerical linear algebra. This talk will focus on the design and application of these sampling methods, which despite the wide range of problems addressed, have much in common. These routines lead to provably efficient algorithms for a wide range of problems motivated by combinatorial and scientific flows.
Bio:Richard Peng is an assistant professor in the school of computer science at Georgia Institute of Technology. His main research interests are in the design, analysis, and implementation of efficient algorithms. Richard received his Ph.D. from Carnegie Mellon University in 2013 and was an instructor (postdoc) in applied math at Massachusetts Institute of Technology until 2015. He was a Microsoft Research PhD Fellow and his thesis won the CMU SCS Distinguished Dissertation Award.
Title:Worst-Case Optimal Join Algorithms
Abstract:Evaluating join queries is one of the most central problems in relational databases, both in theory and practice. Yet surprisingly, the worst-case complexity of join evaluation has started to be unraveled just recently. In this talk, I will survey the worst-case optimal join algorithms developed recently, in internal memory, external memory, as well as some parallel models.
Bio: Ke Yi is an Associate Professor in the Department of Computer Science and Engineering, Hong Kong University of Science and Technology. He obtained his Bachelor's degree from Tsinghua University (2001) and Ph.D. from Duke University (2006), both in computer science. His research spans theoretical computer science and database systems. He has received a Google Faculty Research Award (2010), a Young Investigator Research Award from HKUST (2012), and an ACM SIGMOD Best Demonstration Award (2015). He currently serves as an Associate Editor of TODS and TKDE.
Title:Sensitivity Conjecture and Log-rank Conjecture for functions with small alternating numbers
Abstract:The Sensitivity Conjecture and the Log-rank Conjecture are among the
most important and challenging problems in concrete complexity. Incidentally, the
Sensitivity Conjecture is known to hold for monotone functions, and so is the
Log-rank Conjecture for f(x∧y) and f(x⊕y) with monotone functions f, where ∧ and ⊕
are bit-wise AND and XOR, respectively. In this paper, we extend these results to
functions f which alternate values for a relatively small number of times on any
monotone path from all-0 input to all-1 input. These deepen our understandings of
the two conjectures, and contribute to the recent line of research on functions with
small alternating numbers.
Paper available at arXiv:1602.06627.
Bio:Shengyu Zhang received his B.S. in Mathematics at Fudan University in 1999, his M.S. in Computer Science at Tsinghua University in 2002 (under the supervision of Prof. Mingsheng Ying), and his Ph.D. in Computer Science at Princeton University in 2006 (under the supervision of Prof. Andrew Yao). After working in NEC Laboratories America for a summer, and in California Institute of Technology for two years as a postdoc, he joined The Chinese University of Hong Kong, where he is now an associate professor in Department of Computer Science and Engineering. His research interest focuses on algorithm designs, computational complexity, quantum computing, and foundation of machine learning.