Page
%P
-
Article
Reliable communication over highly connected noisy networks
We consider the task of multiparty computation performed over networks in the presence of random noise. Given an n-party protocol that takes R rounds assuming noiseless communication, the goal is to find a coding...
-
Article
Information complexity and applications
This paper is a lecture note accompanying the 19th Takagi Lectures lectures in July 2017 at Kyoto University.
-
Article
Strategyproof Mechanisms for Competitive Influence in Networks
Motivated by applications to word-of-mouth advertising, we consider a game-theoretic scenario in which competing advertisers want to target initial adopters in a social network. Each advertiser wishes to maxim...
-
Article
Guest Editorial for Information Complexity and Applications
-
Article
A Discrepancy Lower Bound for Information Complexity
This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized ...
-
Article
Information Lower Bounds via Self-Reducibility
We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our...
-
Chapter and Conference Paper
Public vs Private Coin in Bounded-Round Information
We precisely characterize the role of private randomness in the ability of Alice to send a message to Bob while minimizing the amount of information revealed to him. We give an example of a (randomized) messag...
-
Chapter and Conference Paper
Information Lower Bounds via Self-reducibility
We use self-reduction methods to prove strong information lower bounds on two of the most studied functions in the communication complexity literature: Gap Hamming Distance (GHD) and Inner Product (IP). In our...
-
Chapter and Conference Paper
Noise versus Computational Intractability in Dynamics
Computation plays a key role in predicting and analyzing natural phenomena. There are two fundamental barriers to our ability to computationally understand the long-term behavior of a dynamical system that des...
-
Chapter and Conference Paper
Direct Product via Round-Preserving Compression
We obtain a strong direct product theorem for two-party bounded round communication complexity. Let suc r (μ,f,C) denote the maximum success probability ...
-
Article
The rate of convergence of the Walk on Spheres Algorithm
In this paper we examine the rate of convergence of one of the standard algorithms for emulating exit probabilities of Brownian motion, the Walk on Spheres (WoS) algorithm. We obtain a complete characterizatio...
-
Chapter and Conference Paper
A Discrepancy Lower Bound for Information Complexity
This paper provides the first general technique for proving information lower bounds on two-party unbounded-rounds communication problems. We show that the discrepancy lower bound, which applies to randomized ...
-
Article
Computability of Brolin-Lyubich Measure
Brolin-Lyubich measure λ R of a rational endomorphism $${R:{\hat{\mathbb {C}}}\to {\hat{\mathbb {C}...
-
Chapter and Conference Paper
Inapproximability of NP-Complete Variants of Nash Equilibrium
In recent work of Hazan and Krauthgamer (SICOMP 2011), it was shown that finding an ε-approximate Nash equilibrium with near-optimal value in a two-player game is as hard as finding a hidden clique of size O(logn
-
Article
Constructing Locally Connected Non-Computable Julia Sets
A locally connected quadratic Siegel Julia set has a simple explicit topological model. Such a set is computable if there exists an algorithm to draw it on a computer screen with an arbitrary resolution. We co...
-
Article
Space-Efficient Counting in Graphs on Surfaces
We consider the problem of counting the number of spanning trees in planar graphs. We prove tight bounds on the complexity of the problem, both in general and especially in the modular setting. We exhibit the pro...
-
Book
-
Chapter and Conference Paper
Branching Programs for Tree Evaluation
The problem \(FT^{h}_{d}(k)\) consists in computing the value in [k] = {1,...,k} taken by the root of a balanced d-ary ...
-
Article
On the computational complexity of the Riemann map**
In this paper we consider the computational complexity of uniformizing a domain with a given computable boundary. We give nontrivial upper and lower bounds in two settings: when the approximation of the bounda...
-
Chapter and Conference Paper
Derandomization of Euclidean Random Walks
We consider the problem of derandomizing random walks in the Euclidean space k . We show that for k =...
