 Publication Date:
 NSFPAR ID:
 10326345
 Journal Name:
 ACM Transactions on Computation Theory
 Volume:
 13
 Issue:
 4
 Page Range or eLocationID:
 1 to 17
 ISSN:
 19423454
 Sponsoring Org:
 National Science Foundation
More Like this

The communication class UPP^{cc} is a communication analog of the Turing Machine complexity class PP. It is characterized by a matrixanalytic complexity measure called signrank (also called dimension complexity), and is essentially the most powerful communication class against which we know how to prove lower bounds. For a communication problem f, let f wedge f denote the function that evaluates f on two disjoint inputs and outputs the AND of the results. We exhibit a communication problem f with UPP^{cc}(f)= O(log n), and UPP^{cc}(f wedge f) = Theta(log^2 n). This is the first result showing that UPP communication complexity can increase by more than a constant factor under intersection. We view this as a first step toward showing that UPP^{cc}, the class of problems with polylogarithmiccost UPP communication protocols, is not closed under intersection. Our result shows that the function class consisting of intersections of two majorities on n bits has dimension complexity n^{Omega(log n)}. This matches an upper bound of (Klivans, O'Donnell, and Servedio, FOCS 2002), who used it to give a quasipolynomial time algorithm for PAC learning intersections of polylogarithmically many majorities. Hence, fundamentally new techniques will be needed to learn this class of functions in polynomial time.

The noise sensitivity of a Boolean function f: {0,1}^n  > {0,1} is one of its fundamental properties. For noise parameter delta, the noise sensitivity is denoted as NS_{delta}[f]. This quantity is defined as follows: First, pick x = (x_1,...,x_n) uniformly at random from {0,1}^n, then pick z by flipping each x_i independently with probability delta. NS_{delta}[f] is defined to equal Pr [f(x) != f(z)]. Much of the existing literature on noise sensitivity explores the following two directions: (1) Showing that functions with low noisesensitivity are structured in certain ways. (2) Mathematically showing that certain classes of functions have low noise sensitivity. Combined, these two research directions show that certain classes of functions have low noise sensitivity and therefore have useful structure. The fundamental importance of noise sensitivity, together with this wealth of structural results, motivates the algorithmic question of approximating NS_{delta}[f] given an oracle access to the function f. We show that the standard sampling approach is essentially optimal for general Boolean functions. Therefore, we focus on estimating the noise sensitivity of monotone functions, which form an important subclass of Boolean functions, since many functions of interest are either monotone or can be simply transformed into a monotone functionmore »

The Sparsest Cut is a fundamental optimization problem that have been extensively studied. For planar inputs the problem is in P and can be solved in Õ(n 3 ) time if all vertex weights are 1. Despite a significant amount of effort, the best algorithms date back to the early 90’s and can only achieve O(log n)approximation in Õ(n) time or 3.5approximation in Õ(n 2 ) time [Rao, STOC92]. Our main result is an Ω(n 2−ε ) lower bound for Sparsest Cut even in planar graphs with unit vertex weights, under the (min, +)Convolution conjecture, showing that approxima tions are inevitable in the nearlinear time regime. To complement the lower bound, we provide a 3.3approximation in nearlinear time, improving upon the 25year old result of Rao in both time and accuracy. We also show that our lower bound is not far from optimal by observing an exact algorithm with running time Õ(n 5/2 ) improving upon the Õ(n 3 ) algorithm of Park and Phillips [STOC93]. Our lower bound accomplishes a repeatedly raised challenge by being the first finegrained lower bound for a natural planar graph problem in P. Building on our construction we prove nearquadratic lower bounds under SETHmore »

In a recent work (Ghazi et al., SODA 2016), the authors with Komargodski and Kothari initiated the study of communication with contextual uncertainty, a setup aiming to understand how efficient communication is possible when the communicating parties imperfectly share a huge context. In this setting, Alice is given a function f and an input string x, and Bob is given a function g and an input string y. The pair (x,y) comes from a known distribution mu and f and g are guaranteed to be close under this distribution. Alice and Bob wish to compute g(x,y) with high probability. The lack of agreement between Alice and Bob on the function that is being computed captures the uncertainty in the context. The previous work showed that any problem with oneway communication complexity k in the standard model (i.e., without uncertainty, in other words, under the promise that f=g) has publiccoin communication at most O(k(1+I)) bits in the uncertain case, where I is the mutual information between x and y. Moreover, a lower bound of Omega(sqrt{I}) bits on the publiccoin uncertain communication was also shown. However, an important question that was left open is related to the power that public randomness bringsmore »

Abstract We continue the program of proving circuit lower bounds via circuit satisfiability algorithms. So far, this program has yielded several concrete results, proving that functions in
and other complexity classes do not have small circuits (in the worst case and/or on average) from various circuit classes$\mathsf {Quasi}\text {}\mathsf {NP} = \mathsf {NTIME}[n^{(\log n)^{O(1)}}]$ $\mathrm{Quasi}\mathrm{NP}=\mathrm{NTIME}\left[{n}^{{\left(\mathrm{log}n\right)}^{O\left(1\right)}}\right]$ , by showing that$\mathcal { C}$ $C$ admits nontrivial satisfiability and/or$\mathcal { C}$ $C$# SAT algorithms which beat exhaustive search by a minor amount. In this paper, we present a new strong lower bound consequence of having a nontrivial# SAT algorithm for a circuit class . Say that a symmetric Boolean function${\mathcal C}$ $C$f (x _{1},…,x _{n}) issparse if it outputs 1 onO (1) values of . We show that for every sparse${\sum }_{i} x_{i}$ ${\sum}_{i}{x}_{i}$f , and for all “typical” , faster$\mathcal { C}$ $C$# SAT algorithms for circuits imply lower bounds against the circuit class$\mathcal { C}$ $C$ , which may be$f \circ \mathcal { C}$ $f\circ C$stronger than itself. In particular:$\mathcal { C}$ $C$# SAT algorithms forn ^{k}size circuits running in 2^{n}/$\mathcal { C}$ $C$n ^{k}time (for allk ) implyN E X P does not have circuits of polynomial size.$(f \circ \mathcal { C})$ $(f\circ C)$# SAT algorithms for size$2^{n^{{\varepsilon }}}$ ${2}^{{n}^{\epsilon}}$ circuits running in$\mathcal { C}$ $C$ time (for some$2^{nn^{{\varepsilon }}}$ ${2}^{n{n}^{\epsilon}}$ε > 0) implyQ u a s i N P does not have circuits of polynomial size.$(f \circ \mathcal { C})$ $(f\circ C)$Applying
# SAT algorithms from the literature, one immediate corollary of our results is thatQ u a s i N P does not haveE M A J ∘A C C ^{0}∘T H R circuits of polynomialmore »