Theory Reading Group@cse.ust.hk

Title: Cell-Probe Lower Bounds for Succinct Partial Sums

Speaker: Qin Zhang

Abstract: The partial sums problem in succinct data structures asks to preprocess an array A[1 .. n] of bits into a data structure using as close to n bits as possible, and answer queries of the form Rank(k) = A[1] + ... + A[k]. The problem has been intensely studied, and features as a subroutine in a number of succinct data structures. This paper gives a tight lower bound for the problem. The proof is done by an elegant encoding argument, which is quite useful to know.

Date: 22, Dec, 2009 Time: 3:00 - 4:30 pm Venue: 2578

Title: Fusion tree

Speaker: Jiongxin Jin

In this talk, we will study "Fusion tree", a data structure that supports fast predecessor/successor queries.

Date: 17, June, 2009 Time: 3:30 - 5:00 pm Venue: 3530

Title: On the Lower Bounds on the Dynamic Dictionary Problem

Speaker: Qin Zhang

In this talk, we will discuss one of the most fundamental data structure problems -- the Dictionary Problem. We consider the tradeoff between the cost of update and query in the dynamic setting. We will discuss a result by Rajamani Sundar in its simplest version (if time permits, we can talk about some intuition of its general version, which is very very complicated). We also try to mention some similarities, although just coincidences, between Sundar's work and our work for the dynamic setting with a cache .

Date: 3, June, 2009 Time: 3:30 - 5:00 pm Venue: 3530

Title: Maximizing the Spread Influence in Social Networks

Speaker: Jiongxin Jin

In this talk, we will discuss the problem of maximizing the influence spread in social networks. First, we will consider two widely used models, which are called independent cascade and linear threshold, and see how to compute a (1-1/e)-approximate solution using greedy algorithms. Then, we will see a much more general model, and prove its influence function is submodular. The submodularity of the influence function implies a (1-1/e)-approximation by greedy algorithms.

Date: 5, May, 2009 Time: 3:30 - 5:00 pm Venue: 2578

Title: Team Competition

Speaker: Pingzhong Tang

Abstract: In a team competition, two participating teams have an equal number of players, and each team orders its players linearly based on their strengths. A mechanism then specifies how the players from the two teams are matched up and how to score them. There are two types of manipulations by a team: Misreporting the strength ordering and deliberately losing a match. To identify these strategically behaviors, we model the team competition problem in a game-theoretical framework, under which we prove necessary and sufficient conditions which ensure that truthful reporting and maximal effort in matches are equilibrium strategies, and which further ensure certain fairness conditions described by choice functions.

  • Reference: Team Competition by Pingzhong Tang, Yoav Shoham, Fangzhen Lin, To appear in AAMAS, 2009.
Date: 29, April, 2009 Time: 3:30 - 5:00 pm Venue: 2578

Title: Range counting over multidimensional Data Stream

Speaker: Zengfeng Huang

Abstract: In this talk, we will discuss algorithms of maintaining epsilon-approximation over a stream of d-dimensional points.

Date: 15, April, 2009 Time: 3:00 - 4:00 pm Venue: 2578

Title: Sink equilibrium and convergence

Speaker: Jiajin Yu

Abstract: In this talk, we will see a new solution concept called sink equilibrium. After discussing the motivation and definition of sink equilibrium, we will use it to analyze the unsplittable selfish routing game. Using a similar technique, we can bound the number of best responses needed to approximate the social optimal in some weighted congestion game. We will also see some properties of sink equilibrium in the facility location game, a special case of valid-utility game.

Date: 25, Mar, 2009 Time: 3:30 - 5:00 pm Venue: 3530

Title: Expander graphs I

Speaker: Zhewei Wei

Abstract: In this talk we will discuss a interesting family of graph: expander graphs. We will consider 3 motivating problems and solve them using a "Magical Graph". Then we will give a definition of expander graph. The talk will closely follow Hoory's Survey.

Date: 18, Mar, 2009 Time: 3:30 - 5:00 pm Venue: 2578

Title: Computing epsilon-approximation

Speaker: Zengfeng Huang

Abstract: In this talk, we will discuss a deterministic algorithm to compute an epsilon-approximation of a set system with bounded VC-dimension. The size of the epsilon-approximation computed will be small and independent on the size of the set system..

Date: 11, Mar, 2009 Time: 3:30 - 5:00 pm Venue: 2578

Title: Cache Oblivious B-trees

Speaker: Zhewei Wei

Abstract: In this talk, we will discuss a dynamic dictionary designed for a hierarchy memory called cache oblivious B-tree. The structure achieves an optimal range query cost and an near-optimal amortized update cost, on any hierarchical memory. The structure is also locality-preserving, and therefore supports fast sequential access.

Date: 4, Mar, 2009 Time: 3:30 - 5:00 pm Venue: 2578

Title: Introduction to the Learning Theory

Speaker: Elad Verbin

Abstract: In this talk, we will give an introduction for learning theory, and in particular, we will breifly discuss the Fourier analysis used in the learning theory.

Date: 11, Feb, 2009 Time: 3:30 - 5:00 pm Venue: 3530

Title: Lower Bounds for Static Data Structures via Asymmetric Communication Complexity: Part III

Speaker: Jian Xia

Abstract: In this talk, we discuss the reduction chain from set disjointness to reachability oracles and then to orthogonal range stabbing. The presentation will closely follow Chapter 7 of Mihai's PhD thesis.

Date: 26, Nov, 2008 Time: 3:30 - 5:00 pm Venue: 3530

Title: Lower Bounds for Static Data Structures via Asymmetric Communication Complexity: Part II

Speaker: Jian Xia

Abstract: In this talk, we discuss two static problems such as partial match and approximate near neighbor search, and prove the lower bounds by reduction from the communication complexity of set disjointness. The presentation will closely follow Chapter 6 of Mihai's PhD thesis.

Date: 5, Nov, 2008 Time: 3:30 - 5:00 pm Venue: 3530

Title: Approximate clustering

Speaker: Jiongxin Jin

Abstract: For clustering problems, many approximation algorithms have been developed to approximate the objective functions(i.e. k-median). In many applications, approximately optimizing the objectives actually gives us a clustering close to the truth. In this talk, we will discuss the clustering problem in metric spaces under the assumption of (c, \eps) property, that is, any c-approximation to the given objective function gives a clustering with symmetric difference \eps to the truth. We will see effecient algorithms for k-median and k-means with any c > 1, and for min-sum objective with any c > 2.

Date: 29, Oct, 2008 Time: 3:30 - 5:00 pm Venue: 3530

Title: Lower Bounds for Static Data Structures via Asymmetric Communication Complexity: Part I

Speaker: Jian Xia

Abstract: A key tool in showing lower bounds for static data structures is asymmetric communication complexity. In this talk, we discuss simple communication problems such as INDEXING and Lopsided Set Disjointness (LSD), and prove the tight deterministic lower bounds for these two problems using the richness method. The presentation will closely follow Chapter 5 of Mihai's PhD thesis.

Date: 22, Oct, 2008 Time: 3:30 - 5:00 pm Venue: 2578

Title: Introduction to the cell-rpobe model and lowerbound techniques

Speaker: Qin Zhang

Abstract: In this talk, we will give an introduction about the cell-probe model. We will first discuss a game called "Were-you-last", which serves as a good example for us to get some felling about how to prove lowerbounds in the cell-probe model. Next, we show a lowerbound result for the dynamic ranking problem in the cell-probe model, using a technique called the Chronogram method.

Date: 15, Oct, 2008 Time: 3:30 - 5:00 pm Venue: 3530

Title: Constant-time approximation algorithms via local improvements

Speaker: Jiongxin Jin

Abstract: In this talk, we will discuss a technique for transforming classical approximation algorithms into constant-time approximation algorithms. This technique is based on greedy local improvements in random order. Then, we will see how to apply the technique to some classical problems, including Max-Matching and Set-Cover.

Date: 08, Oct, 2008 Time: 3:30 - 5:00 pm Venue: 3530

Title: Cuckoo hashing

Speaker: Jiongxin Jin

Abstract: In this talk, we review a simple and cute hashing, called cuckoo hashing. It was first introduced by Pagh and Rolder in 2001. It makes use of O(\log_{1+\eps} n) independent universal hashing family and achieves O(1) expected time for update, O(1) worst case time query and (2+\eps)n space.

Date: 24, Sep, 2008 Time: 3:30 - 5:00 pm Venue: 3530

Title: The Dynamic Graph Connectivity Problem: Lowerbound

Speaker: Qin Zhang

Abstract: In this talk, we study the \Omega(log n) lowerbound of the dynamic graph connectivity algorithm. And as a warm up, we first study the dynamic partial sum problem. Both results are due to Mihai Patrascu and Erik Demaine. Like the upper bound of the dynamic connectivity problem shown in the previous talk, this is also an important question open for years!

Date: 17, Sep, 2008 Time: 3:30 - 5:00 pm Venue: 3530

Title: The Dynamic Graph Connectivity Problem: Upperbound

Speaker: Qin Zhang

Abstract: In this talk, we study the dynamic graph connectivity algorithm proposed by Henzinger and King, this is the first dynamic algorithms to maintain the connectivity (amony others) in polylogarithmic time per edge insertion and deletion.

  • Reference: Randomized fully dynamic graph algorithms with polylogarithmic time per operation (Google it!) by Monika Rauch Henzinger, Valerie King, 1999
Date: 10, Sep, 2008 Time: 3:30 - 5:00 pm Venue: 4480 (Via Lift 25/26)

Title: Algorithms for Secretary Problems on Graphs

Speaker: Jiajin Yu

Abstract: In this talk, we study several online matching problems with applications to Internet advertising reservation systems. The first model is a edge-weighted bipartite graph G, with partite sets L, R. Initially given R, and |L|, the algorithm receives the vertices of L sequentially, in a random order. When a vertex l in L is seen, all edges incident to l are revealed, together with their weights. The algorithm must immediately either match l to an available vertex of R, or decide that l will remain unmatched..

Date: 28, Aug, 2008 Time: 2:30 - 4:00 pm Venue: 4201 (Via Lift 19/20)

Title: Embedding and similarity search for point sets under translation

Speaker: Jiongxin Jin

Abstract: David Mount gave a talk about their recent work last week. In this talk, we will review the paper and discuss some details. We are given a point set that may contain outliers and are subject to an unknown translation. We define the distance between any two point sets to be the minimum size of their symmetric difference over all translations of one set relative to the other. We want to compute the closest matches in the database efficiently. The approach is based on showing that there is a randomized algorithm that computes a translation-invariant embedding of any point set of size at most n into the L_1 metric, so that with high probability, distances are subject to a distortion that is O(log^2 n).

Date: 27, Aug, 2008 Time: 2:30 - 4:00 pm Venue: 4201 (Via Lift 19/20)

Title: Logarithmic lower bounds in the cell-probe model

Speaker: Qin Zhang

Abstract: In this talk, we introduce a new technique for proving cell-probe lower bounds on dynamic data structures. This technique enables us to prove an amortized randomized (lg n) lower bound per operation for several data structural problems on n elements, including partial sums and dynamic connectivity in graphs.

Date: 26, August, 2008 Time: 2:30 - 4:00 pm Venue: 4201 (Via Lift 19/20)

Title: Network design with weighted players

Speaker: Jiajin Yu

Abstract: In this talk, we will first have a quick review of the unweighted model of network design games. We will see how to use potential function method to prove the upper bound of price of stability in the game. Then we introduce the weighted player model of network design games on directed graph and the idea of \alpha-approximate Nash equilibria. We show how potential function method can be modified to prove the upper bound of price of stability with respect to O(\log w_{\max})-approx. N.E. At last we will study how to prove the lower bound of \alpha for \alpha-approx N.E in this model.

Date: 16, April, 2008 Time: 2:00 - 3:00 pm Venue: 3530 (Via Lift 25/26)

Title: The space complexity of approximating the frequency moments

Speaker: Jian Xia

Abstract: In this talk, we will study streaming algorithms, especially those of approximating the frequency moments. At the beginning, the first result on this problem will be presented, and then we will discuss the optimal result found by Piotr Indyk and David P. Woodruff. If we still have some time, we can study the CountSketch algorithm, which is used as a subroutine in the optimal algorithm.

Date: 9, April, 2008 Time: 2:30 - 3:30 pm Venue: 2578 (Via Lift 19/20)

Title: Approximation Algorithms for Clustering Uncertain Data

Speaker: Jiongxin Jin

Abstract: In this talk, we will see the some clustering problems on uncertain data. For uncertain versions of k-means and k-median, we show reductions to their corresponding weighted versions without uncertainty. For k-center, we pick O(k\epsilon^{-1}\log n \log \Delta) centers to achieve \epsilon approximation. Alternatively, we pick 2k centers to achieve a constant factor approximation.

Date: 2, April, 2008 Time: 2:30 - 3:30 pm Venue: 2578 (Via Lift 29/30)

Title: Routing and Packing Via Online Primal-Dual

Speaker: Qin Zhang

Abstract: In this talk, we study a wide range of online and offline routing and packing problems with various objectives. We provide a unified approach, based on a clean primal-dual method, for the design of online algorithms for these problems, as well as improved bounds on the competitive factor.

Date: 26, Mar, 2008 Time: 2:30 - 3:30 pm Venue: 4201 (Via Lift 19/20)

Contact