# Theory of Computing Blog Aggregator

### TR15-193 | On the hardness of learning sparse parities | Arnab Bhattacharyya, Ameet Gadekar, Suprovat Ghoshal, Rishi Saket

from ECCC papers

This work investigates the hardness of computing sparse solutions to systems of linear equations over $\mathbb{F}_2$. Consider the $k$-EvenSet problem: given a homogeneous system of linear equations over $\mathbb{F}_2$ on $n$ variables, decide if there exists a nonzero solution of Hamming weight at most $k$ (i.e. a $k$-sparse solution). While there is a simple $O(n^{k/2})$-time algorithm for it, establishing fixed parameter intractability for $k$-EvenSet has been a notorious open problem. Towards this goal, we show that unless $k$-Clique can be solved in $n^{o(k)}$ time, $k$-EvenSet has no $\textrm{poly}(n)\cdot 2^{o(\sqrt{k})}$ time algorithm for all $k$ and no polynomial time algorithm when $k = \omega(\log^2 n)$. Our work also shows that the non-homogeneous generalization of the problem -- which we call $k$-VectorSum -- is W[1]-hard on instances where the number of equations is $O(k\log n)$, improving on previous reductions which produced $\Omega(n)$ equations. We use the hardness of $k$-VectorSum as a starting point to prove the result for $k$-EvenSet, and additionally strengthen the former to show the hardness of approximately learning $k$-juntas. In particular, we prove that for any constant $\epsilon > 0$, given a system of $O(\textrm{exp}(O(k))\cdot \log n)$ linear equations, it is W[1]-hard to decide if there is a $k$-sparse linear form satisfying all the equations or any function on at most $k$-variables (a $k$-junta) satisfies at most $(1/2 + \epsilon)$-fraction of the equations. In the setting of computational learning, this shows hardness of approximate non-proper learning of $k$-parities. In a similar vein, we use the hardness of $k$-EvenSet to show that that for any constant $d$, unless $k$-Clique can be solved in $n^{o(k)}$ time, there is no $\textrm{poly}(m, n)\cdot 2^{o(\sqrt{k})}$ time algorithm to decide whether a given set of $m$ points in $\mathbb{F}_2^n$ satisfies: (i) there exists a non-trivial $k$-sparse homogeneous linear form evaluating to $0$ on all the points, or (ii) any non-trivial degree $d$ polynomial $P$ supported on at most $k$ variables evaluates to zero on $\approx \Pr_{\mathbb{F}_2^n}[P({\bf z}) = 0]$ fraction of the points i.e., $P$ is fooled by the set of points. Lastly, we study the approximation in the sparsity of the solution. Let the Gap-$k$-VectorSum problem be: given an instance of $k$-VectorSum of size $n$, decide if there exist a $k$-sparse solution, or every solution is of sparsity at least $k' = (1+\delta_0)k$. Assuming ETH, we show that for some constants $c_0$, $\delta_0 > 0$ there is no $\textrm{poly}(n)$ time algorithm for Gap-$k$-VectorSum when $k = \omega((\log \log n)^{c_0})$.

### TR15-192 | Satisfiability on Mixed Instances | Ruiwen Chen, Rahul Santhanam

from ECCC papers

The study of the worst-case complexity of the Boolean Satisfiability (SAT) problem has seen considerable progress in recent years, for various types of instances including CNFs \cite{PPZ99, PPSZ05, Sch99, Sch05}, Boolean formulas \cite{San10} and constant-depth circuits \cite{IMP12}. We systematically investigate the complexity of solving {\it mixed} instances, where different parts of the instance come from different types. Our investigation is motivated partly by practical contexts such as SMT (Satisfiability Modulo Theories) solving, and partly by theoretical issues such as the exact complexity of graph problems and the desire to find a unifying framework for known satisfiability algorithms. We investigate two kinds of mixing: conjunctive mixing, where the mixed instance is formed by taking the conjunction of pure instances of different types, and compositional mixing, where the mixed instance is formed by the composition of different kinds of circuits. For conjunctive mixing, we show that non-trivial savings over brute force search can be obtained for a number of instance types in a generic way using the paradigm of {\it subcube partitioning}. We apply this generic result to show a meta-algorithmic result about graph optimisation problems: any optimisation problem that can be formalised in Monadic SNP can be solved exactly with exponential savings over brute-force search. This captures known results about problems such as Clique, Independent Set and Vertex Cover, in a uniform way. For certain kinds of conjunctive mixing, such as mixtures of $k$-CNFs and CNFs of bounded size, and of $k$-CNFs and Boolean formulas, we obtain improved savings over subcube partitioning by combining existing algorithmic ideas in a more fine-grained way. We use the perspective of compositional mixing to show the first non-trivial algorithm for satisfiability of quantified Boolean formulas, where there is no depth restriction on the formula. We show that there is an algorithm which for any such formula with a constant number of quantifier blocks and of size $n^c$, where $c < 5/4$, solves satisfiability in time $2^{n-n^{\Omega(1)}}$.

### TR15-191 | Average-Case Lower Bounds and Satisfiability Algorithms for Small Threshold Circuits | Rahul Santhanam, Ruiwen Chen, Srikanth Srinivasan

from ECCC papers

We show average-case lower bounds for explicit Boolean functions against bounded-depth threshold circuits with a superlinear number of wires. We show that for each integer d > 1, there is \epsilon_d > 0 such that Parity has correlation at most 1/n^{\Omega(1)} with depth-d threshold circuits which have at most n^{1+\epsilon_d} wires, and the Generalized Andreev Function has correlation at most 1/2^{n^{\Omega(1)}} with depth-d threshold circuits which have at most n^{1+\epsilon_d} wires. Previously, only worst-case lower bounds in this setting were known [22]. We use our ideas to make progress on several related questions. We give satisfiability algorithms beating brute force search for depth-d threshold circuits with a superlinear number of wires. These are the first such algorithms for depth greater than 2. We also show that Parity cannot be computed by polynomial-size AC0 circuits with n^{o(1)} general threshold gates. Previously no lower bound for Parity in this setting could handle more than log(n) gates. This result also implies subexponential- time learning algorithms for AC0 with n^{o(1)} threshold gates under the uniform distribution. In addition, we give almost optimal bounds for the number of gates in a depth-d threshold circuit computing Parity on average, and show average-case lower bounds for threshold formulas of any depth. Our techniques include adaptive random restrictions, anti-concentration and the structural theory of threshold functions, and bounded-read Chernoff bounds.

### TR15-190 | On the Beck-Fiala Conjecture for Random Set Systems | Shachar Lovett, Esther Ezra

from ECCC papers

Motivated by the Beck-Fiala conjecture, we study discrepancy bounds for random sparse set systems. Concretely, these are set systems $(X,\Sigma)$, where each element $x \in X$ lies in $t$ randomly selected sets of $\Sigma$, where $t$ is an integer parameter. We provide new bounds in two regimes of parameters. We show that when $|\Sigma| \ge |X|$ the hereditary discrepancy of $(X,\Sigma)$ is with high probability $O(\sqrt{t \log t})$; and when $|X| \gg |\Sigma|^t$ the hereditary discrepancy of $(X,\Sigma)$ is with high probability $O(1)$. The first bound combines the Lov{\'a}sz Local Lemma with a new argument based on partial matchings; the second follows from an analysis of the lattice spanned by sparse vectors.

### TR15-189 | Shattered Sets and the Hilbert Function | Cyrus Rashtchian, Shay Moran

from ECCC papers

We study complexity measures on subsets of the boolean hypercube and exhibit connections between algebra (the Hilbert function) and combinatorics (VC theory). These connections yield results in both directions. Our main complexity-theoretic result proves that most linear program feasibility problems cannot be computed by polynomial-sized constant-depth circuits. Moreover, our result applies to a stronger regime in which the hyperplanes are fixed and only the directions of the inequalities are given as input to the circuit. We derive this result by proving that a rich class of extremal functions in VC theory cannot be approximated by low-degree polynomials. We also present applications of algebra to combinatorics. We provide a new algebraic proof of the Sandwich Theorem, which is a generalization of the well-known Sauer-Perles-Shelah Lemma. Finally, we prove a structural result about downward-closed sets, related to the Chv\'{a}tal conjecture in extremal combinatorics.

### Graph Isomorphism and Circuit Size

Authors: Eric Allender, Joshua A. Grochow, Cristopher Moore
Abstract: We show that the Graph Automorphism problem is ZPP-reducible to MKTP, the problem of minimizing time-bounded Kolmogorov complexity. MKTP has previously been studied in connection with the Minimum Circuit Size Problem (MCSP) and is often viewed as essentially a different encoding of MCSP. All prior reductions to MCSP have applied equally well to MKTP, and vice-versa, and all such reductions have relied on the fact that functions computable in polynomial time can be inverted with high probability relative to MCSP and MKTP. Our reduction uses a different approach, and consequently yields the first example of a problem -- other than MKTP itself -- that is in ZPP^MKTP but that is not known to lie in NP intersect coNP. We also show that this approach can be used to provide a reduction of the Graph Isomorphism problem to MKTP.

### Max-Cut under Graph Constraints

Authors: Jon Lee, Viswanath Nagarajan, Xiangkun Shen
Abstract: An instance of the graph-constrained max-cut (GCMC) problem consists of (i) an undirected graph G and (ii) edge-weights on a complete undirected graph on the same vertex set. The objective is to find a subset of vertices satisfying some graph-based constraint in G that maximizes the total weight of edges in the cut. The types of graph constraints we can handle include independent set, vertex cover, dominating set and connectivity. Our main results are for the case when G is a graph with bounded treewidth, where we obtain a 0.5-approximation algorithm. Our algorithm uses an LP relaxation based on the Sherali-Adams hierarchy. It can handle any graph constraint for which there is a (certain type of) dynamic program that exactly optimizes linear objectives. Using known decomposition results, these imply essentially the same approximation ratio for GCMC under constraints such as independent set, dominating set and connectivity on a planar graph G (more generally for bounded-genus or excluded-minor graphs).

### Permanent versus determinant, obstructions, and Kronecker coefficients

Authors: Peter Bürgisser
Abstract: We give an introduction to some of the recent ideas that go under the name geometric complexity theory''. We first sketch the proof of the known upper and lower bounds for the determinantal complexity of the permanent. We then introduce the concept of a representation theoretic obstruction, which has close links to algebraic combinatorics, and we explain some of the insights gained so far. In particular, we address very recent insights on the complexity of testing the positivity of Kronecker coefficients. We also briefly discuss the related asymptotic version of this question.

### Reordering GPU Kernel Launches to Enable Efficient Concurrent Execution

Authors: Teng Li, Vikram K. Narayana, Tarek El-Ghazawi
Abstract: Contemporary GPUs allow concurrent execution of small computational kernels in order to prevent idling of GPU resources. Despite the potential concurrency between independent kernels, the order in which kernels are issued to the GPU will significantly influence the application performance. A technique for deriving suitable kernel launch orders is therefore presented, with the aim of reducing the total execution time. Experimental results indicate that the proposed method yields solutions that are well above the 90 percentile mark in the design space of all possible permutations of the kernel launch sequences.

### R\'enyi Information Complexity and an Information Theoretic Characterization of the Partition Bound

Authors: Manoj M. Prabhakaran, Vinod M. Prabhakaran
Abstract: We introduce a new information-theoretic complexity measure $IC_\infty$ for 2-party functions which is a lower-bound on communication complexity, and has the two leading lower-bounds on communication complexity as its natural relaxations: (external) information complexity ($IC$) and logarithm of partition complexity ($\text{prt}$) which have so far appeared conceptually quite different from each other. $IC_\infty$ is an external information complexity based on R\'enyi mutual information of order infinity. In the definition of $IC_\infty$, relaxing the order of R\'enyi mutual information from infinity to 1 yields $IC$, while $\log \text{prt}$ is obtained by replacing protocol transcripts with what we term "pseudotranscripts," which omits the interactive nature of a protocol, but only requires that the probability of any transcript given the inputs $x$ and $y$ to the two parties, factorizes into two terms which depend on $x$ and $y$ separately. Further understanding $IC_\infty$ might have consequences for important direct-sum problems in communication complexity, as it lies between communication complexity and information complexity.

We also show that applying both the above relaxations simultaneously to $IC_\infty$ gives a complexity measure that is lower-bounded by the (log of) relaxed partition complexity, a complexity measure introduced by Kerenidis et al. (FOCS 2012). We obtain a sharper connection between (external) information complexity and relaxed partition complexity than Kerenidis et al., using an arguably more direct proof.

### TR15-188 | Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits | Ryan Williams, Daniel Kane

from ECCC papers

In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function. $\bullet$ We prove that for all $\epsilon\gg \sqrt{\log(n)/n}$, the linear-time computable Andreev's function cannot be computed on a $(1/2+\epsilon)$-fraction of $n$-bit inputs by depth-two linear threshold circuits of $o(\epsilon^3 n^{3/2}/\log^3 n)$ gates, nor can it be computed with $o(\epsilon^{3} n^{5/2}/\log^{7/2} n)$ wires. This establishes an average-case size hierarchy'' for threshold circuits, as Andreev's function is computable by uniform depth-two circuits of $o(n^3)$ linear threshold gates, and by uniform depth-three circuits of $O(n)$ majority gates. $\bullet$ We present a new function in $P$ based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two linear threshold circuits with $o(n^{3/2}/\log^3 n)$ gates, nor with $o(n^{5/2}/\log^{7/2}n)$ wires. $\bullet$ We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits. The key is a new random restriction lemma for linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.

### Super-Linear Gate and Super-Quadratic Wire Lower Bounds for Depth-Two and Depth-Three Threshold Circuits

Authors: Daniel M. Kane, Ryan Williams
Abstract: In order to formally understand the power of neural computing, we first need to crack the frontier of threshold circuits with two and three layers, a regime that has been surprisingly intractable to analyze. We prove the first super-linear gate lower bounds and the first super-quadratic wire lower bounds for depth-two linear threshold circuits with arbitrary weights, and depth-three majority circuits computing an explicit function.

$\bullet$ We prove that for all $\epsilon\gg \sqrt{\log(n)/n}$, the linear-time computable Andreev's function cannot be computed on a $(1/2+\epsilon)$-fraction of $n$-bit inputs by depth-two linear threshold circuits of $o(\epsilon^3 n^{3/2}/\log^3 n)$ gates, nor can it be computed with $o(\epsilon^{3} n^{5/2}/\log^{7/2} n)$ wires. This establishes an average-case size hierarchy'' for threshold circuits, as Andreev's function is computable by uniform depth-two circuits of $o(n^3)$ linear threshold gates, and by uniform depth-three circuits of $O(n)$ majority gates.

$\bullet$ We present a new function in $P$ based on small-biased sets, which we prove cannot be computed by a majority vote of depth-two linear threshold circuits with $o(n^{3/2}/\log^3 n)$ gates, nor with $o(n^{5/2}/\log^{7/2}n)$ wires.

$\bullet$ We give tight average-case (gate and wire) complexity results for computing PARITY with depth-two threshold circuits; the answer turns out to be the same as for depth-two majority circuits.

The key is a new random restriction lemma for linear threshold functions. Our main analytical tool is the Littlewood-Offord Lemma from additive combinatorics.

### Lift-and-Round to Improve Weighted Completion Time on Unrelated Machines

Authors: Nikhil Bansal, Ola Svensson, Aravind Srinivasan
Abstract: We consider the problem of scheduling jobs on unrelated machines so as to minimize the sum of weighted completion times. Our main result is a $(3/2-c)$-approximation algorithm for some fixed $c>0$, improving upon the long-standing bound of 3/2 (independently due to Skutella, Journal of the ACM, 2001, and Sethuraman & Squillante, SODA, 1999). To do this, we first introduce a new lift-and-project based SDP relaxation for the problem. This is necessary as the previous convex programming relaxations have an integrality gap of $3/2$. Second, we give a new general bipartite-rounding procedure that produces an assignment with certain strong negative correlation properties.

### A Note on Fault Tolerant Reachability for Directed Graphs

Authors: Loukas Georgiadis, Robert E. Tarjan
Abstract: In this note we describe an application of low-high orders in fault-tolerant network design. Baswana et al. [DISC 2015] study the following reachability problem. We are given a flow graph $G = (V, A)$ with start vertex $s$, and a spanning tree $T =(V, A_T)$ rooted at $s$. We call a set of arcs $A'$ valid if the subgraph $G' = (V, A_T \cup A')$ of $G$ has the same dominators as $G$. The goal is to find a valid set of minimum size. Baswana et al. gave an $O(m \log{n})$-time algorithm to compute a minimum-size valid set in $O(m \log{n})$ time, where $n = |V|$ and $m = |A|$. Here we provide a simple $O(m)$-time algorithm that uses the dominator tree $D$ of $G$ and a low-high order of it.

### A communication game related to the sensitivity conjecture

Authors: Justin Gilmer, Michal Koucký, Michael Saks
Abstract: One of the major outstanding foundational problems about boolean functions is the sensitivity conjecture, which (in one of its many forms) asserts that the degree of a boolean function (i.e. the minimum degree of a real polynomial that interpolates the function) is bounded above by some fixed power of its sensitivity (which is the maximum vertex degree of the graph defined on the inputs where two inputs are adjacent if they differ in exactly one coordinate and their function values are different). We propose an attack on the sensitivity conjecture in terms of a novel two-player communication game. A lower bound of the form $n^{\Omega(1)}$ on the cost of this game would imply the sensitivity conjecture.

To investigate the problem of bounding the cost of the game, three natural (stronger) variants of the question are considered. For two of these variants, protocols are presented that show that the hoped for lower bound does not hold. These protocols satisfy a certain monotonicity property, and (in contrast to the situation for the two variants) we show that the cost of any monotone protocol satisfies a strong lower bound.

There is an easy upper bound of $\sqrt{n}$ on the cost of the game. We also improve slightly on this upper bound.

### On the Computational Complexity of Limit Cycles in Dynamical Systems

Authors: Christos H. Papadimitriou, Nisheeth K. Vishnoi
Abstract: We study the Poincare-Bendixson theorem for two-dimensional continuous dynamical systems in compact domains from the point of view of computation, seeking algorithms for finding the limit cycle promised by this classical result. We start by considering a discrete analogue of this theorem and show that both finding a point on a limit cycle, and determining if a given point is on one, are PSPACE-complete.

For the continuous version, we show that both problems are uncomputable in the real complexity sense; i.e., their complexity is arbitrarily high. Subsequently, we introduce a notion of an "approximate cycle" and prove an "approximate" Poincar\'e-Bendixson theorem guaranteeing that some orbits come very close to forming a cycle in the absence of approximate fixpoints; surprisingly, it holds for all dimensions. The corresponding computational problem defined in terms of arithmetic circuits is PSPACE-complete.

### Cost Minimizing Online Algorithms for Energy Storage Management with Worst-case Guarantee

Authors: Chi-Kin Chau, Guanglin Zhang, Minghua Chen
Abstract: The fluctuations of electricity prices in demand response schemes and intermittency of renewable energy supplies necessitate the adoption of energy storage in microgrids. However, it is challenging to design effective real-time energy storage management strategies that can deliver assured optimality, without being hampered by the uncertainty of volatile electricity prices and renewable energy supplies. This paper presents a simple effective online algorithm for the charging and discharging decisions of energy storage that minimizes the electricity cost in the presence of electricity price fluctuations and renewable energy supplies, without relying on the future information of prices, demands or renewable energy supplies. The proposed algorithm is supported by a near-best worst-case guarantee (i.e., competitive ratio), as compared to the offline optimal decisions based on full future information. Furthermore, the algorithm can be adapted to take advantage of limited future information, if available. By simulations on real-world data, it is observed that the proposed algorithms can achieve satisfactory outcome in practice.

### Lower bounds for constant query affine-invariant LCCs and LTCs

Authors: Arnab Bhattacharyya, Sivakanth Gopi
Abstract: Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is that they seem well-suited to admit local correctors and testers.

In this work, we give lower bounds on the length of locally correctable and locally testable affine-invariant codes with constant query complexity. We show that if a code $\mathcal{C} \subset \Sigma^{\mathbb{K}^n}$ is an $r$-query locally correctable code (LCC), where $\mathbb{K}$ is a finite field and $\Sigma$ is a finite alphabet, then the number of codewords in $\mathcal{C}$ is at most $\exp(O_{\mathbb{K}, r, |\Sigma|}(n^{r-1}))$. Also, we show that if $\mathcal{C} \subset \Sigma^{\mathbb{K}^n}$ is an $r$-query locally testable code (LTC), then the number of codewords in $\mathcal{C}$ is at most $\exp(O_{\mathbb{K}, r, |\Sigma|}(n^{r-2}))$. The dependence on $n$ in these bounds is tight for constant-query LCCs/LTCs, since Guo, Kopparty and Sudan (ITCS 13) construct affine-invariant codes via lifting that have the same asymptotic tradeoffs. Note that our result holds for non-linear codes, whereas previously, Ben-Sasson and Sudan (RANDOM 11) assumed linearity to derive similar results.

Our analysis uses higher-order Fourier analysis. In particular, we show that the codewords corresponding to an affine-invariant LCC/LTC must be far from each other with respect to Gowers norm of an appropriate order. This then allows us to bound the number of codewords, using known decomposition theorems which approximate any bounded function in terms of a finite number of low-degree non-classical polynomials, upto a small error in the Gowers norm.

### Calculating the Unrooted Subtree Prune-and-Regraft Distance

Authors: Chris Whidden, Frederick A. Matsen IV
Abstract: The subtree prune-and-regraft (SPR) distance metric is a fundamental way of comparing evolutionary trees. It has wide-ranging applications, such as to study lateral genetic transfer, viral recombination, and Markov chain Monte Carlo phylogenetic inference. Although the rooted version of SPR distance can be computed relatively efficiently between rooted trees using fixed-parameter-tractable maximum agreement forest (MAF) algorithms, no MAF formulation is known for the unrooted case. Correspondingly, previous algorithms are unable to compute unrooted SPR distances larger than 7.

In this paper, we substantially advance understanding of and computational algorithms for the unrooted SPR distance. First we identify four properties of minimal SPR paths, each of which suggests that no MAF formulation exists in the unrooted case. We then prove the 2008 conjecture of Hickey et al. that chain reduction preserves the unrooted SPR distance. This reduces the problem to a linear size problem kernel, substantially improving on the previous best quadratic size kernel. Then we introduce a new lower bound on the unrooted SPR distance called the replug distance that is amenable to MAF methods, and give an efficient fixed-parameter algorithm for calculating it. Finally, we develop a "progressive A*" search algorithm using multiple heuristics, including the TBR and replug distances, to exactly compute the unrooted SPR distance. Our algorithm is nearly two orders of magnitude faster than previous methods on small trees, and allows computation of unrooted SPR distances as large as 14 on trees with 50 leaves.

### Tradeoffs for nearest neighbors on the sphere

Authors: Thijs Laarhoven
Abstract: We consider tradeoffs between the query and update complexities for the (approximate) nearest neighbor problem on the sphere, extending the recent spherical filters to sparse regimes and generalizing the scheme and analysis to account for different tradeoffs. In a nutshell, for the sparse regime the tradeoff between the query complexity $n^{\rho_q}$ and update complexity $n^{\rho_u}$ for data sets of size $n$ is given by the following equation in terms of the approximation factor $c$ and the exponents $\rho_q$ and $\rho_u$: $$c^2\sqrt{\rho_q}+(c^2-1)\sqrt{\rho_u}=\sqrt{2c^2-1}.$$

For small $c=1+\epsilon$, minimizing the time for updates leads to a linear space complexity at the cost of a query time complexity $n^{1-4\epsilon^2}$. Balancing the query and update costs leads to optimal complexities $n^{1/(2c^2-1)}$, matching bounds from [Andoni-Razenshteyn, 2015] and [Dubiner, IEEE-TIT'10] and matching the asymptotic complexities of [Andoni-Razenshteyn, STOC'15] and [Andoni-Indyk-Laarhoven-Razenshteyn-Schmidt, NIPS'15]. A subpolynomial query time complexity $n^{o(1)}$ can be achieved at the cost of a space complexity of the order $n^{1/(4\epsilon^2)}$, matching the bound $n^{\Omega(1/\epsilon^2)}$ of [Andoni-Indyk-Patrascu, FOCS'06] and [Panigrahy-Talwar-Wieder, FOCS'10] and improving upon results of [Indyk-Motwani, STOC'98] and [Kushilevitz-Ostrovsky-Rabani, STOC'98].

For large $c$, minimizing the update complexity results in a query complexity of $n^{2/c^2+O(1/c^4)}$, improving upon the related exponent for large $c$ of [Kapralov, PODS'15] by a factor $2$, and matching the bound $n^{\Omega(1/c^2)}$ of [Panigrahy-Talwar-Wieder, FOCS'08]. Balancing the costs leads to optimal complexities $n^{1/(2c^2-1)}$, while a minimum query time complexity can be achieved with update complexity $n^{2/c^2+O(1/c^4)}$, improving upon the previous best exponents of Kapralov by a factor $2$.

### An approximation algorithm for Uniform Capacitated k-Median problem with 1 + {\epsilon} capacity violation

Authors: Jarosław Byrka, Bartosz Rybicki, Sumedha Uniyal
Abstract: We study the Capacitated k-Median problem, for which all the known constant factor approximation algorithms violate either the number of facilities or the capacities. While the standard LP-relaxation can only be used for algorithms violating one of the two by a factor of at least two, Shi Li [SODA'15, SODA'16] gave algorithms violating the number of facilities by a factor of 1+{\epsilon} exploring properties of extended relaxations.

In this paper we develop a constant factor approximation algorithm for Uniform Capacitated k-Median violating only the capacities by a factor of 1+{\epsilon}. The algorithm is based on a configuration LP. Unlike in the algorithms violating the number of facilities, we cannot simply open extra few facilities at selected locations. Instead, our algorithm decides about the facility openings in a carefully designed dependent rounding process.

### Decoding Reed-Muller codes over product sets

Authors: John Kim, Swastik Kopparty
Abstract: We give a polynomial time algorithm to decode multivariate polynomial codes of degree $d$ up to half their minimum distance, when the evaluation points are an arbitrary product set $S^m$, for every $d < |S|$. Previously known algorithms can achieve this only if the set $S$ has some very special algebraic structure, or if the degree $d$ is significantly smaller than $|S|$. We also give a near-linear time randomized algorithm, which is based on tools from list-decoding, to decode these codes from nearly half their minimum distance, provided $d < (1-\epsilon)|S|$ for constant $\epsilon > 0$.

Our result gives an $m$-dimensional generalization of the well known decoding algorithms for Reed-Solomon codes, and can be viewed as giving an algorithmic version of the Schwartz-Zippel lemma.

### Parity Separation: A Scientifically Proven Method for Permanent Weight Loss

Abstract: Given an edge-weighted graph G, let PerfMatch(G) denote the weighted sum over all perfect matchings M in G, weighting each matching M by the product of weights of edges in M. If G is unweighted, this plainly counts the perfect matchings of G.

In this paper, we introduce parity separation, a new method for reducing PerfMatch to unweighted instances: For graphs G with edge-weights -1 and 1, we construct two unweighted graphs G1 and G2 such that PerfMatch(G) = PerfMatch(G1) - PerfMatch(G2). This yields a novel weight removal technique for counting perfect matchings, in addition to those known from classical #P-hardness proofs. We derive the following applications:

1. An alternative #P-completeness proof for counting unweighted perfect matchings.

2. C=P-completeness for deciding whether two given unweighted graphs have the same number of perfect matchings. To the best of our knowledge, this is the first C=P-completeness result for the "equality-testing version" of any natural counting problem that is not already #P-hard under parsimonious reductions.

3. An alternative tight lower bound for counting unweighted perfect matchings under the counting exponential-time hypothesis #ETH.

Our technique is based upon matchgates and the Holant framework. To make our #P-hardness proof self-contained, we also apply matchgates for an alternative #P-hardness proof of PerfMatch on graphs with edge-weights -1 and 1.

### Communication Lower Bounds for Statistical Estimation Problems via a Distributed Data Processing Inequality

Authors: Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff
Abstract: We study the tradeoff between the statistical error and communication cost of distributed statistical estimation problems in high dimensions. In the distributed sparse Gaussian mean estimation problem, each of the $m$ machines receives $n$ data points from a $d$-dimensional Gaussian distribution with unknown mean $\theta$ which is promised to be $k$-sparse. The machines communicate by message passing and aim to estimate the mean $\theta$. We provide a tight (up to logarithmic factors) tradeoff between the estimation error and the number of bits communicated between the machines. This directly leads to a lower bound for the distributed sparse linear regression problem: to achieve the statistical minimax error, the total communication is at least $\Omega(\min\{n,d\}m)$, where $n$ is the number of observations that each machine receives and $d$ is the ambient dimension. We also give the first optimal simultaneous protocol in the dense case for mean estimation.

As our main technique, we prove a distributed data processing inequality, as a generalization of usual data processing inequalities, which might be of independent interest and useful for other problems.

### Congratulations, Dr. Lam!

from David Eppstein

Jenny Lam, my teaching assistant for algorithms this quarter, passed today her thesis defense. She has been working with Sandy Irani, primarily on online algorithms for replacement and memory management strategies in heterogeneous caches (such as web proxies that have to maintain copies of documents of widely varying sizes), and has three papers on that subject, one at ALENEX and two at Middleware. She also has another paper on security-related algorithms in submission, which I'm also a co-author on. My understanding is that she will be teaching next semester at Pomona College on a temporary basis, while she looks for a more permanent position. Congratulations!

### TR15-187 | A Note on Perfect Correctness by Derandomization | Nir Bitansky, Vinod Vaikuntanathan

from ECCC papers

In this note, we show how to transform a large class of erroneous cryptographic schemes into perfectly correct ones. The transformation works for schemes that are correct on every input with probability noticeably larger than half, and are secure under parallel repetition. We assume the existence of one-way functions and of functions with deterministic (uniform) time complexity $2^{O(n)}$ and non-deterministic circuit complexity $2^{\Omega(n)}$. The transformation complements previous results showing that public-key encryption and indistinguishability obfuscation that err on a noticeable fraction of inputs can be turned into ones that are often correct {\em for all inputs}. The technique relies on the idea of reverse randomization'' [Naor, Crypto 1989] and on Nisan-Wigderson style derandomization, which was previously used in cryptography to obtain non-interactive witness-indistinguishable proofs and commitment schemes [Barak, Ong and Vadhan, Crypto 2003].

### TR15-186 | On the Relationship between Statistical Zero-Knowledge and Statistical Randomized Encodings | Benny Applebaum, Pavel Raykov

from ECCC papers

\emph{Statistical Zero-knowledge proofs} (Goldwasser, Micali and Rackoff, SICOMP 1989) allow a computationally-unbounded server to convince a computationally-limited client that an input $x$ is in a language $\Pi$ without revealing any additional information about $x$ that the client cannot compute by herself. \emph{Randomized encoding} (RE) of functions (Ishai and Kushilevitz, FOCS 2000) allows a computationally-limited client to publish a single (randomized) message, $E(x)$, from which the server learns whether $x$ is in $\Pi$ and nothing else. It is known that SRE, the class of problems that admit statistically private randomized encoding with polynomial-time client and computationally-unbounded server, is contained in the class SZK of problems that have statistical zero-knowledge proof. However, the exact relation between these two classes, and, in particular, the possibility of equivalence was left as an open problem. In this paper, we explore the relationship between SRE and SZK, and derive the following results: (1) In a non-uniform setting, statistical randomized encoding with one-side privacy (1RE) is equivalent to non-interactive statistical zero-knowledge (NISZK). These variants were studied in the past as natural relaxation/strengthening of the original notions. Our theorem shows that proving SRE=SZK is equivalent to showing that 1RE=SRE and SZK=NISZK. The latter is a well-known open problem (Goldreich, Sahai, Vadhan, CRYPTO 1999). (2) If SRE is non-trivial (not in BPP), then infinitely-often one-way functions exist. The analog hypothesis for SZK yields only \emph{auxiliary-input} one-way functions (Ostrovsky, Structure in Complexity Theory, 1991), which is believed to be a significantly weaker implication. (3) If there exists an average-case hard language with \emph{perfect randomized encoding}, then collision-resistance hash functions (CRH) exist. Again, a similar assumption for SZK implies only constant-round statistically-hiding commitments, a primitive which seems weaker than CRH. We believe that our results sharpen the relationship between SRE and SZK and illuminates the core differences between these two classes.

### Research instructorship at Princeton and IAS (apply by Dec 15, 2015)

from CCI: jobs

The newly created 3-year positions for outstanding young theorists. Combining research with teaching duties, these positions come with attractive benefits and working conditions. Typically, the 1st and 3rd years are spent at Princeton University and the 2nd year is spent at the IAS. These arrangements are flexible. The application process for this position is separate from Princeton postdoc applic

Email: mbraverm@cs.princeton.edu

by theorycsjobs at November 24, 2015 05:30 PM UTC

### TR15-185 | Lower bounds for constant query affine-invariant LCCs and LTCs | Sivakanth Gopi, Arnab Bhattacharyya

from ECCC papers

Affine-invariant codes are codes whose coordinates form a vector space over a finite field and which are invariant under affine transformations of the coordinate space. They form a natural, well-studied class of codes; they include popular codes such as Reed-Muller and Reed-Solomon. A particularly appealing feature of affine-invariant codes is that they seem well-suited to admit local correctors and testers. In this work, we give lower bounds on the length of locally correctable and locally testable affine-invariant codes with constant query complexity. We show that if a code $\mathcal{C} \subset \Sigma^{\mathbb{K}^n}$ is an $r$-query locally correctable code (LCC), where $\mathbb{K}$ is a finite field and $\Sigma$ is a finite alphabet, then the number of codewords in $\mathcal{C}$ is at most $\exp(O_{\mathbb{K}, r, |\Sigma|}(n^{r-1}))$. Also, we show that if $\mathcal{C} \subset \Sigma^{\mathbb{K}^n}$ is an $r$-query locally testable code (LTC), then the number of codewords in $\mathcal{C}$ is at most $\exp(O_{\mathbb{K}, r, |\Sigma|}(n^{r-2}))$. The dependence on $n$ in these bounds is tight for constant-query LCCs/LTCs, since Guo, Kopparty and Sudan (ITCS 13) construct affine-invariant codes via lifting that have the same asymptotic tradeoffs. Note that our result holds for non-linear codes, whereas previously, Ben-Sasson and Sudan (RANDOM 11) assumed linearity to derive similar results. Our analysis uses higher-order Fourier analysis. In particular, we show that the codewords corresponding to an affine-invariant LCC/LTC must be far from each other with respect to Gowers norm of an appropriate order. This then allows us to bound the number of codewords, using known decomposition theorems which approximate any bounded function in terms of a finite number of low-degree non-classical polynomials, upto a small error in the Gowers norm.

### Postdoc at North Carolina State University (apply by January 1, 2016)

from CCI: jobs

The Dept of Computer Science at NCState University, seeks applications for a two year Postdoc position in the Theory In Practice group of Dr. Blair D. Sullivan.

Position funded by Moore Foundation Data-Driven Discovery Initiative; research focus on improving practicality of parameterized algorithms using graph structure.

Anticipated start date in May-Sept 2016.

Email: blair_sullivan@ncsu.edu

by theorycsjobs at November 24, 2015 12:04 PM UTC

### Postdoc at Princeton Computer Science (apply by Dec 15, 2015)

from CCI: jobs

The Department of Computer Science at Princeton University is seeking applications for postdoctoral or more senior research positions in theoretical computer science and theoretical machine learning. Positions are for one year with the possibility of renewal. Candidates must have a PhD in Computer Science or a related field. These positions are subject to the University’s background check poli

Email: mbraverm@cs.princeton.edu

by theorycsjobs at November 24, 2015 02:21 AM UTC

### Talk, be merry, and be rational

from Scott Aaronson

Yesterday I wrote a statement on behalf of a Scott Alexander SlateStarCodex/rationalist meetup, which happened last night at MIT (in the same room where I teach my graduate class), and which I’d really wanted to attend but couldn’t.  I figured I’d share the statement here:

I had been looking forward to attending tonight’s MIT SlateStarCodex meetup as I hardly ever look forward to anything. Alas, I’m now stuck in Chicago, with my flight cancelled due to snow, and with all flights for the next day booked up. But instead of continuing to be depressed about it, I’ve decided to be happy that this meetup is even happening at all—that there’s a community of people who can read, let’s say, a hypothetical debate moderator questioning Ben Carson about what it’s like to be a severed half-brain, and simply be amused, instead of silently trying to figure out who benefits from the post and which tribe the writer belongs to. (And yes, I know: the answer is the gray tribe.) And you can find this community anywhere—even in Cambridge, Massachusetts! Look, I spend a lot of time online, just getting more and more upset reading social justice debates that are full of people calling each other douchebags without even being able to state anything in the same galactic supercluster as the other side’s case. And then what gives me hope for humanity is to click over to the slatestarcodex tab, and to see all the hundreds of comments (way more than my blog gets) by people who disagree with each other but who all basically get it, who all have minds that don’t make me despair. And to realize that, when Scott Alexander calls an SSC meetup, he can fill a room just about anywhere … well, at least anywhere I would visit. So talk, be merry, and be rational.

I’m now back in town, and told by people who attended the meetup that it was crowded, disorganized, and great.  And now I’m off to Harvard, to attend the other Scott A.’s talk “How To Ruin A Perfectly Good Randomized Controlled Trial.”

Update (Nov. 24) Scott Alexander’s talk at Harvard last night was one of the finest talks I’ve ever attended. He was introduced to rapturous applause as simply “the best blogger on the Internet,” and as finally an important speaker, in a talk series that had previously wasted everyone’s time with the likes of Steven Pinker and Peter Singer. (Scott demurred that his most notable accomplishment in life was giving the talk at Harvard that he was just now giving.) The actual content, as Scott warned from the outset, was “just” a small subset of a basic statistics course, but Scott brought each point alive with numerous recent examples, from psychiatry, pharmacology, and social sciences, where bad statistics or misinterpretations of statistics were accepted by nearly everyone and used to set policy. (E.g., Alcoholics Anonymous groups that claimed an “over 95%” success rate, because the people who relapsed were kicked out partway through and not counted toward the total.) Most impressively, Scott leapt immediately into the meat, ended after 20 minutes, and then spent the next two hours just taking questions. Scott is publicity-shy, but I hope for others’ sake that video of the talk will eventually make its way online.

Then, after the talk, I had the honor of meeting two fellow Boston-area rationalist bloggers, Kate Donovan and Jesse Galef. Yes, I said “fellow”: for almost a decade, I’ve considered myself on the fringes of the “rationalist movement.” I’d hang out a lot with skeptic/effective-altruist/transhumanist/LessWrong/OvercomingBias people (who are increasingly now SlateStarCodex people), read their blogs, listen and respond to their arguments, answer their CS theory questions. But I was always vaguely uncomfortable identifying myself with any group that even seemed to define itself by how rational it was compared to everyone else (even if the rationalists constantly qualified their self-designation with “aspiring”!). Also, my rationalist friends seemed overly interested in questions like how to prevent malevolent AIs from taking over the world, which I tend to think we lack the tools to make much progress on right now (though, like with many other remote possibilities, I’m happy for some people to work on them and see if they find anything interesting).

So, what changed? Well, in the debates about social justice, public shaming, etc. that have swept across the Internet these past few years, it seems to me that my rationalist friends have proven themselves able to weigh opposing arguments, examine their own shortcomings, resist groupthink and hysteria from both sides, and attack ideas rather than people, in a way that the wider society—and most depressingly to me, the “enlightened, liberal” part of society—has often failed. In a real-world test (“real-world,” in this context, meaning social media…), the rationalists have walked the walk and rationaled the rational, and thus they’ve given me no choice but to stand up and be counted as one of them.

Have a great Thanksgiving, those of you in the US!

Another Update: Dana, Lily, and I had the honor of having Scott Alexander over for dinner tonight. I found this genius of human nature, who took so much flak last year for defending me, to be completely uninterested in discussing anything related to social justice or online shaming. Instead, his gaze was fixed on the eternal: he just wanted to grill me all evening about physics and math and epistemology. Having recently read this Nature News article by Ron Cowen, he kept asking me things like: “you say that in quantum gravity, spacetime itself is supposed to dissolve into some sort of network of qubits. Well then, how does each qubit know which other qubits it’s supposed to be connected to? Are there additional qubits to specify the connectivity pattern? If so, then doesn’t that cause an infinite regress?” I handwaved something about AdS/CFT, where a dynamic spacetime is supposed to emerge from an ordinary quantum theory on a fixed background specified in advance. But I added that, in some sense, he had rediscovered the whole problem of quantum gravity that’s confused everyone for almost a century: if quantum mechanics presupposes a causal structure on the qubits or whatever other objects it talks about, then how do you write down a quantum theory of the causal structures themselves?

I’m sure there’s a lesson in here somewhere about what I should spend my time on.

### Telephone primes

from David Eppstein

This weekend I helped add a new sequence to OEIS, A264737 of the prime numbers that divide at least one telephone number (the numbers of matchings in a complete graph etc).

The telephone numbers obey a simple recurrence T(n) = T(n-1) + (n-1)T(n-2), and it's easy to test whether a prime number p divides at least one telephone number by running this recurrence modulo p. Whenever n is 1 mod p, the right hand side of the recurrence simplifies to T(n-1) mod p, and we get two consecutive numbers that are equal mod p; After that point, the recurrence continues as it would from its initial conditiions (two consecutive ones), multiplied mod p by some unknown factor. Therefore, the recurrence mod p either repeats exactly with period p, or it becomes identically zero (as it does for p=2), or it repeats with a higher period that is a multiple of p and a divisor of p(p–1), where all sub-periods of length p are multiples of each other. In particular, if p divides at least one telephone number, it divides infinitely many of them, whose positions are periodic with period p.

All primes divide at least one Fibonacci number (a sequence of numbers with an even simpler recurrence) but that is not true for the telephone numbers. For instance, the telephone numbers mod 3 form the infinite repeating sequence 1,1,2,1,1,2,... with no zeros. So how many of the prime numbers are in the new sequence? A heuristic estimate suggests that the telephone primes should form a 1–1/e fraction of all primes (around 63.21%): p is a telephone prime when there is a zero in the first p terms of the recurrence sequence mod p, and if we use random numbers instead of the actual recurrence then the probability of not getting a zero is approximately 1/e. With this estimate in mind, I tried some computational experiments and found that among the first 10000 primes, 6295 of them (approximately 63%) are in the sequence. Pretty accurate, I think! But I have no idea how to approach a rigorous proof that this estimate should be correct.

Incidentally, while looking up background material for this I ran into a paper by Rote in 1992 that observes a relationship between the telephone number and another sequence, A086828. A086828 counts the number of states in a dynamic programming algorithm for the traveling salesman problem on graphs of bandwidth k, for a parameter k. So its calculation, in the mid-1980s, can be seen as an early example of the parameterized analysis of algorithms. It has the same recurrence relation as the telephone numbers, but with different initial conditions, so we can consider using this sequence instead of the telephone numbers. But the same analysis above showing that all subperiods of length p are similar applies equally well to this sequence, showing that after an initial transient of length p, all subperiods are either identically zero or similar to the corresponding subperiods of the telephone numbers. So if we ask which primes divide at least one member of A086828, we get almost the same answer, except possibly for some additional primes that either divide one of the first p numbers of A086828 (and then no other members of A086828 later in the sequence) or that divide all but finitely many members of A086828.

### Star Trek Computing

In the wake of Leonard Nimoy's death last February, I decided to rewatch the entire original Star Trek series, all 79 episodes. I had watched them each many times over in high school in the 70's, though the local station removed a scene or two from each episode to add commercial time and I often missed the opening segment because I didn't get home from school in time. Back in those stone ages we had no DVR or other method to record shows. I hadn't seen many episodes of the original series since high school.

Now I can watch the entire episodes whenever I want in full and in order through the magic of Netflix. I finished this quest a few days ago. Some spoilers below.

I could talk about the heavy sexism, the ability to predict future technologies (the flat screen TV in episode 74), the social issues in the 23rd century as viewed from the 60's, or just the lessons in leadership you can get from Kirk. Given the topic of this blog, let's talk about computing in Star Trek which they often just get so wrong, such as when Spock asks the computer to compute the last digit of π to force Jack-the-Ripper to remove his consciousness from the ship's computers.

Too many episodes end with Kirk convincing a computer or robot to destroy itself. I'd like to see him try that with Siri. In one such episode "The Ultimate Computer", a new computer is installed in the Enterprise that replaces most of the crew. A conversation between Kirk and McCoy sounds familiar to many we have today (source).

MCCOY: Did you see the love light in Spock's eyes? The right computer finally came along. What's the matter, Jim?
KIRK: I think that thing is wrong, and I don't know why.
MCCOY: I think it's wrong, too, replacing men with mindless machines.
KIRK: I don't mean that. I'm getting a Red Alert right here. (the back of his head) That thing is dangerous. I feel. (hesitates) Only a fool would stand in the way of progress, if this is progress. You have my psychological profiles. Am I afraid of losing my job to that computer?
MCCOY: Jim, we've all seen the advances of mechanisation. After all, Daystrom did design the computers that run this ship.
KIRK: Under human control.
MCCOY: We're all sorry for the other guy when he loses his job to a machine. When it comes to your job, that's different. And it always will be different.
KIRK: Am I afraid of losing command to a computer? Daystrom's right. I can do a lot of other things. Am I afraid of losing the prestige and the power that goes with being a starship captain? Is that why I'm fighting it? Am I that petty?
MCCOY: Jim, if you have the awareness to ask yourself that question, you don't need me to answer it for you. Why don't you ask James T. Kirk? He's a pretty honest guy.

Later in the episode the computer starts behaving badly and Kirk has to convince it to shut itself down. But what if the computer just did its job? Is that our real future: Ships that travel to stars controlled only by machine. Or are we already there?

by Lance Fortnow (noreply@blogger.com) at November 23, 2015 03:30 PM UTC

### TEMPO: Feature-Endowed Teichm\"{u}ller Extremal Mappings of Point Clouds

Authors: Ting Wei Meng, Pui Tung Choi, Lok Ming Lui
Abstract: In recent decades, the use of 3D point clouds has been widespread in computer industry. The development of techniques in analyzing point clouds is increasingly important. In particular, mapping of point clouds has been a challenging problem. In this paper, we develop a discrete analogue of the Teichm\"{u}ller extremal mappings, which guarantee uniform conformality distortions, on point cloud surfaces. Based on the discrete analogue, we propose a novel method called TEMPO for computing Teichm\"{u}ller extremal mappings between feature-endowed point clouds. Using our proposed method, the Teichm\"{u}ller metric is introduced for evaluating the dissimilarity of point clouds. Consequently, our algorithm enables accurate recognitions and classifications of point clouds. Experimental results demonstrate the effectiveness of our proposed method.

### Use of Eigenvector Centrality to Detect Graph Isomorphism

Authors: Natarajan Meghanathan
Abstract: Graph Isomorphism is one of the classical problems of graph theory for which no deterministic polynomial-time algorithm is currently known, but has been neither proven to be NP-complete. Several heuristic algorithms have been proposed to determine whether or not two graphs are isomorphic (i.e., structurally the same). In this research, we propose to use the sequence (either the non-decreasing or nonincreasing order) of eigenvector centrality (EVC) values of the vertices of two graphs as a precursor step to decide whether or not to further conduct tests for graph isomorphism. The eigenvector centrality of a vertex in a graph is a measure of the degree of the vertex as well as the degrees of its neighbors. We hypothesize that if the non-increasing (or non-decreasing) order of listings of the EVC values of the vertices of two test graphs are not the same, then the two graphs are not isomorphic. If two test graphs have an identical non-increasing order of the EVC sequence, then they are declared to be potentially isomorphic and confirmed through additional heuristics. We test our hypothesis on random graphs (generated according to the Erdos-Renyi model) and we observe the hypothesis to be indeed true: graph pairs that have the same sequence of non-increasing order of EVC values have been confirmed to be isomorphic using the well-known Nauty software.

### Tree Embedding and Directed Steiner Problems

Authors: Bundit Laekhanukit
Abstract: Tree-Embedding is a powerful technique in the area of approximation algorithms as it reduces many diffcult problems like {\em group Steiner tree} (GST) on general graphs into amenable tree intances. However, the developments on tree-embedding are pertained only to undirected graphs, thus rendering it useless against problems on directed graphs like {\em directed Steiner tree} (DST) and its generalization {\em $k$-edge connected directed Steiner tree} ($k$-DST). The latter problem, $k$-DST, is a notorious problem that has no known non-trivial approximation algorithm despites having been mentioned many times in literature, e.g., by Feldman et al. [JCSS'12], by Cheriyan et al. [TALG'14] and by Laekhanukit [SODA'14]. We explore the possibility of obtaining a non-trivial approximation algorithm for $k$-DST via tree-embedding. To be precise, in $k$-GST, given a digraph $G$ on $n$ vertices with edge-costs, a root vertex $r$, a set of $h$ terminals $T$ and an integer $k$, the goal is to find a min-cost subgraph $H$ of $G$ that connects $r$ to each terminal $t\in T$ by $k$ edge-disjoint $r,t$-paths. We reduce $k$-GST on general graphs into instances on trees. As a result, we devise an $O(Dk^{D-1}\log h)$-approximation algorithm for $k$-DST on directed acyclic graphs (DAGs) with $D$ layers which extends to a special case of $k$-DST on general graphs'' when an optimal solution has $k$ edge-disjoint $r,t$-paths, each of length at most $D$, for every terminal $t\in T$.

Our contribution is two fold. First, we make a progress toward developing an approximation algorithm for $k$-DST. We remark that the $k^{1/4-\epsilon}$-hardness instance of $k$-DST is a DAG with $5$ layers, and our algorithm gives $O(k^3\log h)$-approximation for this special case. Second, we initiate the study of tree-embedding on directed graphs, which might later have more applications.

### Near-Optimal UGC-hardness of Approximating Max k-CSP_R

Authors: Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan
Abstract: In this paper, we prove an almost-optimal hardness for Max $k$-CSP$_R$ based on Khot's Unique Games Conjecture (UGC). In Max $k$-CSP$_R$, we are given a set of predicates each of which depends on exactly $k$ variables. Each variable can take any value from $1, 2, \dots, R$. The goal is to find an assignment to variables that maximizes the number of satisfied predicates.

Assuming the Unique Games Conjecture, we show that it is NP-hard to approximate Max $k$-CSP$_R$ to within factor $2^{O(k \log k)}(\log R)^{k/2}/R^{k - 1}$ for any $k, R$. To the best of our knowledge, this result improves on all the known hardness of approximation results when $3 \leq k = o(\log R/\log \log R)$. In this case, the previous best hardness result was NP-hardness of approximating within a factor $O(k/R^{k-2})$ by Chan. When $k = 2$, our result matches the best known UGC-hardness result of Khot, Kindler, Mossel and O'Donnell.

In addition, by extending an algorithm for Max 2-CSP$_R$ by Kindler, Kolla and Trevisan, we provide an $\Omega(\log R/R^{k - 1})$-approximation algorithm for Max $k$-CSP$_R$. This algorithm implies that our inapproximability result is tight up to a factor of $2^{O(k \log k)}(\log R)^{k/2 - 1}$. In comparison, when $3 \leq k$ is a constant, the previously known gap was $O(R)$, which is significantly larger than our gap of $O(\text{polylog } R)$.

Finally, we show that we can replace the Unique Games Conjecture assumption with Khot's $d$-to-1 Conjecture and still get asymptotically the same hardness of approximation.

### mplrs: A scalable parallel vertex/facet enumeration code

Authors: David Avis, Charles Jordan
Abstract: Binary embeddings provide efficient and powerful ways to perform operations on large scale data. However binary embedding typically requires long codes in order to preserve the discriminative power of the input space. Thus binary coding methods traditionally suffer from high computation and storage costs in such a scenario. To address this problem, we propose Circulant Binary Embedding (CBE) which generates binary codes by projecting the data with a circulant matrix. The circulant structure allows us to use Fast Fourier Transform algorithms to speed up the computation. For obtaining $k$-bit binary codes from $d$-dimensional data, this improves the time complexity from $O(dk)$ to $O(d\log{d})$, and the space complexity from $O(dk)$ to $O(d)$.