CS 591 B1: Communication Complexity, Fall 2019 Course Project Guidelines
The course project is an opportunity to perform an in-depth exploration of a topic in communication complexity that interests you. The goals are to gain experience
• Independently reading and synthesizing research papers,
• Presenting research papers to an audience of your peers, and • Formulating and carrying out a short-term research project.
You are not expected to produce publishable results by the end of the semester, but hopefully you will be able to lay the groundwork for something that can be further developed into publishable research. Projects may be done individually or in pairs. Some examples of possible projects include:
• Making progress on an open theoretical question in communication complexity,
• Applying known (or new!) communication lower bounds to another area that interests
you,
• Modeling a new communication problem that may not be captured by the current literature,
• Synthesizing several papers in the communication complexity literature (which were not covered in detail in class), or
• Something totally different! Be creative!
At the bottom of this document are several broad topic ideas with references to relevant papers. These are only intended for inspiration. You are highly encouraged to come up with your own topics, especially if they relate to your research interests. Please feel free to discuss your ideas with me and with each other throughout the semester, in office hours, by email, or on Piazza. Auditors are welcome to complete projects and collaborate with registered students.
To keep you on track with your project, there are several intermediate milestones. If you are working with a partner, you may submit a single set of any of these components.
Topic Ideas (Wednesday 10/23): Submit one to three possible topic ideas, with a paragraph describing each. For each topic, include the general question that may like to address, a list of relevant research papers that you plan to read, and one particular paper that you might like to present to the class. Submitting these ideas will encourage you start thinking about your project early, allow you to identify students with similar interests with whom you might like to collaborate, and let me give you preliminary suggestions for how to proceed.
1
Presentation Sign-Up (Wednesday 11/6): Each project group will present a paper or a few very closely related papers to the class. Individuals may choose either a Tuesday slot or a Thursday slot, and pairs should choose a Tuesday slot (with time split evenly between the two group members).
Project Proposal (Wednesday 11/13): Submit a page or two outlining what your project will look like. At this stage, you should be able to clearly state your research questions, describe how your project relates to prior work on the topic, and describe your plan of attack for addressing these questions.
Presentation (Roughly Thursday 11/21 – Tuesday 12/10): Your presentation should clearly explain the main question(s) the paper addresses, provide the context and motivation for studying these questions, state the paper’s main result(s), and give as detailed a proof sketch as is reasonable given the time constraints. You should also spend a few minutes describing your project and any new results you have to share. You may either use slides or do a blackboard presentation. A blackboard presentation should be accompanied by a set of typeset lecture notes similar to those appearing on the course website.
Project Report (Wednesday 12/11): Submit a paper (about 8–10 pages) describing your completed project. The paper should motivate your research questions and results, explain how the project fits into the context of previous work, and present the results in a clear and convincing manner.
These project and presentation guidelines are adapted from those used in other courses, including Jelani Nelson’s “Algorithms for Big Data,” Toni Pitassi’s “Communication Complexity: Applications and New Directions,” and especially Salil Vadhan/Jon Ullman’s “Mathematical Approaches to Data Privacy.”
2
Project/Presentation Topic Ideas
Below are a number of suggestions for possible project and presentation topics with a few representative references for each. These are just meant as inspiration to get you started thinking. You are in no way obligated to stick to these topics and are encouraged to explore topics that interest you. The references provided are not exhaustive and you will want to do additional research to find the state-of-the-art on each topic.
Log Rank Conjecture The log rank conjecture, that PPcc(f) ≤ polylog(rankMf) for every function f, is perhaps the most notorious open question in communication complex- ity. Lovett recently made substantial progress on this conjecture, showing that PPcc(f) ≤ O ̃(log rank Mf ). (The proof was then simplified by Rothvoß.)
• On rank vs. communication complexity. Nisan, Wigderson, 1994.
• An additive combinatorics approach to the log-rank conjecture. Ben-Sasson, Lovett,
Zewi, 2011.
• En route to the log-rank conjecture: New reductions and equivalent formulations. Gavinsky, Lovett, 2014.
• Communication is bounded by root of rank. Lovett, 2014.
• Recent advances on the log rank conjecture. Lovett, 2014.
• A direct proof for Lovett’s bound on the communication complexity of low rank ma- trices. Rothvoß, 2014.
Approximate Log Rank Conjecture Just as rank provides a lower bound on determinis- tic communication complexity, approximate rank is a lower bound on bounded error random- ized (and even bounded error quantum) communication complexity. Here, the approximate rankofamatrixM istheleastrankofrealmatrixM′ suchthat|M′[x,y]−M[x,y]|≤1/3 for every entry (x, y). By analogy to the log rank conjecture, one could also conjecture that BPPcc(f) is always bounded by the logarithm of the approximate rank of f. This conjecture turns out to be false, as corruption can be exponentially larger than log approximate rank. A generalization of this exponential separation also holds for quantum communication using tools from quantum information complexity.
• The log-approximate-rank conjecture is false. Chattopadhyay, Mande, Sherif, 2018.
• Quantum log-approximate-rank conjecture is also false. Anshu, Boddu, Touchette,
2018.
• Exponential separation between quantum communication and logarithm of approxi- mate rank. Sinha, de Wolf, 2018.
3
Protocol Compression In class, we talked about Braverman and Rao’s method for com- pressing interactive protocols. However, there are other schemes which achieve different tradeoffs between the information complexity and communication complexity of the starting protocol or which apply to different communication settings.
• How to compress interactive communication. Braverman, Barak, Chen, Rao, 2010.
• Information equals amortized communication. Braverman, Rao, 2011.
• Interactive information complexity. Braverman, 2012.
• Direct product via round-preserving compression. Braverman, Rao, Weinstein, Yehu- dayoff, 2013.
• From information to exact communication. Braverman, Garg, Pankratov, Weinstein, 2013.
• Interactive compression for product distributions. Kol, 2016.
• Compressing interactive communication under product distributions. Sherstov, 2016.
• Interactive compression for multi-party protocols. Kol, Oshman, Sadeh, 2017.
• Interactive compression to external information. Braverman, Kol, 2018.
Separating Information and Communication What are the limits of protocol com- pression? It turns out to be impossible to compress an arbitrary protocol all the way down to its internal, or even external, information cost.
• Exponential separation of information and communication. Ganor, Kol, Raz, 2014.
• Exponential separation of information and communication for boolean functions. Ganor,
Kol, Raz, 2015.
• Exponential separation of communication and external information. Ganor, Kol, Raz, 2016.
• Exponential separation of quantum communication and classical information. Anshu, Touchette, Yao, Yu, 2018.
• Simplified separation of information and communication. Rao, Sinha, 2018.
• A candidate for a strong separation of information and communication. Braverman, Ganor, Kol, Raz, 2018.
4
Pointer Functions and Cheat Sheets A relatively recent line of work has uncovered new separations between various query complexity measures and various communication complexity measures by studying functions whose inputs encode pointers to other inputs.
• Deterministic communication vs. partition number. G ̈oo ̈s, Pitassi, Watson, 2015.
• Separations in query complexity based on pointer functions. Ambainis, Balodis, Belovs,
Lee, Santha, Smotrovs, 2015.
• Separations in query complexity using cheat sheets. Aaronson, Ben-David, Kothari, 2016.
• Separations in communication complexity using cheat sheets and information complex- ity. Anshu, Belovs, Ben-David, Go ̈o ̈s, Jain, Kothari, Lee, Santha, 2016.
Communication vs. Rounds Tradeoffs In addition to understanding how many bits need to be exchanged between Alice and Bob in order to compute a function, it is of interest to understand how many rounds of interaction between them are needed. “Pointer-chasing” functions can be used to exhibit dramatic separations between k round and k + 1 round protocols. More natural problems, such as disjointness, exhibit smooth tradeoffs between rounds and total communication required in various communication models.
• Rounds in communication complexity revisited. Nisan, Wigderson, 1993.
• The communication complexity of pointer chasing. Ponzio, Radhakrishnan, Venkatesh,
2000.
• On the communication complexity of sparse set disjointness and exists-equal problems. Sagˇlam, Tardos, 2013.
• Near optimal bounds on bounded-round quantum communication complexity of dis- jointness. Braverman, Garg, Ko, Mao, Touchette, 2016.
• A rounds vs. communication tradeoff for multi-party set disjointness. Braverman, Oshman, 2017.
Multiparty Set Disjointness (Relatively recent papers only.)
• Multiparty communication complexity of disjointness. Chattopadhyay, Ada, 2008.
• Disjointness is hard in the multiparty number-on-the-forehead model. Lee, Shraibman, 2008.
• Multiparty communication complexity and threshold circuit size of AC0. Beame, Huynh-Ngoc, 2009.
5
• The multiparty communication complexity of set disjointness. Sherstov, 2012.
• Communication lower bounds using directional derivatives. Sherstov, 2013.
• Simplified lower bounds on the multiparty communication complexity of disjointness. Rao, Yehudayoff, 2015.
• A rounds vs. communication tradeoff for multi-party set disjointness. Braverman, Oshman, 2017.
Direct Product Theorems
• Strong direct product theorems for quantum communication and query complexity. Sherstov, 2010.
• Direct products in communication complexity. Braverman, Rao, Weinstein, Yehuday- off, 2013.
Unbounded Error Communication and Sign Rank
• The unbounded error communication complexity of symmetric functions. Sherstov, 2008.
• The sign rank of AC0. Razborov, Sherstov, 2008.
• Improved bounds on the sign rank of AC0. Bun, Thaler, 2016.
• The large error approximate degree of AC0. Bun, Thaler, 2018.
• Near-optimal lower bounds on the threshold degree and sign-rank of AC0. Sherstov, Wu, 2018.
Proof Systems, Polynomial Hierarchy A major open question is to give an explicit function which is outside the communication analog of the polynomial hierarchy. This ques- tion is close related to questions about matrix rigidity. An answer to this question was given recently by Alman and Chan who showed that such a function can be constructed in ENP. The question remains open for functions that can be constructed in, say, NP, even with respect to classes low within the polynomial hierarchy like NISZKcc ⊆ AMcc ⊆ Σcc.
• Rectangle size bounds and threshold covers in communication complexity. Klauck, 2003.
• Algebrization: A new barrier in complexity theory. Aaronson, Wigderson, 2009.
• On Arthur-Merlin games in communication complexity. Klauck, 2011.
• Zero-information protocols and unambiguity in Arthur-Merlin communication. G ̈oo ̈s, Pitassi, Watson, 2016.
• Efficient constructions of rigid matrices using an NP oracle. Alman, Chen, 2019. 6
2
Other Lifting Theorems
• Communication lower bounds via critical block sensitivity. G ̈oo ̈s, Pitassi, 2014.
• Rectangles are non-negative juntas. G ̈oo ̈s, Lovett, Meka, Watson, Zuckerman, 2015.
• Query-to-communication lifting for PNP. G ̈oo ̈s, Kamath, Pitassi, Watson, 2017.
• A ZPPNP[1] Lifting Theorem. Watson, 2017.
• Approximating rectangles by juntas and weakly-exponential lower bounds for LP re- laxations of CSPs. Kothari, Meka, Raghavendra, 2017.
• A lifting theorem with applications to symmetric functions. Chattopadhay, Mande, 2017.
• Query-to-communication lifting using low-discrepancy gadgets. Chattopadhyay, Fil- mus, Koroth, Meir, Pitassi, 2019.
Communication with Uncertainty In standard communication models, we usually as- sume 1) that the parties know ahead of time what function they are trying to compute and b) they have access to a perfect source of shared randomness. What can be said when either of these assumptions is relaxed?
• Communication with imperfectly shared randomness. Canonne, Guruswami, Meka, Sudan, 2014.
• Communication with contextual uncertainty. Ghazi, Komargodski, Kothari, Sudan, 2016.
• The power of shared randomness in uncertain communication. Ghazi, Sudan, 2017.
• Communication for generating correlation: A unifying survey. Sudan, Tyagi, Watan-
abe, 2019.
Communication Complexity and Data Structures
• Cell probe complexity – A survey. Miltersen, 1999.
• On data structures and asymmetric communication complexity. Miltersen, Nisan,
Safra, Wigderson, 1998.
• Towards polynomial lower bounds for dynamic problems. Patrascu, 2010.
• Unifying the landscape of cell probe lower bounds. Patrascu, 2008.
• A little advice can be very helpful. Chattopadhyay, Edmonds, Ellen, Pitassi, 2011.
7
• Crossing the logarithmic barrier for dynamic boolean data structure lower bounds. Larsen, Weinstein, Yu, 2017.
• Simulation beats richness: new data-structure lower bounds. Chattopadhyay, Koucky ́, Loff, Mukhopadhyay, 2018.
Communication Complexity and Proof Complexity
• Upper and lower bounds for tree-like cutting planes proofs. Impagliazzo, Pitassi, Uruquhart, 1994.
• Interpolation theorems, lower bounds for proof systems, and independence results for bounded arithmetic. Kraj ́ıˇcek, 1997.
• Lower bounds for Lovasz-Schrijver systems and beyond follow from multiparty com- munication complexity. Beame, Pitassi, Segerlind, 2007.
Communication Complexity and Extended Formulations
• Linear vs semidefinite extended formulations: exponential separation and strong lower bounds. Fiorini, Massar, Pokutta, Tiwary, de Wolf, 2012.
• Approximation limits of linear programs (beyond hierarchies). Braun, Fiorini, Pokutta, Steurer 2012.
• The matching polytope has exponential extension complexity. Rothvoß 2014.
• Extension complexity of independent set polytopes. G ̈oo ̈s, Jain, Watson, 2016.
Communication Complexity and Distributed Computing
• Tight bounds for set disjointness in the message passing model. Braverman, Ellen, Oshman, Pitassi, Vaikuntanathan, 2013.
• Topology matters in communication. Chattopadhyay, Radhakrishnan, Rudra, 2014. Communication Complexity and Circuit Lower Bounds (Relatively recent papers
only)
• Separating AC0 from depth-2 majority circuits. Sherstov, 2007.
• Strongly exponential lower bounds for monotone circuit complexity. Pitassi, Robere, 2017.
8
Communication Complexity and Streaming
• The space complexity of approximating the frequency moments. Alon, Matias, Szegedy, 1996.
• On the exact space complexity of sketching and streaming small norms. Kane, Nelson, Woodruff, 2010.
• Robust lower bounds for communication and stream computation. Chakrabarti, Cor- mode, McGregor, 2012.
Communication Complexity and Game Theory
• Barriers to near-optimal equilibria. Roughgarden, 2014.
• The communication complexity of local search. Babichenko, Dobzinski, Nisan, 2018.
• Near-optimal communication lower bounds for approximate Nash Equilibria. Go ̈ ̈os, Rubinstein, 2018.
Communication Complexity and Property Testing
• Property testing lower bounds via communication complexity. Blais, Brody, Matulef, 2011.
• Testing and reconstruction of Lipschitz functions with applications to data privacy. Jha, Raskhodnikova, 2011.
• On the communication complexity methodology for proving lower bounds on the query complexity of property testing. Goldreich, 2013.
• Non-interactive proofs of proximity. Gur, Rothblum, 2013. Communication Complexity and Differential Privacy
• Sample complexity bounds for differentially private learning via communication com- plexity. Feldman, Xiao 2014.
• The limits of two-party differential privacy. McGregor, Mironov, Pitassi, Reingold, Talwar, Vadhan 2010.
• The role of interactivity in local differential privacy. Joseph, Mao, Neal, Roth 2019.
• Exponential separations in local differential privacy via communication complexity. Joseph, Mao, Roth 2019.
9