# Theory of Computing Blog Aggregator

at November 27, 2015 02:49 PM UTC

at November 27, 2015 02:45 PM UTC

at November 27, 2015 02:40 PM UTC

at November 27, 2015 02:38 PM UTC

at November 26, 2015 07:42 AM UTC

**Authors: **Eric Allender, Joshua A. Grochow, Cristopher Moore **Download:** PDF**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.

at November 26, 2015 01:41 AM UTC

**Authors: **Jon Lee, Viswanath Nagarajan, Xiangkun Shen **Download:** PDF**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).

at November 26, 2015 01:42 AM UTC

**Authors: **Peter Bürgisser **Download:** PDF**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.

at November 26, 2015 01:40 AM UTC

**Authors: **Teng Li, Vikram K. Narayana, Tarek El-Ghazawi **Download:** PDF**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.

at November 26, 2015 01:42 AM UTC

**Authors: **Manoj M. Prabhakaran, Vinod M. Prabhakaran **Download:** PDF**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.

at November 26, 2015 01:40 AM UTC

at November 25, 2015 03:32 AM UTC

**Authors: **Daniel M. Kane, Ryan Williams **Download:** PDF**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.

at November 25, 2015 01:45 AM UTC

**Authors: **Nikhil Bansal, Ola Svensson, Aravind Srinivasan **Download:** PDF**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.

at November 25, 2015 01:51 AM UTC

**Authors: **Loukas Georgiadis, Robert E. Tarjan **Download:** PDF**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.

at November 25, 2015 01:45 AM UTC

**Authors: **Justin Gilmer, Michal Koucký, Michael Saks **Download:** PDF**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.

at November 25, 2015 01:44 AM UTC

**Authors: **Christos H. Papadimitriou, Nisheeth K. Vishnoi **Download:** PDF**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.

at November 25, 2015 12:00 AM UTC

**Authors: **Chi-Kin Chau, Guanglin Zhang, Minghua Chen **Download:** PDF**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.

at November 25, 2015 01:53 AM UTC

**Authors: **Arnab Bhattacharyya, Sivakanth Gopi **Download:** PDF**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.

at November 25, 2015 01:44 AM UTC

**Authors: **Chris Whidden, Frederick A. Matsen IV **Download:** PDF**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.

at November 25, 2015 01:48 AM UTC

**Authors: **Thijs Laarhoven **Download:** PDF**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$.

at November 25, 2015 12:00 AM UTC

**Authors: **Jarosław Byrka, Bartosz Rybicki, Sumedha Uniyal **Download:** PDF**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.

at November 25, 2015 01:53 AM UTC

**Authors: **John Kim, Swastik Kopparty **Download:** PDF**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.

at November 25, 2015 01:45 AM UTC

**Authors: **Radu Curticapean **Download:** PDF**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.

at November 25, 2015 01:45 AM UTC

**Authors: **Mark Braverman, Ankit Garg, Tengyu Ma, Huy L. Nguyen, David P. Woodruff **Download:** PDF**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.

at November 25, 2015 01:40 AM UTC

at November 24, 2015 10:49 PM UTC

at November 24, 2015 07:52 PM UTC

at November 24, 2015 07:51 PM UTC

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

Webpage: http://jobs.princeton.edu/applicants/jsp/shared/position/JobDetails_css.jsp?postingId=216653

Email: mbraverm@cs.princeton.edu

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

at November 24, 2015 02:37 PM UTC

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.

Webpage: http://www.csc.ncsu.edu/faculty/bdsullivan

Email: blair_sullivan@ncsu.edu

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

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

Webpage: http://https://jobs.princeton.edu/applicants/jsp/shared/position/JobDetails_css.jsp?postingId=216580

Email: mbraverm@cs.princeton.edu

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

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.

by Scott at November 23, 2015 09:07 PM UTC

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.

at November 23, 2015 07:27 PM UTC

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

**Authors: **Ting Wei Meng, Pui Tung Choi, Lok Ming Lui **Download:** PDF**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.

at November 23, 2015 01:46 AM UTC

**Authors: **Natarajan Meghanathan **Download:** PDF**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.

at November 23, 2015 01:45 AM UTC

**Authors: **Bundit Laekhanukit **Download:** PDF**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.

at November 23, 2015 01:46 AM UTC

**Authors: **Pasin Manurangsi, Preetum Nakkiran, Luca Trevisan **Download:** PDF**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.

at November 23, 2015 12:00 AM UTC

**Authors: **David Avis, Charles Jordan **Download:** PDF**Abstract: **We describe a new parallel implementation, mplrs, of the vertex enumeration
code lrs that uses the MPI parallel environment and can be run on a network of
computers. The implementation makes use of a C wrapper that essentially uses
the existing lrs code with only minor modifications. mplrs was derived from the
earlier parallel implementation plrs, written by G. Roumanis in C++. plrs uses
the Boost library and runs on a shared memory machine. In developing mplrs we
discovered a method of balancing the parallel tree search, called budgeting,
that greatly improves parallelization beyond the bottleneck encountered
previously at around 32 cores. This method can be readily adapted for use in
other reverse search enumeration codes. We also report some preliminary
computational results comparing parallel and sequential codes for vertex/facet
enumeration problems for convex polyhedra. The problems chosen span the range
from simple to highly degenerate polytopes. For most problems tested, the
results clearly show the advantage of using the parallel implementation mplrs
of the reverse search based code lrs, even when as few as 8 cores are
available. For some problems almost linear speedup was observed up to 1200
cores, the largest number of cores tested.

at November 23, 2015 01:47 AM UTC

**Authors: **Felix X. Yu, Aditya Bhaskara, Sanjiv Kumar, Yunchao Gong, Shih-Fu Chang **Download:** PDF**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)$.

We study two settings, which differ in the way we choose the parameters of the circulant matrix. In the first, the parameters are chosen randomly and in the second, the parameters are learned using the data. For randomized CBE, we give a theoretical analysis comparing it with binary embedding using an unstructured random projection matrix. The challenge here is to show that the dependencies in the entries of the circulant matrix do not lead to a loss in performance. In the second setting, we design a novel time-frequency alternating optimization to learn data-dependent circulant projections, which alternatively minimizes the objective in original and Fourier domains. In both the settings, we show by extensive experiments that the CBE approach gives much better performance than the state-of-the-art approaches if we fix a running time, and provides much faster computation with negligible performance degradation if we fix the number of bits in the embedding.

at November 23, 2015 01:42 AM UTC