For every fixed graph H, it is known that homomorphism counts from H and colorful H-subgraph counts can be determined in O(n^{t+1}) time on n-vertex input graphs G, where t is the treewidth of H. On the other hand, a running time of n^{o(t / log t)} would refute the exponential-time hypothesis. Komarath, Pandey, and Rahul (Algorithmica, 2023) studied algebraic variants of these counting problems, i.e., homomorphism and subgraph polynomials for fixed graphs H. These polynomials are weighted sums over the objects counted above, where each object is weighted by the product of variables corresponding to edges contained in the object. As shown by Komarath et al., the monotone circuit complexity of the homomorphism polynomial for H is Θ(n^{tw(H)+1}). In this paper, we characterize the power of monotone bounded-depth circuits for homomorphism and colorful subgraph polynomials. This leads us to discover a natural hierarchy of graph parameters tw_Δ(H), for fixed Δ ∈ ℕ, which capture the width of tree-decompositions for H when the underlying tree is required to have depth at most Δ. We prove that monotone circuits of product-depth Δ computing the homomorphism polynomial for H require size Θ(n^{tw_Δ(H^{†})+1}), where H^{†} is the graph obtained from H by removing all degree-1 vertices. This allows us to derive an optimal depth hierarchy theorem for monotone bounded-depth circuits through graph-theoretic arguments.

With the explosion of data transmitted over the Internet, Content Delivery Networks (CDNs) carry massive network traffic globally and suffer an increasingly higher bandwidth cost. A critical issue for CDN service providers is how to allocate network traffic among CDN facilities to reduce the total bandwidth cost without violating the quality of service. This work studies online traffic allocation in CDNs to minimize the bandwidth cost under the 95th percentile charging model. Specifically, we here take into account practical deployment issues in large-scale CDN systems, e.g., allocation granularity and deviation. We first theoretically prove the approximation hardness of the traffic allocation problem. We then propose a novel prediction-based algorithm named OnTPC, which effectively addresses constraints raised in practical deployment. Extensive experiments demonstrate that OnTPC outperforms state-of-the-art baselines and is expected to save over a million dollars per month for our large-scale commercial CDN collaborator. Moreover, the performance of OnTPC is consistently outstanding under various settings, and specifically robust to large allocation deviation.

In the 1970s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings [ Proceedings of FCT, 1979, pp. 565--574]. A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the noncommutative rank problem [A. Garg et al., Proceedings of FOCS, 2016, pp. 109--117; G. Ivanyos, Y. Qiao, and K. V. Subrahmanyam, Comput. Complexity, 26 (2017), pp. 717--763]. In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex $c$-coloring problem reduce to the maximum isotropic space problem and the isotropic $c$-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration.

In the 1970’s, Lovász built a bridge between graphs and alternating matrix spaces, in the context of perfect matchings (FCT 1979). A similar connection between bipartite graphs and matrix spaces plays a key role in the recent resolutions of the non-commutative rank problem (Garg-Gurvits-Oliveira-Wigderson, FOCS 2016; Ivanyos-Qiao-Subrahmanyam, ITCS 2017). In this paper, we lay the foundation for another bridge between graphs and alternating matrix spaces, in the context of independent sets and vertex colorings. The corresponding structures in alternating matrix spaces are isotropic spaces and isotropic decompositions, both useful structures in group theory and manifold theory. We first show that the maximum independent set problem and the vertex c-coloring problem reduce to the maximum isotropic space problem and the isotropic c-decomposition problem, respectively. Next, we show that several topics and results about independent sets and vertex colorings have natural correspondences for isotropic spaces and decompositions. These include algorithmic problems, such as the maximum independent set problem for bipartite graphs, and exact exponential-time algorithms for the chromatic number, as well as mathematical questions, such as the number of maximal independent sets, and the relation between the maximum degree and the chromatic number. These connections lead to new interactions between graph theory and algebra. Some results have concrete applications to group theory and manifold theory, and we initiate a variant of these structures in the context of quantum information theory. Finally, we propose several open questions for further exploration. (Dedicated to the memory of Ker-I Ko)

We show that every circuit with ${AND},{OR},{NOT}$, and ${MOD}_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-2, ${SYM}\circ{AND}$, circuit of size $2^{(\log n)^{O(d)}}$. This is an exponential size improvement over the traditional Yao--Beigel--Tarui, which has size blowup $2^{(\log n)^{2^{O(d)}}}$. Therefore, depth-reduction for composite $m$ matches the size of the Allender--Hertrampf construction for primes from 1989. We also list two among the consequences of our construction. One immediate implication is a near-exponential improvement in the depth, from $o(\log\log n)$ to $o(\log n/\log\log n)$, in Williams' program for ${NEXP}$ circuit lower bounds. In fact, this pushes William's program to the ${NC}^1$ frontier. Another, but nontrivial, implication is the strengthening of this $o(\log n/\log\log n)$ depth lower bound in the Chattopadhyay--Santhanam interactive compression setting.

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating NEXP from non-uniform ACC. In particular, we show that every circuit with AND, OR, NOT, and MODmgates, m ε Z+, of polynomial size and depth d can be reduced to a depth-2, SYM-AND, circuit of size 2(log n)O(d). This is an exponential size improvement over the traditional Yao-Beigel-Tarui, which has size blowup 2(log n)2O(d). Therefore, depth-reduction for composite m matches the size of the Allender-Hertrampf construction for primes from 1989. One immediate implication of depth reduction is an improvement of the depth from o(loglog n) to o(log n/loglog n), in Williams' program for ACC circuit lower bounds against NEXP. This is just short of O(log n/loglog n) and thus pushes William's program to the NC1barrier, since NC1is contained in ACC of depth O(log n/loglog n). A second, but non-immediate, implication regards the strengthening of the ACC lower bound in the Chattopadhyay-Santhanam interactive compression setting.

In the past thirty years, Communication Complexity has emerged as a foundational tool to proving lower bounds in many areas of computer science. Its power comes from its generality, but this generality comes at a price---no superlinear communication lower bound is possible, since a player may communicate his entire input. However, what if the players are limited in their ability to recall parts of their interaction?

In 1998, Paturi, Pudlák, Saks, and Zane presented PPSZ, an elegant randomized algorithm for k-SAT. Fourteen years on, this algorithm is still the fastest known worst-case algorithm. They proved that its expected running time on k-CNF formulas with n variables is at most , where εk ∊ Ω(1/k). So far, no exponential lower bounds at all have been known. In this paper, we construct hard instances for PPSZ. That is, we construct satisfiable k-CNF formulas over n variables on which the expected running time is at least , for εk ∊ O(log2 k/k).