Semidefinite and Matrix Methods for Optimization and Communication - IMS

Semidefinite and Matrix Methods for Optimization and Communication
(18 Jan - 28 Feb 2016)

~ Abstracts ~

A short overview of algebraic and semialgebraic proof complexity
Albert Atserias, Universitat Politécnica de Catalunya, Spain

Propositional proof complexity studies the size of proofs in well-known proof systems for propositional logic. One of the most basic and best studied such proof systems is resolution, and there the concept of "width" plays a very important role for its understanding. Originally motivated by the fact that resolution and similar proof systems that operate with low-depth formulas lack the ability to efficiently formalize counting arguments, in the late 1990's and early 2000's the area moved to studying so-called algebraic and semi-algebraic proofs systems. These are systems that operate with polynomial equalities and inequalities, and there an appropriate concept of "rank" (which is closely related to the standard notion polynomial degree) plays a role that is somewhat analogue to width in resolution. In recent years we have seen a reemergence of semialgebraic proof systems in the context of approximation algorithms and combinatorial optimization, and somewhat surprisingly, the methods of proof complexity, and in particular the methods surrounding width in resolution, turned out to be quite useful there too. This talk will be a short overview of how this is the case.

Fast algorithms for optimising over unentangled states: SDP hierarchies vs eps-nets
Fernando Brandao, Microsoft Research, USA

In the talk I'll discuss algorithms for a central problem in quantum information theory: To optimise over the set of separable (unentangled) states. I'll outline how this problem is connected to several others (from computing the capacity of a quantum channel to the unique games and small set expansion problems). Then I'll discuss the state-of-the-art in solving it. I'll show how the Sum-of-Squares hierarchy (aka Lasserre Hierarchy) can be used to give the fastest known algorithm for optimizing over the set of separable states. I'll review the proof that the hierarchy solves it quickly, which is based on ideas from quantum information theory. Finally I'll discuss a recent alternative approach to the problem, based on enumerating over carefully chosen eps-nets, which matches the performance of the Sum-of-Squares hierarchy.

Quantum information and the the round complexity of disjointness
Ankit Garg, Princeton University, USA

I will give an overview of quantum information complexity, a notion recently introduced by Touchette. It holds the promise of helping tackle direct sum and direct product questions for quantum communication complexity. As an application, I will describe a recent result on the optimal round-communication tradeoffs for the quantum communication complexity of disjointness. The result on disjointness is joint work with Mark Braverman, Young Kun Ko, Jieming Mao and Dave Touchette.

On quantum vs. classical communication complexity
Dmitry Gavinsky, The Czech Academy of Sciences, Prague, Czech Republic

The setting of communication complexity is one of the strongest computational models, as of today, where people have tools to prove "hardness" - that is, where problems are known that don't have efficient solutions. This allows, in particular, to compare the computational power of two communication regimes via demonstrating that certain problem has an efficient solution in one regime, but not in the other. Many researchers have applied this methodology to argue qualitative advantage of quantum over classical communication models; this talk aims to survey some old and new results.

Classical approximation algorithms for quantum constraint satisfaction problems
Sevag Gharibian, Virginia Commonwealth University, USA

The study of approximation algorithms for Boolean satisfiability problems such as MAX-k-SAT is a well-established line of research. In the quantum setting, there is a physically motivated generalization of MAX-k-SAT known as the k-Local Hamiltonian problem (k-LH), which is of interest for two reasons: From a complexity theoretic perspective, k-LH is complete for the quantum analogue of NP, and from a physics perspective, k-LH asks one to estimate the energy of a quantum system when cooled to very low temperatures. For the latter reason in particular, the condensed matter physics community has devoted decades to developing heuristic algorithms for k-LH and related problems. However, recent years have witnessed the development of the first classical approximation algorithms for k-LH, which shall be the focus of this talk. We will begin with an introductory overview of some existing results, with no background in quantum computing assumed. We will then discuss recent work in progress on generalizing the celebrated Goemans-Williamson algorithm for MAX-CUT to approximate physically motivated special cases of k-LH. The latter is joint work with Yi-Kai Liu (NIST, USA).

Extended formulations and circuit complexity
Mika Goos, University of Toronto, Canada

What is the connection between these two results?

(1) Rothvoss's extension complexity lower bound for the perfect matching polytope.
(2) Raz-Wigderson lower bound for the monotone depth of the perfect matching function.

I claim that (1) implies (2) in a simple black-box fashion. More generally, I will discuss a (new?) connection between extended formulations (EF) and Karchmer- Wigderson games. For example, this connection suggests an approach to proving higher EF lower bounds for explicit polytopes (e.g., independent set polytopes). Moreover, the connection highlights a *barrier* to proving EF lower bounds for a large class of matroid polytopes: any lower bound for an explicit "sparse paving" matroid would imply (non-monotone!) circuit depth lower bounds.

A lower degree bound for the real Nullstellensatz and pseudo-densities with minimal norm
Sebastian Gruler, University of Konstanz, Germany

In 2001, Grigoriev gave a lower degree bound for a "Real Nullstellensatz" infeasibility certificate for sum_{i=1}^n x_i-n/2= 0 and x in {0,1}^n$ using a separating linear functional. This result plays an important role in the recent work of Lee, Raghavendra and Steurer, where they prove a lower bound on the psd-rank for the correlation polytope. In their work, they use a so called pseudo-density, that represent the linear functional of Grigoriev and they are interested in pseudo-densities with small norm.

In my talk, I will first give a new easy proof of the result of Grigoriev and then I will show, that the pseudo-density, used by L-R-S, is the best you can hope for. That means, it has the smallest norm of all pseudo-densities satisfying certain properties.

Towards the sliding scale conjecture: old and new PCP constructions
Prahladh Harsha, Tata Institute of Fundamental Research, India

The PCP theorem (AS,ALMSS 1991) is a cornerstone of theoretical computer science, which describes how any NP proof can be made robust which has strong consequences for hardness of approximation. It guarantees that every NP language has a probabilistically checkable proof (PCP) system allowing a verifier to check a witness very eciently using randomness, and allowing for small error. In this talk, I'll revisit some of the older constructions of PCP and analyze them using the more modern modular composition approach. This will allow us to make (some) progress towards the "sliding-scale conjecture" of Bellare-Goldreich-Lund-Russel from 1993. This conjecture states that there exist polynomial sized constant query PCPs with inverse polynomially small error.
Based on joint work with Irit Dinur and Guy Kindler

Factor-11/8 NP-inapproximability for 2-variable linear equations
Sangxia Huang, École Polytechnique Fédérale de Lausanne, Switzerland

An instance of the E2-Lin(2) problem is a system of equations of the form xi + xj = b(mod2). Given such a system in which it is possible to satisfy all but an epsilon fraction of the equations, we would like to find an assignment that violates as few equations as possible. In this paper, we show that it is NP-hard to satisfy all but a C*epsilon fraction of the equations, for any C < 11/8 and 0 < epsilon <= 1/8. Our result holds also for the special case of Max-Cut. The previous best NP-hardness result, standing for over 15 years, had 5/4 in place of 11/8. We also give a conjecture concerning analysis of Boolean functions which, if true, would yield a larger hardness factor of 3/2.

Our proof is by a modified gadget reduction from a predicate that supports a pairwise independent distribution. We also show an inherent limitation to this type of gadget reduction. In particular, we show that no such reduction can establish a hardness factor C greater than 2.54.

Joint work with Johan Hastad, Rajsekar Manokaran, Ryan O'Donnell, John Wright.

A composition theorem for conical juntas with applications to query and communication complexity
T.S. Jayram, IBM Almaden Research Center, USA

We describe a general method of proving degree lower bounds for conical juntas (nonnegative combinations of conjunctions) that compute recursively defined boolean functions. Such lower bounds are known to carry over to communication complexity. We give two applications:

AND-OR trees: We show a near-optimal \Omega~(n^{0.753...}) randomized communication lower bound for the recursive NAND function (a.k.a. AND-OR tree). This answers an open question posed by Beame and Lawry 1992,1993.

Recursive Majority: We show an \Omega(2.59^k) randomized communication lower bound for the 3-majority tree of height k. This improves over the state-of-the-art already in the context of randomised decision tree complexity.

Joint with Mika Goos (U. Toronto)

Relative discrepancy does not separate information and communication complexity
Iordanis Kerenidis, Université Paris Diderot, France

Does the information complexity of a function equal its communication complexity? We examine whether any currently known techniques might be used to show a separation between the two notions. Recently, Ganor et al. provided such a separation in the distributional setting for a specific input distribution ?. We show that in the non- distributional setting, the relative discrepancy bound they defined is, in fact, smaller than the information complexity, and hence it cannot be used to separate information and communication complexity. In addition, in the distributional case, we provide an equivalent linear program formulation for relative discrepancy and relate it to variants of the partition bound, resolving also an open question regarding the relation of the partition bound and information complexity. Last, we prove the equivalence between the adaptive relative discrepancy and the public-coin partition bound, which implies that the logarithm of the adaptive relative discrepancy bound is quadratically tight with respect to communication.

Almost optimal sum of squares lower bounds for planted clique
Pravesh Kothari, The University of Texas at Austin, USA

This talk is about an almost optimal lower bound for any polynomial time algorithm (any constant round/degree) from the Sum of Squares hierarchy for the planted clique problem. In this problem, the input is a random graph to which, a clique of size w is added. The question is to determine the smallest w such that an efficient algorithm can recover the vertices in the added clique. Investigating the power of the Sum of Squares method for the problem was begun by a recent work of Raghu Meka and Avi Wigderson (2015). A key component our proof is the construction of a canonical lower bound witness for planted clique: a feasible solution for the SoS program that certifies that the algorithm "thinks" there is a √n size clique in a random G(n, 1=2) graph with high probability. This construction immediately extends to other similar problems and will likely be useful for showing new SoS lower bounds.
This is based on joint works with Boaz Barak, Sam Hopkins, Jon Kelner, Ankur Moitra and Aaron Potechin.

Lower bounds on the size of semidefinite programming relaxations
James R. Lee, University of Washington, USA

Semi-definite extended formulations are a powerful, general, and geometrically appealing model for SDP characterizations and relaxations of polytopes. The SDP variant of Yannakakis' factorzation theorem connects such formulations to the positive semi-definite rank of associated matrices.

Understanding the notion of PSD rank and, in particular, the PSD rank of matrices that arise in combinatorial optimization has proved to be a challenging and rewarding task. In this lecture series, we present a proof that classical polytopes (like the CUT and TSP polytopes) do not admit semi-definite characterizations of sub-exponential size.

This is done by relating such SDPs to specific families of formulations coming from the sum-of-squares hierarchy. In exploring this connection, we will see non-trivial connections to proof complexity, communication complexity, quantum information theory, approximation theory, and online convex optimization.

[These lectures are based on a series of joint works with Prasad Raghavendra and David Steurer.]

Approximate sum-of-squares degree
Troy Lee, Nanyang Technological University and National University of Singapore

We study the degree of sum-of-squares (sos) polynomials needed to approximate functions over the boolean cube. In particular, we look at a family of symmetric quadratic functions and study both the average error and the worst case error for approximation by sos polynomials. For this family of functions, we give upper bounds on the average error achievable by degree n/10 sos polynomials which imply that the semidefinite extension lower bounds on the correlation polytope by Lee, Raghavendra, and Steurer cannot be improved in a black box manner. For constant worst case error we tightly characterize degree needed by sos polynomials to approximate the functions in this family.

The log-rank conjecture: recent progress and future directions
Shachar Lovett, University of California, San Diego, USA

The log-rank conjecture, proposed by Lovasz and Saks in 1988, speculates that the optimal deterministic communication complexity for any total two-player boolean function, can be approximated (up to polynomial factors) by log of the rank of its associated matrix. Extensions of the conjecture to more powerful communication models, such as randomized or quantum protocols, were also later suggested. This conjecture is still far from resolved, and the tutorial will cover some recent progress on the conjecture, as well as its relation to problems arising in combinatorics, additive number theory and geometry.

The tutorial will consist of four talks:

Talk 1: background, basic reductions
Talk 2: an approach based on additive number theory
Talk 3: an approach based on factorization norms
Talk 4: special families of functions

Nonuniform graph partitioning with unrelated weights
Yury Makarychev, Toyota Technological Institute at Chicago, USA

We give a bi-criteria approximation algorithm for the Minimum Nonuniform Partitioning problem, recently introduced by Krauthgamer, Naor, Schwartz, and Talwar (2014). In this problem, we are given a graph G = (V;E) on n vertices and k numbers r1,. . . , rk. The goal is to partition the graph into k disjoint sets P1, . . ., Pk satisfying |P_i| r_in so as to minimize the number of edges cut by the partition. Our algorithm has an approximation factor of O(√ (log n log k)) for general graphs and an O(1) approximation for graphs with excluded minors. This is an improvement upon the O(log n)-approximation algorithm of Krauthgamer, Naor, Schwartz, and Talwar (2014). Our approximation factor matches the best known factor for the Minimum (Uniform) k-Partitioning problem. We extend our results to the case of "unrelated weights" and to the case of "unrelated d-dimensional weights".
Joint work with Konstantin Makarychev

Beyond worst case analysis of graph partitioning algorithms
Konstantin Makarychev, Microsoft Research, USA

Many combinatorial optimization problems are much simpler in practice than in the worst-case. One of the challenges in the area of approximation algorithms is to explain this phenomena and to design algorithms that work well in real-life. In this talk, we will first discuss dierent ways of modelling ?real-life? instances. Then, I will present a new semi-random semi-adversarial model for graph partitioning problems, a planted model with permutation-invariant random edges (PIE). This model is much more general than stochastic models considered previously. Finally, I will describe a ?constant factor? approximation algorithm for finding the minimum balanced cut in graphs from this model. The algorithm uses semidefinite programming. Joint work with Yury Makarychev and Aravindan Vijayaraghavan.

Sign-rank, machine learning, and communication complexity
Shay Moran, Technion - Israel Institute of Technology, Israel

The sign rank of a sign matrix A is the minimum possible rank of a real matrix S that has the same sign pattern like A. The sign rank is known to capture basic complexity measures in communication complexity and in machine learning. We will discuss the role of the sign-rank in these fields and demonstrate how an attempt to explain the practical efficiency of kernel based learning algorithms gives rise to basic open questions about the sign-rank, and that these questions have natural interpretations in communication complexity.

Limitations of monogamy, Tsirelson-type bounds, and other semidefinite programs in quantum information
Anand Natarajan, Massachusetts Institute of Technology, USA

We show that semidefinite programs (SDPs) have limited ability to approximate two particularly important
sets in quantum information theory:
1. The set of separable (i.e. unentangled) states.
2. The set of quantum correlations; i.e. conditional probability distributions achievable with local measurements on a shared entangled state.

The former result implies a proof of a version of the ?no approximate disentangler? conjecture of Watrous and a no-go theorem for SDP relaxations of the 2 ? 4 norm of a matrix, while the latter is the first unconditional negative result for SDP relaxations of noncommutative polynomial optimization. Our unconditional results achieve the same parameters as previous conditional results that used the Exponential-Time Hypothesis, and show that any SDPs which approximately solve either of these problems must have a number of variables which grows very quickly with problem size.

These results can be viewed as limitations on various ideas from quantum information (including the monogamy principle, the PPT test, Tsirelson-type inequalities) for understanding entanglement. Many of these ideas have been formalized into SDP hierarchies by Doherty-Parrilo-Spedalieri, Navascues-Pironio-Acin and Berta-Fawzi-Scholz, all of which we establish limits on the eectiveness of.

Our techniques are based on reductions between integrality gaps. This allows the recent integrality gaps of Lee-Raghavendra-Steurer to be extended to a wide range of problems, without needing to redo their use of Fourier analysis to non-boolean domains.

Joint work with Aram Harrow and Xiaodi Wu.

A generalized method for proving polynomial calculus degree lower bounds
Jakob Nordström, KTH Royal Institute of Technology, Sweden

We study the problem of obtaining lower bounds for polynomial calculus (PC) and polynomial calculus resolution (PCR) on proof degree, and hence by [Impagliazzo et al. '99] also on proof size. [Alekhnovich and Razborov '03] established that if the clause-variable incidence graph of a CNF formula F is a good enough expander, then proving that F is unsatisfiable requires high PC/PCR degree. We further develop the techniques in [AR03] to show that if one can "cluster" clauses and variables in a way that "respects the structure" of the formula in a certain sense, then it is sufficient that the incidence graph of this clustered version is an expander. As a corollary of this, we prove that the functional pigeonhole principle (FPHP) formulas require high PC/PCR degree when restricted to constant-degree expander graphs. This answers an open question in [Razborov '02], and also implies that the standard CNF encoding of the FPHP formulas require exponential proof size in polynomial calculus resolution. Thus, while Onto-FPHP formulas are easy for polynomial calculus, as shown in [Riis '93], both FPHP and Onto-PHP formulas are hard even when restricted to bounded-degree expanders.

This is joint work with Mladen Miksa that appeared at CCC '15.

Random words, longest increasing subsequences, and quantum PCA
Ryan O'Donnell, Carnegie Mellon University, USA

Suppose you have access to i.i.d. samples from an unknown probability distribution $p = (p_1, ..., p_d)$ on $[d]$, and you want to learn or test something about it. For example, if you wants to estimate $p$ itself, then the empirical distribution will suffice when the number of samples, $n$, is $O(d/epsilon^2)$. In general, you can ask many more specific questions about $p$: Is it close to some known distribution $q$? Does it have high entropy? Etc. For many of these questions the optimal sample complexity has only been determined over the last $10$ years in the computer science literature.

The natural quantum version of these problems involves being given samples of an unknown $d$-dimensional quantum mixed state $\rho$, which is a $d \times d$ PSD matrix with trace $1$. Many questions from learning and testing probability carry over naturally to this setting. In this talk, we will focus on the most basic of these questions: how many samples of $\rho$ are necessary to produce a good approximation of it? Our main result is an algorithm for learning $\rho$ with optimal sample complexity. Furthermore, in the case when $\rho$ is almost low-rank, we show how to perform PCA on it with optimal sample complexity.

Surprisingly, we are able to reduce the analysis of our algorithm to questions dealing with the combinatorics of longest increasing subsequences (LISes) in random words. In particular, the main technical question we have to solve is this: given a random word $w \in [d]^n$, where each letter $w_i$ is drawn i.i.d. from some distribution $p$, what do we expect $\mathrm{LIS}(w)$ to be? Answering this question requires diversions into the RSK algorithm, representation theory of the symmetric group, the theory of symmetric polynomials, and many other interesting areas.

Hypercontractivity and sum of squares
Ryan O'Donnell, Carnegie Mellon University, USA

We will discuss the complexity of proving hypercontractivity, reverse hypercontractivity, and other "hypercube expansion" statements in the Sum-of-Squares proof system. The applications are to approximability of the Balanced-Separator, Vertex-Cover, and 3-Coloring problems.

Symmetrizing sum of squares polynomials on the hypercube
Anupam Prakash, Nanyang Technological University

We present a proof of a recent theorem due to Blekherman that characterizes the symmetrization of sums of squares polynomials on the hypercube. We use the theorem to provide a simple proof of Grigoriev's lower bound on the degree of Positivestellensatz refutations for the knapsack problem.

Strong reductions for extended formulations
Aurko Roy, Georgia Institute of Technology, USA

We generalize the reduction mechanism for linear programming problems and semidefinite programming problems from Braun, Pokutta and Zink in two ways 1) relaxing the requirement of affineness and 2) extending to fractional optimization problems. As applications we provide several new LP-hardness and SDP-hardness results, e.g., for the SparsestCut problem, the BalancedSeparator problem, the MaxCut problem and the Matching problem on 3-regular graphs. We also provide a new, very strong Lasserre integrality gap result for the IndependentSet problem, which is strictly greater than the best known LP approximation, showing that the Lasserre hierarchy does not always provide the tightest SDP relaxation.

Based on the manuscript: http://arxiv.org/abs/1512.04932 (to appear in IPCO 2016).

New results on the exactness of Lasserre relaxations for compact basic closed semialgebraic sets
Markus Schweighofer, University of Konstanz, Germany

In this talk we recall Lasserre's moment relaxation method for relaxing arbitrary finite systems of real polynomial non-strict inequalities in several variables. Solution sets of such systems are called basic closed semialgebraic sets. Lasserre's method consists in first adding certain families of valid inequalities and then linearizing them in a natural way. In the ideal case, this procedure leads to a linear matrix inequality (i.e. to a constraint of a semidefinite program) whose solution set is the convex hull of the original basic closed semialgebraic set. In this case, we say that the moment relaxation is exact. In two seminal papers, Helton and Nie proved around 2010 the exactness of the moment relaxation in many cases. Using new proof techniques involving non-archimedean real closed fields, we improve substantially the results of Helton and Nie. For example, we do away with technical assumptions in the case of compact convex basic closed semialgebraic sets and we extend their results to not necessarily connected sets with not necessarily convex connected components. In particular, we show that a single Lasserre relaxation works in many cases where Helton and Nie used a whole patchwork of local Lasserre relaxations in order to get a semidefinite lifting.
Joint work with Tom-Lukas Kriel.

PSD-minimal polytopes
Rekha Thomas, University of Washington, USA

The positive semidefinite rank of a polytope is the smallest k such that there is an affine slice of the k x k psd cone that projects onto the polytope. It is easy to see that the psd rank of a d-dimensional polytope is at least d+1 and we say that a polytope is psd minimal when its psd rank is exactly d+1. Psd-minimality of a polytope is not a combinatorial property and depends critically on the embedding. I will present a complete classification of psd minimal polytopes in
dimension up to four. I will also explain the techniques developed for this work which are interesting in their own right and connect to other parts of mathematics.

Joint work with Joao Gouveia, Kanstanstin Pashkovich and Richard Robinson.

Completely positive semidefinite rank
Antonios Varvitsiotis, National University of Singapore

A matrix X is called completely positive semidefinite (cpsd) if there exist d-by-d Hermitian positive semidefinite operators \{P_i\}_{i=1}^n (for some d\ge 1) such that X=trace(P_iP_j), for all i,j\in [n]. Given a cpsd matrix, its cpsd-rank is defined as the smallest d for which such a representation exists. The study of the cpsd-rank is motivated twofold: First, the cpsd-rank is a natural non-commutative analogue of the cp-rank of a completely positive matrix. Secondly, the study of the cpsd-rank admits natural physical motivation as it can be used to upper and lower bound the size of a quantum system needed to generate all quantum correlations corresponding to a Bell scenario. In this talk I will explain the connection to quantum correlations and I will present some recent results on the cpsd-rank.

Based on joint work with A. Prakash, J. Sikora and Z. Wei.

Rounding the sparsest cut SDP on low threshold-rank graphs
Rakesh Venkat, Tata Institute of Fundamental Research, India

Recently, there has been much progress on designing algorithms for graphs that are 'low threshold-rank', that is, they have the r-th eigenvalue of the Laplacian bounded away from zero, for a typically small value of r called the threshold-rank of the graph. The Sparsest-Cut problem is a fundamental problem in graph optimization that has been shown to have an O(1)-approximation on graphs of threshold-rank r using O(r) rounds of the Lasserre/SoS hierarchy of the natural SDP relaxation (requiring solving a n^O (r)-sized SDP). The best-known unconditional approximation, however, is due to Arora-Rao-Vazirani that uses just a basic SDP relaxation. We give a new, simple rounding technique for this basic SDP relaxation, that gives an O(r) approximation on graphs of threshold-rank r, and simultaneously furnishes a robust version of a theorem of Goemans regarding embedding low-dimensional negative-type metrics into l1. In contrast to the SoS-based algorithms, our algorithm (and its running time) is independent of the threshold-rank of the graph, and points to some interesting directions for progress. Joint work with Amit Deshpande and Prahladh Harsha

On the minimum dimension of a Hilbert space needed to generate a quantum correlation
Zhaohui Wei, National University of Singapore

Consider a two-party correlation that can be generated by performing local measurements on a bipartite quantum system. A question of fundamental importance is to understand how many resources, which we quantify by the dimension of the underlying quantum system, are needed to reproduce this correlation. In this talk, by combining a novel geometric characterization for the set of quantum correlations with techniques that were recently introduced to lower bound the PSD-rank, we give an easy-to-compute lower bound on the smallest Hilbert space dimension needed to generate a given two-party quantum correlation. We show that our bound is tight on the correlations generated in many famous quantum tasks.

A classification of the joint numerical range of three hermitian 3-by-3 matrices
Stephan Weis, Universidade Estadual de Campinas (Unicamp), Brazil

The joint numerical range of three hermitian 3-by-3 matrices is a three-dimensional convex and compact set equal to a dual spectrahedron, hence it has a positive semidefinite lift. We prove that the convex set is generically an oval. We divide the non-generic objects into groups with equal numbers of one- and twodimensional faces (segments and ellipses) and show that a complete graph is embedded into their union with one vertex on each face. Eleven numbers are possible, for eight of which we find and illustrate examples. If time allows I will make further comments on normal cones of dual spectrahedra.

This is joint work with Konrad Szymanski and Karol Zyczkowski (Jagiellonian University)

Parity decision tree complexity and 4-party communication complexity of XOR- functions are polynomially equivalent
Penghui Yao, University of Waterloo, Canada

In this talk, we study the relation between the parity decision tree complexity of a boolean function f and the k-party number-in-hand multiparty communication
complexity of the XOR functions F(x1,... xk)=f(x1+...+xk). We show that the parity decision tree complexity of f and communication complexity of F are polynomially equivalent whenever k>3. Our main tool is a recent result from additive combinatorics due to Sanders.

Log-rank conjecture for some special classes of functions
Shengyu Zhang, Chinese University of Hong Kong, Hong Kong

Logrank Conjecture is one of the most intriguing and challenging open problems in theoretical computer science. In this talk, we will review some recent progress on special classes of functions, with an emphasize on bit-wise composition of the two distributed inputs.

Best viewed with IE 7 and above