The class ACC⁰ consists of Boolean functions that can be computed by constant-depth circuits of polynomial size with AND, NOT and MOD_m gates, where m is a natural number. At the frontier of our understanding lies a widely believed conjecture asserting that MAJORITY does not belong to ACC⁰. A few years ago, Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) introduced torus polynomial approximations as an approach towards this conjecture. Torus polynomials approximate Boolean functions when the fractional part of their value on Boolean points is close to half the value of the function. They reduced the conjecture that MAJORITY ∉ ACC⁰ to a conjecture concerning the non-existence of low degree torus polynomials that approximate MAJORITY. We reduce the non-existence problem further, to a statement about finding feasible solutions for an infinite family of linear programs. The main advantage of this statement is that it allows for incremental progress, which means finding feasible solutions for successively larger collections of these programs. As an immediate first step, we find feasible solutions for a large class of these linear programs, leaving only a finite set for further consideration. Our method is inspired by the method of dual polynomials, which is used to study the approximate degree of Boolean functions. Using our method, we also propose a way to progress further. We prove several additional key results with the same method, which include: - A lower bound on the degree of symmetric torus polynomials that approximate the AND function. As a consequence, we get a separation that symmetric torus polynomials are weaker than their asymmetric counterparts. - An error-degree trade-off for symmetric torus polynomials approximating the MAJORITY function, strengthening the corresponding result of Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019). - The first lower bounds against torus polynomials approximating AND, showcasing the power of the machinery we develop. This lower bound nearly matches the corresponding upper bound. Hence, we get an almost complete characterization of the torus polynomial approximation degree of AND. - Lower bounds against asymmetric torus polynomials approximating MAJORITY, or AND, in the very low error regime. This partially answers a question posed in Bhrushundi, Hosseini, Lovett and Rao (ITCS 2019) about error-reduction for torus polynomials.

The weighted k -server problem is a generalization of the k -server problem wherein the cost of moving a server of weight β i through a distance d is β i ⋅ d . On uniform metric spaces, this models caching with caches having different page replacement costs. A memoryless algorithm is an online algorithm whose behavior is independent of the history given the positions of its k servers. In this article, we develop a framework to analyze the competitiveness of randomized memoryless algorithms. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. Using this, we establish tight bounds on the competitive ratio achievable by randomized memoryless algorithms for the weighted k -server problem on uniform metrics. We first prove that there is an α k -competitive memoryless algorithm for this problem, where α k =α k − 1 2 + 3α k − 1 +1; α 1 = 1. We complement this result by proving that no randomized memoryless algorithm can have a competitive ratio less than α k . Finally, we prove that the above bounds also hold for the generalized k -server problem on weighted uniform metrics.

We present a randomized approximation algorithm for computing traveling salesperson tours in undirected regular graphs. Given an $n$-vertex, $k$-regular graph, the algorithm computes a tour of length at most $\left(1+\frac{7}{\ln k-O(1)}\right)n$, with high probability, in $O(nk \log k)$ time. This improves upon a recent result by Vishnoi (\cite{Vishnoi12}, FOCS 2012) for the same problem, in terms of both approximation factor, and running time. The key ingredient of our algorithm is a technique that uses edge-coloring algorithms to sample a cycle cover with $O(n/\log k)$ cycles with high probability, in near linear time. Additionally, we also give a deterministic $\frac{3}{2}+O\left(\frac{1}{\sqrt{k}}\right)$ factor approximation algorithm running in time $O(nk)$.

The weighted k-server problem is a generalization of the k-server problem in which the cost of moving a server of weight β_i through a distance d is β_i· d. The weighted server problem on uniform spaces models caching where caches have different write costs. We prove tight bounds on the performance of randomized memory less algorithms for this problem on uniform metric spaces. We prove that there is an α_k competitive memory less algorithm for this problem, where α_k=α_k-12+3α_k-1+1; α_1=1. On the other hand, we also prove a lower bound result, which is a strong evidence to our conjecture, that no randomized memory less algorithm can have competitive ratio better than α_k. To prove the upper bound of α_k, we develop a framework to bound from above the competitive ratio of any randomized memory less algorithm for this problem. The key technical contribution is a method for working with potential functions defined implicitly as the solution of a linear system. The result is robust in the sense that a small change in the probabilities used by the algorithm results in a small change in the upper bound on the competitive ratio. The above result has two important implications. Firstly this yields an α_k-competitive memory less algorithm for the weighted k-server problem on uniform spaces. This is the first competitive algorithm for k>2 which is memory less. For k=2, our algorithm agrees with the one given by Chrobak and Sgall. Secondly, this helps us prove that the Harmonic algorithm, which chooses probabilities in inverse proportion to weights, has a competitive ratio of kα_k. The only known competitive algorithm for every k before this work is a carefully crafted deterministic algorithm due to Fiat and Ricklin. Their algorithm uses memory crucially and their bound on competitive ratio more than 24k. Our algorithm is not only memory less, but also has a considerably improved competitive ratio of α_k

The Abelian Sandpile Model is a discrete diffusion process defined on graphs (Dhar [14], Dhar et al. [15]) which serves as the standard model of self-organized criticality. The transience class of a sandpile is defined as the maximum number of particles that can be added without making the system recurrent ([4]). We develop the theory of discrete diffusions in contrast to continuous harmonic functions on graphs and establish deep connections between standard results in the study of random walks on graphs and sandpiles on graphs. Using this connection and building other necessary machinery we improve the main result of Babai and Gorodezky (SODA 2007,[2]) of the bound on the transience class of an n × n grid, from O(n30) to O(n7). Proving that the transience class is small validates the general notion that for most natural phenomenon, the time during which the system is transient is small. In addition, we use the machinery developed to prove a number of auxiliary results. We exhibit an equivalence between two other tessellations of plane, the honeycomb and triangular lattices. We give general upper bounds on the transience class as a function of the number of edges to the sink. Further, for planar sandpiles we derive an explicit algebraic expression which provably approximates the transience class of G to within O(E(G)). This expression is based on the spectrum of the Laplacian of the dual of the graph G. We also show a lower bound of Ω(n3) on the transience class on the grid improving the obvious bound of Ω(n2).

We propose a new LP relaxation for obtaining the MAP assignment of a binary MRF with pairwise potentials. Our relaxation is derived from reducing the MAP assignment problem to an instance of a recently proposed Bipartite Multi-cut problem where the LP relaxation is guaranteed to provide an O(log k) approximation where k is the number of vertices adjacent to non-submodular edges in the MRF. We then propose a combinatorial algorithm to efficiently solve the LP and also provide a lower bound by concurrently solving its dual to within an approximation. The algorithm is up to an order of magnitude faster and provides better MAP scores and bounds than the state of the art message passing algorithm of [1] that tightens the local marginal polytope with third-order marginal constraints.

Consider a graph G and a collection of connected spanning subgraphs $G_1, G_2, \ldots, G_k$, not necessarily edge-disjoint. A subset $U_i$ of the vertex set is said to d-$dominate$ $G_i$ if in $G_i$, all the vertices are at distance at most d from some vertex in $U_i$. Alon et al. [Discrete Math., 262 (2003), pp. 17–25] introduced and studied a function $\mu(k)$, which is defined as the minimum radius of domination d such that the vertex set of every graph with a collection of k spanning subgraphs can be partitioned into $U_1, U_2, \ldots, U_k$ such that $U_i$ d-dominates $G_i$. They proved that $\mu(k) < \frac{3}{2}k$, and the proof yields a polynomial time algorithm for the same. We prove that the problem is $\cal NP$-complete, and we also answer a question from their paper by improving their bound to $(\frac{3}{2}-\epsilon)k$. We also present an algorithm which finds such a coloring in polynomial time.

We show that if there is a 2 - ϵ approximation algorithm for vertex cover on graphs with vector chromatic number at most 2 + δ, then there is a 2 - f (ϵ, δ) approximation algorithm for vertex cover for all graphs.

A layered graph is a connected graph whose vertices are partitioned into sets L 0 =s, L 1 , L 2 ,..., and whose edges, which have nonnegative integral weights, run between consecutive layers. Its width is $\max\{|L_i|\}$. In the on-line layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. We give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. We give a deterministic on-line algorithm which is O(9 w )-competitive on width-w graphs and prove that for no w can a deterministic on-line algorithm have a competitive ratio better than 2 w-2 on width-w graphs. We prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized on-line layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, we give a randomized on-line algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.

We study the problem of locality based graph coloring.This problem is motivated by the problem of assigning time slots for broadcast in mobile packet radio networks.This problem has also been studied in the context of distributed and parallel graph coloring [4, 6, 9, 8].In this problem, one has to design a coloring algorithm that assigns a color to a vertex based on the label of the vertex and the labels on its neighbors.Linial proved an upper bound of O(A2 log n) and a lower bound of fl(log log n) on the number of colors needed to locally color an n-vertex graph with maximum vertex degree A [9, 8].His main motivation was that repeated application of local coloring gives a fast algorithm for distributed coloring.He proved that one could get a A2 coloring in O(log* n) steps this way.In this paper we improve upon the bounds for the problem of local coloring.Using a new characterization in terms of a family of set systems we design a randomized algorithm for the problem and prove an upper bound of O(A.2A log log n).An important question left open in Linial's paper was the case of large A. The best lower bound was A + 1. Linial observed that a result of Erdos, Frankl and Furedi implied that his method cannot be applied to reduce the number of colors to below (A~2).We obtain lower bounds that match the upper bounds within a factor that is poly-logarithmic in terms of these bounds.Of particular interest we have very precise bounds for the case when A > 2+.These bounds are useful to obtain a heuristic estimate on the *Researchsupported in part by Ketan Mulmuley's Packard Fellowship.

A layered graph is a connected, weighted graph whose vertices are partitioned into sets L/sub 0/=(s), L/sub 1/, L/sub 2/, . . ., and whose edges run between consecutive layers. Its width is max( mod L/sub i/ mod ). In the online layered graph traversal problem, a searcher starts at s in a layered graph of unknown width and tries to reach a target vertex t; however, the vertices in layer i and the edges between layers i-1 and i are only revealed when the searcher reaches layer i-1. The authors give upper and lower bounds on the competitive ratio of layered graph traversal algorithms. They give a deterministic online algorithm that is O(9w)-competitive on width-w graphs and prove that for no w can a deterministic online algorithm have a competitive ratio better than 2w/sup -2/ on width-w graphs. They prove that for all w, w/2 is a lower bound on the competitive ratio of any randomized online layered graph traversal algorithm. For traversing layered graphs consisting of w disjoint paths tied together at a common source, they give a randomized online algorithm with a competitive ratio of O(log w) and prove that this is optimal up to a constant factor.>

In the k-server problem, one must choose how k mobile servers will serve each of a sequence of requests, making decisions in an online manner. An optimal deterministic online strategy is exhibited when the requests fall on the real line. For the weighted-cache problem, in which the cost of moving to x from any other point is $w( x )$, the weight of x, an optimal deterministic algorithm is also provided. The nonexistence of competitive algorithms for the asymmetric two-server problem and of memoryless algorithms for the weighted-cache problem is proved. A fast algorithm for oflline computing of an optimal schedule is given, and it is shown that finding an optimal offline schedule is at least as hard as the assignment problem.

It is shown that randomization helps in coloring graphs online, and a simple randomized online algorithm is presented. For 3-colorable graphs the expected number of colors the algorithm uses is O((n log n)/sup 1/2/). The algorithm runs in polynomial time and compares well with the best known polynomial-time offline algorithms. A lower bound is proved for the randomized algorithm.>