Skip to main content

Activity Report, July - December 2010

Contents

Highlights


Additive Spanners in Nearly-Quadratic Time

David Woodruff considers the problem of efficiently finding an additive $C$-spanner of an undirected unweighted graph $G$, that is, a subgraph $H$ so that for all pairs of vertices $u,v$, $\delta_H(u,v) \leq \delta_G(u,v) + C$, where $\delta$ denotes shortest path distance. It is known that for every graph $G$, one can find an additive $6$-spanner with $O(n^{4/3})$ edges in $O(mn^{2/3})$ time. It is unknown if there exists a constant $C$ and an additive $C$-spanner with $o(n^{4/3})$ edges. Moreover, for $C \leq 5$ all known constructions require $\Omega(n^{3/2})$ edges. David gives a significantly more efficient construction of an additive $6$-spanner. The number of edges in his spanner is $n^{4/3}$polylog(n), matching what was previously known up to a polylogarithmic factor, but he greatly improves the time for construction, from $O(mn^{2/3})$ to $n^2$polylog(n). Notice that $mn^{2/3} \leq n^2$ only if $m \leq n^{4/3}$, but in this case $G$ itself is a sparse spanner. This thus provide both the fastest and the sparsest (up to logarithmic factors) known construction of a spanner with constant additive distortion. Work appeared in ICALP, 2010.

Bypassing UGC from Some Optimal Geometric Inapproximability Results

Together with Venkatesan Gurusami (CMU), Prasad Raghavendra (Georgia Tech), and Rishi Saket (Princeton), Yi Wu shows how to bypass the UGC assumption in inapproximability results for two geometric problems, obtaining a tight NP-hardness result in each case. The first problem known as the Lp Subspace Approximation is a generalization of the classic least squares regression problem. The authors show that for any finite $p$, it is NP-hard to approximate this problem to within a factor of $\gamma_p-\eps$ for constant $\epsilon>0$, where $\gamma_p$ is the $p$-th moment of a standard Gaussian. This matches the $p$ approximation algorithm obtained by Deshpande, Tulsiani and Vishnoi who also showed the same hardness result under the UGC. The second problem the authors study is the related Lp Quadratic Grothendieck Maximization Problem, considered by Kindler, Naor and Schechtman. Here, the input is a multilinear quadratic form, and the goal is to maximize the quadratic form over the p unit ball. The authors show that for any finite constant $p>2$, it is NP-hard to approximate the problem within a factor of $\gamma_p^2-\epsilon$ for any $\epsilon>0$. The same hardness factor was earlier shown under the UGC. The authors also obtain a $\gamma_p^2$-approximation algorithm for the problem using a convex relaxation of the problem. These are the first approximation thresholds, proven under P=NP, that involve the Gaussian random variable in a fundamental way. Note that the problem statements themselves have no mention of Gaussians. This work will appear in SODA, 2012.

Hardness of Max-2LIN and Max-3LIN

In 1997, H{\aa}stad showed $\NP$-hardness of $(1-\eps, 1/q + \delta)$-approximating $\maxthreelin(\Z_q)$; however it was not until 2007 that Guruswami and Raghavendra were able to show $\NP$-hardness of $(1-\eps, \delta)$-approximating $\maxthreelin(\Z)$. In 2004, Khot--Kindler--Mossel--O'Donnell showed $\UG$-hardness of $(1-\eps, \delta)$-approximating $\maxtwolin(\Z_q)$ for $q = q(\eps,\delta)$ a sufficiently large constant; however achieving the same hardness for $\maxtwolin(\Z)$ was given as an open problem in Raghavendra's 2009 thesis. Together with Ryan O'Donnell (CMU) and Yuan Zhou (CMU), Yi Wu shows that fairly simple modifications to the proofs of the $\maxthreelin(\Z_q)$ and $\maxtwolin(\Z_q)$ results yield optimal hardness results over $\Z$. In fact, the authors show a kind of ``bicriteria'' hardness: even when there is a $(1-\eps)$-good solution over $\Z$, it is hard for an algorithm to find a $\delta$-good solution over $\Z$, $\reals$, or $\Z_m$ for any $m \geq q(\eps,\delta)$ of the algorithm's choosing. This work appeared in CCC, 2011.

Hardness Results of Learning Low-Degree Polynomial Threshold Functions

Hardness results for maximum agreement problems have close connections to hardness results for proper learning in computational learning theory. In this paper, together with Ilias Diakonikolas (Berkeley), Ryan O'Donnell (CMU) and Rocco Servedio (Columbia), Yi Wu proves two hardness results for the problem of finding a low degree polynomial threshold function (PTF) which has the maximum possible agreement with a given set of labeled examples in $\reals^n \rightarrow \{-1,1\}$. The authors prove that for any constants $d, \epsilon > 0, i$) Assuming the Unique Games Conjecture, no polynomial-time algorithm can find a degree-$d$ PTF that is consistent with a $1/2+ \epsilon$ fraction of a given set of labeled examples in $\reals^n \rightarrow \{-1,1\}$, even if there exists a degree-$d$ PTF that is consistent with a $1-\epsilon$ fraction of the examples. It is NP-hard to find a degree-$2$ PTF that is consistent with a 1/2+ \epsilon fraction of a given set of labeled examples in $\reals^n \rightarrow \{-1,1\}$, even if there exists a halfspace (degree-$1$ PTF) that is consistent with a $1 - \epsilon$ fraction of the examples. These results immediately imply the following hardness of learning results: (i) Assuming the Unique Games Conjecture, there is no better-than-trivial proper learning algorithm that agnostically learns degree-$d$ PTFs under arbitrary distributions; (ii) There is no better-than-trivial learning algorithm that outputs degree-$2$ PTFs and agnostically learns halfspaces (i.e. degree-$1$ PTFs) under arbitrary distributions.

Is Submodularity Testable?

C. Seshadhri and Jan Vondrak study a new question, whether the submodularity is efficiently testable in the sense of property testing. I.e., given a value oracle for an unknown function, can we distinguish submodular functions from those that are $\epsilon$-far from submodular? Distance is measured here by the fraction of values that must be modified to make a function submodular. Seshadhri and Vondrak give partial answers to this question: they present a tester whose running time is $1/\epsilon^{O(\sqrt{n} \log n)}$. On the other hand, they show that this tester requires at least $1/\epsilon^{4.8}$ queries. A new construction of submodular functions using lattices is used in the lower bound. This work appeared in ICS 2011.

Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners

Given a directed graph $G = (V,E)$ and an integer $k \geq 1$, a {\it $k$-transitive-closure-spanner ($k$-TC-spanner)} of $G$ is a directed graph $H = (V, E_H)$ that has (1)~the same transitive-closure as $G$ and (2) diameter at most~$k$. Transitive-closure spanners are a common abstraction for applications in access control, property testing and data structures. Arnab Bhattacharyya (MIT), Elena Grigorescu (MIT), Madhav Jha (Penn State), Kyomin Jung (KAIST), and David Woodruff show a connection between $2$-TC-spanners and local monotonicity reconstructors. A local monotonicity reconstructor, introduced by Saks and Seshadhri (SIAM Journal on Computing, 2010), is a randomized algorithm that, given access to an oracle for an almost monotone function $f : [m]^d \to \mathbb{R}$, can quickly evaluate a related function $g : [m]^d \to \mathbb{R}$ which is guaranteed to be monotone. Furthermore, the reconstructor can be implemented in a distributed manner. They show that an efficient local monotonicity reconstructor implies a sparse 2-TC-spanner of the directed hypergrid (hypercube), providing a new technique for proving lower bounds for local monotonicity reconstructors. They present tight upper and lower bounds on the size of the sparsest 2-TC-spanners of the directed hypercube and hypergrid. These bounds imply tighter lower bounds for local monotonicity reconstructors that nearly match the known upper bounds. Work appeared in RANDOM, 2010.

Lower Bounds for Three-Query Locally Decodable Codes Over any Field

A linear $(q, \delta, \epsilon, m(n))$-locally decodable code (LDC) $C: \mathbb{F}^n \rightarrow \mathbb{F}^{m(n)}$ is a linear transformation from the vector space $\mathbb{F}^n$ to the space $\mathbb{F}^{m(n)}$ for which each message symbol $x_i$ can be recovered with probability at least $\frac{1}{|\mathbb{F}|} + \epsilon$ from $C(x)$ by a randomized algorithm that queries only $q$ positions of $C(x)$, even if up to $\delta m(n)$ positions of $C(x)$ are corrupted. Dvir shows that lower bounds for linear LDCs can imply lower bounds for arithmetic circuits. He suggests that proving lower bounds for LDCs over the complex or real field is a good starting point for approaching one of his conjectures. David Woodruff shows an $m(n) = \Omega(n^2)$ lower bound for linear $3$-query LDCs over any, possibly infinite, field. The constant in the $\Omega(\cdot)$ depends only on $\eps$ and $\delta$. This is the first lower bound better than the trivial $m(n) = \Omega(n)$ for arbitrary fields and more than two queries. Work appeared in RANDOM, 2010.

Non-uniform Circuit Lower Bounds

Ryan Williams has proved new lower bounds in complexity theory, showing that the complexity class $NTIME[2^n]$ (nondeterministic exponential time) does not have $ACC$ circuits of polynomial size. The proof can be extended to exponential size lower bounds for the class $EXP^{NP}$ (exponential time with an $NP$ oracle). His proof is the first that gives nontrivial superpolynomial lower bounds for $ACC$, which represented a barrier in the area of circuit complexity for over 20 years. The proof builds on his earlier paper "Improving exhaustive search implies superpolynomial lower bounds", connecting ideas from algorithms and complexity theory. At a high level, the proof designs faster algorithms for checking the satisfiability of $ACC$ circuits, and applies these algorithms in a complexity-theoretic way to prove that small circuits cannot exist. The paper appeared in CCC, 2011.

Optimal Lower Bounds for Locality Sensitive Hashing (Except when q is Tiny)

In work with Ryan O'Donnell (CMU) and Yuan Zhou (CMU), Yi Wu studies lower bounds for Locality Sensitive Hashing (LSH) in the strongest setting: point sets in $\{0,1\}^d$ under the Hamming distance. Recall that here $H$ is said to be an $(r, cr, p, q)$-sensitive hash family if all pairs $x,y$ in ${0,1}^d$ with $dist(x,y) \leq r$ have probability at least $p$ of collision under a randomly chosen $h$ in $H$, whereas all pairs $x,y$ in $\{0,1\}^d$ with $dist(x,y) \geq cr$ have probability at most $q$ of collision. Typically, one considers $d \rightarrow \infty$, with $c > 1$ fixed and $q$ bounded away from $0$. For its applications to approximate nearest neighbor search in high dimensions, the quality of an LSH family $H$ is governed by how small its "rho parameter" $\rho = \ln(1/p)/\ln(1/q)$ is as a function of the parameter $c$. The seminal paper of Indyk and Motwani showed that for each $c \geq 1$, the extremely simple family $H = \{x \mapsto x_i : i in d\}$ achieves $\rho \leq 1/c$. The only known lower bound, due to Motwani, Naor, and Panigrahy, is that $\rho$ must be at least $(e^{1/c}-1)/(e^{1/c}+1)\geq .46/c (minus o_d(1))$. In this paper the authors show an optimal lower bound: $\rho$ must be at least $1/c$ (minus $o_d(1)$). This lower bound for Hamming space yields a lower bound of $1/c^2$ for Euclidean space (or the unit sphere) and $1/c$ for the Jaccard distance on sets; both of these match known upper bounds. The authors' proof is simple; the essence is that the noise stability of a boolean function at $e^{-t}$ is a log-convex function of $t$. Like the Motwani--Naor--Panigrahy lower bound, the proof relies on the assumption that $q$ is not `tiny', meaning of the form $2^{-Theta(d)}$. Some lower bound on $q$ is always necessary, as otherwise it is trivial to achieve $\rho = 0$. The range of $q$ for which the authors' lower bound holds is the same as the range of $q$ for which $\rho$ accurately reflects an LSH family's quality. Still, the authors conclude by discussing why it would be more satisfying to find LSH lower bounds that hold for tiny $q$.

Pricing Loss Leaders Can Be Hard

Yi Wu considers the problem of pricing n items under an unlimited supply with $m$ single minded buyers, each of which is interested in at most $k$ of the items . The goal is to price each item with profit margin $p_1,p_2,...,p_n$ so as to maximize the overall profit. There is an $O(k)$-approximation algorithm by Blum and Balcan when the price on each item must be above its margin cost; i.e., each $p_i>0$. Yi investigates the above problem when the seller is allowed to price some of the items below their margin cost. It was shown in [BB06, BBCH08] that by pricing some of the items below cost, the seller could possibly increase the maximum profit by $\Omega(\log n)$ times. These items sold at low prices to stimulate other profitable sales are usually called "loss leader". It is unclear what kind of approximation guarantees are achievable when some of the items can be priced below cost. Understanding this question is posed as an open problem in [BB06]. In this paper, Yi gives a strong negative result for the problem of pricing loss leaders . Yi proves that assuming the Unique Games Conjecture (UGC), there is no constant approximation algorithm for item pricing with prices below cost allowed even when each customer is interested in at most $3$ items. Conceptually, Yi's result indicates that although it is possible to make more money by selling some items below their margin cost, it can be computationally intractable to do so. This work appeared in ICS, 2011.

Secure Computation with Information Leaking to an Adversary

Assume that Alice is running a program $P$ on a RAM $M$, and an adversary Bob would like to get some information about the input of the program. Sometimes Bob is able to see the contents and addresses of the registers involved in the instruction which is executed. Call a time when this happens a compromised time. Bob can choose the compromised times in an adaptive way, that is, immediately before the instruction at time $t$ is executed, Bob, using all of the information at his disposal, can decide whether time $t$ will be compromised or not. The only restriction on his choice is, that among $m$ consecutive instructions there can be at most $\epsilon m$ whose time is compromised, where $\epsilon>0$ is a small constant. In this work Miki Ajtai shows that Alice can replace the program $P$ with a program $P'$ with the same input/output, and which has the property that with high probability Bob will not gain any information about the input and the output of $P$. A similar theorem is also proved about computation done by circuits. Namely, in this case Alice is doing the computation by a boolean circuit $C$ and Bob learns the output of each gate of the circuit with a probability of $\epsilon$. It is proved in the paper that Alice can replace each circuit $C$ by an input/output equivalent circuit $C'$ so that Bob, with high probability, will not gain any information about the input of the circuit $C'$.

Subcubic Equivalences Between Path, Matrix, and Triangle Problems

Virginia Vassilevska Williams (UC Berkeley) and Ryan Williams present a new strategy for efficiently computing matrix products over algebraic structures used in optimization. An algorithm on n x n matrices (or n-node graphs) is truly subcubic if it runs in $O(n^{3-\varepsilon} poly(log M))$ time for some $\varepsilon > 0$, where $M$ is the largest absolute value of a matrix entry (or an edge weight). This work gives a complexity-theoretic characterization of many fundamental problems in graph and matrix algorithms: all-pairs shortest paths, replacement paths, checking if a matrix is a metric, minimum weight triangle, and others, are all equivalent under truly subcubic reductions. Hence either all of these problems can be solved in truly subcubic time, or none of them can. These results appeared in FOCS 2010.

Sublinear Optimization for Machine Learning

Ken Clarkson, Elad Hazan, and David Woodruff give sublinear-time approximation algorithms for some optimization problems arising in machine learning, such as training linear classifiers and finding minimum enclosing balls. Their algorithms can be extended to some kernelized versions of these problems, such as SVDD, hard margin SVM, and $L_2$-SVM, for which sublinear-time algorithms were not known before. These new algorithms use a combination of a novel sampling techniques and a new multiplicative update algorithm. They also give lower bounds which show the running times of many of their algorithms to be nearly best possible in the unit-cost RAM model. They also give implementations of their algorithms in the semi-streaming setting, obtaining the first low pass polylogarithmic space and sublinear time algorithms achieving arbitrary approximation factor. Work appeared in FOCS, 2010.

The Matroid Secretary Problem and its Variants

In the matroid secretary problem, the elements of a matroid are arriving on-line and their weights are revealed one-by-one. An algorithm has to commit to selecting or rejecting each element when it arrives. The goal is to select a maximum-weight set independent in the matroid. A conjecture by Babaioff et al. from 2007 is that there is a constant-factor competitive algorithm for this problem, generalizing several variants of the classical secretary problem. A related variant of the conjecture has been resolved recently by Jose Soto, who showed that if weights are assigned to elements randomly, a constant factor can be achieved. S. Oveis-Gharan (student at Stanford, intern at IBM) and Jan Vondrak show that if weights are assigned to elements randomly, the on-line ordering of elements can be adversarial rather than random and a constant factor can be still achieved. Work in progress.

The Structure of Inverses in Schema Mappings

A schema mapping is a specification that describes how data structured under one schema (the source schema) is to be transformed into data structured under a different schema (the target schema). The notion of an inverse of a schema mapping is subtle, because a schema mapping may associate many target instances with each source instance, and many source instances with each target instance. In PODS 2006, Ron Fagin defined a notion of the inverse of a schema mapping, that is now considered the "gold standard" for invertibility (weaker notions have been defined since then, in order to help cover cases where there is no inverse). Ron Fagin and Alan Nash, resolved the key open problem of the complexity of deciding whether there is an inverse (they showed that the problem is coNP-complete, whereas before it was not even known to be decidable). They explored a number of interesting questions about inverse schema mappings, including: What is the structure of an inverse? When is the inverse unique? How many nonequivalent inverses can there be? When does an inverse have an inverse? How big must an inverse be? Surprisingly, these questions are all interrelated. For the widely studied "GAV (Global-as-View)" schema mappings, they gave a polynomial-time algorithm that produces an inverse when one exists. They introduced the notion of "essential conjunctions", and showed that essential conjunctions play a crucial role in the study of inverses. They used them to give greatly simplified proofs of some known results about inverses. What emerges is a much deeper understanding about this fundamental and complex operator. This work appeared in JACM.

Awards and Honors

Ryan Williams' paper "Improving exhaustive search implies superpolynomial lower bounds" was invited to the special issue of SIAM Journal on Computing devoted to the best papers of STOC 2010.

David Woodruff was invited to visit University of Dortmund (TU Dortmund) for two weeks in September, 2010 to continue ongoing collaboration.

Publications and Conferences

S. Agrawal, N. Megiddo and B. Armbruster, “Equilibrium in Prediction Markets with Buyers and Sellers,” Economics Letters 109 (2010), No. 1 (October), 46 – 49.

Arnab Bhattacharyya, Elena Grigorescu, Madhav Jha, Kyomin Jung, Sofya Raskhodnikova, and David Woodruff, "Lower Bounds for Local Monotonicity Reconstruction from Transitive-Closure Spanners", Approx/Random, 2010.

Balder ten Cate, Phokion G. Kolaitis, Wang-Chiew Tan, "Database Constraints and Homomorphism Dualities", Proceedings of 16th International Conference on Principles and Practice of Constraint Programming (CP 2010), September 2010, pp, 475-490.

C. Chekuri, J. Vondrak, R. Zenklusen. Dependent randomized rounding via exchange properties of combinatorial structures, 51st IEEE FOCS (2010).

Kenneth Clarkson, Elad Hazan, and David Woodruff, "Sublinear Optimization for Machine Learning", FOCS, 2010.

Ron Fagin and Alan Nash, The structure of inverses in schema mappings. J. ACM 57, 6, Oct. 2010, Article 31.

N. Megiddo, “Towards a formal analysis of emotions in games,” Research Report RJ 10474, IBM Almaden Research Center, San Jose, CA, 10/22/2010.

B. Sudakov and J. Vondrak. A randomized embedding algorithm for trees, Combinatorica 30:4 (2010), 445-470.

Virginia Vassilevska Williams and Ryan Williams. Subcubic equivalences between path, matrix, and triangle problems. In IEEE Symposium on Foundations of Computer Science (FOCS), 2010.

David Woodruff, "Additive Spanners in Nearly Quadratic Time", ICALP, 2010.

David Woodruff, "A Quadratic Lower Bound for Three-Query Linear Locally Decodable Codes", Approx/Random, 2010.

Patents and Patent Applications

R. Fagin, P. Kolaitis, L. Popa, and W.-C Tan. U.S. 7783680, "Quasi-Inverses of Schema Mappings" 08/24/2010.

R. Fagin, P. Kolaitis, L. Popa, W.-C Tan, and C. Yu. US 7,783,680, "Sequential Composition of XML Schema Mappings" 10/24/2010.

E. Hazan, and N. Megiddo, "Fast Adaptation In Real-Time Systems" ARC920100024US1, filed 6/30/2010.

N. Megiddo. U.S. 7,765,140 "System for Enhancing Buyers Performance in Electronic Commerce" 7/27/2010.

D. Woodruff, "A Method for Two Parties to Privately Estimate Similarity of Their Datasets" ARC820100022

Presentations and Seminars

  • Phokion Kolaitis, "Random Graphs and the Parity Quantifier", Invited talk, Set Theory, Model Theory, Generalized Quantifiers, and Foundations of Mathematics, Meeting in Honor of Jouko Vaananen's 60th Birthday, Helsinki, Finland, September, 2010
  • Nimrod Megiddo, "Some Challenges in the Application of Game Theory", Invited talk at Croucher Advanced Study Institute on Theory and Applications of Algorithmic Game Theory (ASI 2010), July 20, 2010
  • Nimrod Megiddo, "Some Challenges in the Application of Game Theory", Plenary presentation at the Sixth Workshop on Internet & Network Economics (WINE 2010), December 13, 2010
  • Jan Vondrak, "Multilinear relaxation: a tool for maximization of submodular functions", Neural Information Processing Systems, Whistler, BC, Canada, December 2010
  • Ryan Williams, "Non-Uniform ACC Circuit Lower Bounds", UC Berkeley, November 2010; MIT, November 2010; MSR New England, December 2010; Princeton, December 2010; MSR Silicon Valley, December 2010
  • Ryan Williams, "Improving Exhaustive Search Implies Superpolynomial Lower Bounds", Schloss Dagstuhl (Germany), November 2010
  • Ryan Williams, "A Survey of Time-Space Lower Bounds for NP-Hard Problems", Stanford, October 2010
  • David Woodruff, "Fast Robust Regression in Data Stream", Universite Paris-Sud theory seminar, July, 2010,
  • David Woodruff, "Fast Robust Regression in Data Streams", University of Utah theory seminar, August, 2010
  • David Woodruff, "Efficient Sketches for Earth-Mover Distance, with Applications", Technical University of Dortmund theory seminar, August, 2010
  • David Woodruff, "An Optimal Algorithm for the Distinct Elements Problem", DIMACS Workshop on Network Data Streaming and Compressive Sensing, October, 2010

Committee Work

  • Vitaly Feldman, Program Committee, Symposium on Discrete Algorithms (SODA), January 2011.
  • Ryan Williams, Program Committee, International Symposium on Parameterized and Exact Computation, December 2010.
  • Ryan Williams, Program Committee, Symposium on Theory of Computing, June 2011.

Editorships

External Positions
  • Jan Vondrak
    Visiting Faculty, Dept. of Computer Science, Stanford University, Fall 2010.

Miscellaneous

Ryan Williams was a moderator for CSTheory, a Q&A site for researchers in theoretical computer science Located at cstheory.stackexchange.com

Phokion Kolaitis gave an invited short course "Relational Databases, Logic, and Complexity", Sino-European School on Logic, Language, and Information (SELLC '10, Guangzhou, China, December 2010.

Jan Vondrak taught "Polyhedral techniques in combinatorial optimization", a graduate course in computer science, Stanford University, Fall 2010.

Research Interests

  • M. Ajtai: Complexity theory, combinatorics, and logic, and the connections between them
  • K. Clarkson: Computational geometry, design and analysis of algorithms, optimization
  • R. Fagin: Applications of logic to computer science, reasoning about knowledge, database theory, finite-model theory
  • V. Feldman: Learning theory, computational models of the brain, complexity theory
  • E. Hazan: Online learning, optimization, computational finance, game theory
  • T. S. Jayram: Complexity theory, algorithms for massive data sets, probabilistic databases
  • B. Kimelfeld: Database theory, XML, query optimization, enumeration algorithms and complexity, probabilistic databases, incomplete information, ranking techniques, information retrieval
  • P. Kolaitis: Logic in computer science, database theory, computational complexity
  • N. Megiddo: Mathematical programming, algorithms and complexity, game theory, machine learning
  • C. Seshadhri: Sublinear algorithms and property testing, approximation algorithms, computational geometry, machine learning
  • R. Williams: Algorithms and complexity theory
  • D. Woodruff: Algorithms, complexity theory, and cryptography
  • Y. Wu: Hardness of approximation

Organization

  • Ken Clarkson, Senior Manager, CS Principles and Methodologies
  • Rene Henthorn (Administrative Assistant)
  • Ron Fagin, Manager, Foundations of Computer Science
  • T. S. Jayram, Manager, Algorithms and Computation
  • Miki Ajtai
  • Vitaly Feldman
  • Elad Hazan
  • Benny Kimelfeld (postdoctoral scholar)
  • Phokion Kolaitis
  • Nimrod Megiddo
  • C. Seshadhri (postdoctoral scholar)
  • Ryan Williams(Raviv postdoctoral scholar)
  • David Woodruff
  • Yi Wu (postdoctoral scholar)

Activity Reports