# Theory of Computing Blog Aggregator

### Martin Gardner Centennial

Martin Gardner was born on October 21, 1914, so today is his Centennial (he died on May 22, 2010, at the age of 95). We've mentioned him in the blog before:

1.  The Life of Martin Gardner
2.  Contribute to the Gardner Centennial
3.  Another Post on Martin Gardner
4. I used the anagram Tim Andrer Gran in both my review of the Lipton-Regan book (see here) and my Applications of Ramsey Theory to History paper (see here)

So what can I add on his centennial?

1. He was not the first person to write on recreational mathematics, but he was certainly early and did it for a long time.
2. I suspect he influenced everyone reading this who is over 50. For every y, y is under 50 and reading this column, there exists x such that MG influenced x and x influenced y.
3. The line between recreational'' and serious'' math is sometimes blurry or hard to see. An obvious case of this was Euler and the Bridges problem leading to graph theory. At one time solving equations was done for competition, which seems recreational. Galois theory is not recreational.
4. Donald Knuth's book Selected Papers in Discrete Math (reviewed by me here) states I've never been able to see the boundary between scientific research and game playing.
5. I am reading a book  Martin Gardner in the 21st century which is papers by people who were inspired by him. The papers really do blur the distinction between recreational and serious. Some are rather difficult but all start out with a fun problem.
6. Aside from recreational math he did other things- magic, and debunking bad science.  (Fads and Fallacies in the name of science was excellent.) He was a well rounded person which is rare now.
7. Brian Hayes and Ian Stewart and others do what he did, but given the times we live in now, its hard capture the attention of a large segment of the public. (analogous to that when I was a kid there were only a handful of TV stations, now there are... too many?)
8. When I was in high school I went to the library looking for math books I could read (naive?). I found one of his books (collection of his columns) and began reading it. I learned about casting out nines and I learned what was to be the first theorem I ever learned a proof of outside of class (given that I was probably 12 it may be the first proof I learned ever). It was that (in todays lang) a graph is Eulerian iff every vertex is even degree.

by GASARCH (noreply@blogger.com) at October 21, 2014 03:09 PM UTC

### Algorithms that never get coded up

(There was a passing ref to this topic in the comments to one of Scott's blogs, so I thought I would pick up the theme.)

When I teach Formal Lang Theory I end up teaching them many algorithms that I don't think are ever coded up. Or if they are, I doubt they are used. A common refrain in my class is

Could you code this up?

Would you want to?

If the answers are YES and NO then they are enlightened.

Here are some examples of algorithms that are commonly taught but are never really used. They are still good to know

1. The algorithm that takes a DFA and makes a Regular Expression out of it. (I use the R(i,j,k) algorithm- R(i,j,k) is the set of all strings that take you from state i to state j using a subset of  {1,...,k} as intermediaries. One computes a reg exp for R(i,j,k) via dynamic programming. The actual reg expressions may get very long so I do not know if its poly time. But its not coded up since there is never a reason to go from a DFA to a Reg Exp. (There IS a reason to go from a Reg Exp to a DFA). Note that it IS good to know that REG EXP = DFA= NDFA so this IS worth teaching and knowing, AND its a nice example of Dyn Programming.
2. The algorithm that takes any CFG and puts it in Chomsky Normal form. The only grammars really used now (for compliers) are of a much more specialized type.
3. The algorithm that shows that and CFL is in P (O(n^3), though you can do better) that uses Chomsky Normal Form. Again, Nobody uses general grammars. Still good to know that CFL's are in P, and again a nice Dyn Programming algorithm.
4. Converting a PDA to a CFG. I doubt this is ever done. The converse is of course a key to compliers. But the converse is done for very specialized grammars, not general ones. Again though, good to know that CFG's and PDA's are equivalent. The PDA to CFG conversion is NOT nice.
5. Converting a Blah-tape Blah-head Turing Machine to a Blah'-tape, Blah'-head Turing Machine.  Important to know you can do it, not important to know the details, not worth coding up unless you are trying to win that contest where you want to get really small Univ TM's
6. All of the reductions in NP-completeness. I doubt any are actually done. Since we have very good SAT solvers there may be algorithms to convert problems TO SAT problems.
If I am wrong on any of these and something on the above list IS worth coding up and HAS been code up and IS being used, then I will be delighted to hear about it.

by GASARCH (noreply@blogger.com) at October 21, 2014 02:34 PM UTC

### An Improved Scheme for Asymmetric LSH

Authors: Anshumali Shrivastava, Ping Li
Abstract: A recent technical report developed a provably sublinear time algorithm for approximate \emph{Maximum Inner Product Search} (MIPS), by observing that inner products, after independent asymmetric transformations, can be converted into the problem of approximate near neighbor search in terms of the $L_2$ distance. We name the particular ALSH scheme in\cite{Report:ALSH_arXiv14} as {\em L2-ALSH}. In this study, we present another asymmetric transformation scheme which converts the problem of maximum inner products into the problem of maximum correlation search. The latter can be solved efficiently by "sign random projections". We name this new scheme as {\em Sign-ALSH}. Theoretical analysis shows that {\em Sign-ALSH} can be noticeably more advantageous than {\em L2-ALSH}. Our experimental study confirms the theoretical finding.

### Scalable Parallel Factorizations of SDD Matrices and Efficient Sampling for Gaussian Graphical Models

Authors: Dehua Cheng, Yu Cheng, Yan Liu, Richard Peng, Shang-Hua Teng
Abstract: Motivated by a sampling problem basic to computational statistical inference, we develop a nearly optimal algorithm for a fundamental problem in spectral graph theory and numerical analysis. Given an $n\times n$ SDDM matrix ${\bf \mathbf{M}}$, and a constant $-1 \leq p \leq 1$, our algorithm gives efficient access to a sparse $n\times n$ linear operator $\tilde{\mathbf{C}}$ such that $${\mathbf{M}}^{p} \approx \tilde{\mathbf{C}} \tilde{\mathbf{C}}^\top.$$ The solution is based on factoring ${\bf \mathbf{M}}$ into a product of simple and sparse matrices using squaring and spectral sparsification. For ${\mathbf{M}}$ with $m$ non-zero entries, our algorithm takes work nearly-linear in $m$, and polylogarithmic depth on a parallel machine with $m$ processors. This gives the first sampling algorithm that only requires nearly linear work and $n$ i.i.d. random univariate Gaussian samples to generate i.i.d. random samples for $n$-dimensional Gaussian random fields with SDDM precision matrices. For sampling this natural subclass of Gaussian random fields, it is optimal in the randomness and nearly optimal in the work and parallel complexity. In addition, our sampling algorithm can be directly extended to Gaussian random fields with SDD precision matrices.

### Proof Complexity Modulo the Polynomial Hierarchy: Understanding Alternation as a Source of Hardness

Authors: Hubie Chen
Abstract: We present and study a framework in which one can present alternation-based lower bounds on proof length in proof systems for quantified Boolean formulas. A key notion in this framework is that of proof system ensemble, which is (essentially) a sequence of proof systems where, for each, proof checking can be performed in the polynomial hierarchy. We introduce a proof system ensemble called relaxing QU-res which is based on the established proof system QU-resolution. Our main results include an exponential separation of the tree-like and general versions of relaxing QU-res, and an exponential lower bound for relaxing QU-res; these are analogs of classical results in propositional proof complexity.

### On the Influence of Graph Density on Randomized Gossiping

Authors: Robert Elsässer, Dominik Kaaser
Abstract: Information dissemination is a fundamental problem in parallel and distributed computing. In its simplest variant, the broadcasting problem, a message has to be spread among all nodes of a graph. A prominent communication protocol for this problem is based on the random phone call model (Karp et al., FOCS 2000). In each step, every node opens a communication channel to a randomly chosen neighbor for bi-directional communication.

Motivated by replicated databases and peer-to-peer networks, Berenbrink et al., ICALP 2010, considered the gossiping problem in the random phone call model. There, each node starts with its own message and all messages have to be disseminated to all nodes in the network. They showed that any $O(\log n)$-time algorithm in complete graphs requires $\Omega(\log n)$ message transmissions per node to complete gossiping, w.h.p, while for broadcasting the average number of transmissions per node is $O(\log\log n)$.

It is known that the $O(n\log\log n)$ bound on the number of transmissions required for randomized broadcasting in complete graphs cannot be achieved in sparse graphs even if they have best expansion and connectivity properties. In this paper, we analyze whether a similar influence of the graph density also holds w.r.t. the performance of gossiping. We study analytically and empirically the communication overhead generated by randomized gossiping in random graphs and consider simple modifications of the random phone call model in these graphs. Our results indicate that, unlike in broadcasting, there is no significant difference between the performance of randomized gossiping in complete graphs and sparse random graphs. Furthermore, our simulations indicate that by tuning the parameters of our algorithms, we can significantly reduce the communication overhead compared to the traditional push-pull approach in the graphs we consider.

### A Polynomial Time Algorithm For The Conjugacy Decision and Search Problems in Free Abelian-by-Infinite Cyclic Groups

Authors: Bren Cavallo, Delaram Kahrobaei
Abstract: In this paper we introduce a polynomial time algorithm that solves both the conjugacy decision and search problems in free abelian-by-infinite cyclic groups where the input is elements in normal form. We do this by adapting the work of Bogopolski, Martino, Maslakova, and Ventura in \cite{bogopolski2006conjugacy} and Bogopolski, Martino, and Ventura in \cite{bogopolski2010orbit}, to free abelian-by-infinite cyclic groups, and in certain cases apply a polynomial time algorithm for the orbit problem over $\Z^n$ by Kannan and Lipton.

### Structural Parameterizations of the Mixed Chinese Postman Problem

Authors: Gregory Gutin, Mark Jones, Magnus Wahlstrom
Abstract: In the Mixed Chinese Postman Problem (MCPP), given a weighted mixed graph $G$ ($G$ may have both edges and arcs), our aim is to find a minimum weight closed walk traversing each edge and arc at least once. The MCPP parameterized by the number of edges in $G$ or the number of arcs in $G$ is fixed-parameter tractable as proved by van Bevern et al. (in press) and Gutin, Jones and Sheng (ESA 2014), respectively. Solving an open question of van Bevern et al. (in press), we show that unexpectedly the MCPP parameterized by the treewidth of $G$ is W[1]-hard. In fact, we prove that even the MCPP parameterized by the pathwidth of $G$ is W[1]-hard.

### On the Hardness of Bribery Variants in Voting with CP-Nets

Authors: Britta Dorn, Dominikus Krüger
Abstract: We continue previous work by Mattei et al. (Mattei, N., Pini, M., Rossi, F., Venable, K.: Bribery in voting with CP-nets. Ann. of Math. and Artif. Intell. pp. 1--26 (2013)) in which they study the computational complexity of bribery schemes when voters have conditional preferences that are modeled by CP-nets. For most of the cases they considered, they could show that the bribery problem is solvable in polynomial time. Some cases remained open---we solve two of them and extend the previous results to the case that voters are weighted. Moreover, we consider negative (weighted) bribery in CP-nets, when the briber is not allowed to pay voters to vote for his preferred candidate.

### Hardness of Peeling with Stashes

Authors: Michael Mitzenmacher, Vikram Nathan
Abstract: The analysis of several algorithms and data structures can be framed as a peeling process on a random hypergraph: vertices with degree less than k and their adjacent edges are removed until no vertices of degree less than k are left. Often the question is whether the remaining hypergraph, the k-core, is empty or not. In some settings, it may be possible to remove either vertices or edges from the hypergraph before peeling, at some cost. For example, in hashing applications where keys correspond to edges and buckets to vertices, one might use an additional side data structure, commonly referred to as a stash, to separately handle some keys in order to avoid collisions. The natural question in such cases is to find the minimum number of edges (or vertices) that need to be stashed in order to realize an empty k-core. We show that both these problems are NP-complete for all $k \geq 2$ on graphs and regular hypergraphs, with the sole exception being that the edge variant of stashing is solvable in polynomial time for $k = 2$ on standard (2-uniform) graphs.

### Fixed-Points of Social Choice: An Axiomatic Approach to Network Communities

Authors: Christian Borgs, Jennifer Chayes, Adrian Marple, Shang-Hua Teng
Abstract: We provide the first social choice theory approach to the question of what constitutes a community in a social network. Inspired by the classic preferences models in social choice theory, we start from an abstract social network framework, called preference networks; these consist of a finite set of members where each member has a total-ranking preference of all members in the set.

Within this framework, we develop two complementary approaches to axiomatically study the formation and structures of communities. (1) We apply social choice theory and define communities indirectly by postulating that they are fixed points of a preference aggregation function obeying certain desirable axioms. (2) We directly postulate desirable axioms for communities without reference to preference aggregation, leading to eight natural community axioms.

These approaches allow us to formulate and analyze community rules. We prove a taxonomy theorem that provides a structural characterization of the family of community rules that satisfies all eight axioms. The structure is actually quite beautiful: these community rules form a bounded lattice under the natural intersection and union operations. Our structural theorem is complemented with a complexity result: while identifying a community by the most selective rule of the lattice is in P, deciding if a subset is a community by the most comprehensive rule of the lattice is coNP-complete. Our studies also shed light on the limitations of defining community rules solely based on preference aggregation: any aggregation function satisfying Arrow's IIA axiom, or based on commonly used aggregation schemes like the Borda count or generalizations thereof, lead to communities which violate at least one of our community axioms. Finally, we give a polynomial-time rule consistent with seven axioms and weakly satisfying the eighth axiom.

### Improved Region-Growing and Combinatorial Algorithms for $k$-Route Cut Problems

Authors: Guru Guruganesh, Laura Sanita, Chaitanya Swamy
Abstract: We study the {\em $k$-route} generalizations of various cut problems, the most general of which is \emph{$k$-route multicut} ($k$-MC) problem, wherein we have $r$ source-sink pairs and the goal is to delete a minimum-cost set of edges to reduce the edge-connectivity of every source-sink pair to below $k$. The $k$-route extensions of multiway cut ($k$-MWC), and the minimum $s$-$t$ cut problem ($k$-$(s,t)$-cut), are similarly defined. We present various approximation and hardness results for these $k$-route cut problems that improve the state-of-the-art for these problems in several cases. (i) For {\em $k$-route multiway cut}, we devise simple, but surprisingly effective, combinatorial algorithms that yield bicriteria approximation guarantees that markedly improve upon the previous-best guarantees. (ii) For {\em $k$-route multicut}, we design algorithms that improve upon the previous-best approximation factors by roughly an $O(\sqrt{\log r})$-factor, when $k=2$, and for general $k$ and unit costs and any fixed violation of the connectivity threshold $k$. The main technical innovation is the definition of a new, powerful \emph{region growing} lemma that allows us to perform region-growing in a recursive fashion even though the LP solution yields a {\em different metric} for each source-sink pair. (iii) We complement these results by showing that the {\em $k$-route $s$-$t$ cut} problem is at least as hard to approximate as the {\em densest-$k$-subgraph} (DkS) problem on uniform hypergraphs.

### Solving Parameterized Problems by Mixing Color Coding-Related Techniques

Authors: Meirav Zehavi
Abstract: We introduce a family of strategies, that we call mixing strategies, for applying color coding-related techniques, developing fast parameterized algorithms. Our strategies combine the following ideas.

* Mixing narrow sieves and representative sets, two independent color coding-related techniques.

* For certain "disjointness conditions", improving the best known computation of representative sets.

* Mixing divide-and-color-based preprocessing with the computation mentioned in the previous item, speeding-up standard representative sets-based algorithms.

* Cutting the universe into small pieces in two special manners, one used in the mix mentioned in the previous item, and the other mixed with a non-standard representative sets-based algorithm to improve its running time.

We demonstrate the usefulness of our strategies by obtaining the following results. We first solve the well-studied k-Internal Out-Branching problem in deterministic time $O^*(5.139^k)$ and randomized time $O^*(3.617^k)$, improving upon the previous best deterministic time $O^*(6.855^k)$ and randomized time $O^*(4^k)$. To this end, we establish a relation between "problematic" out-trees and maximum matching computations in graphs. We then present a unified approach to improve the $O^*$ running times of the previous best deterministic algorithms for the classic k-Path, k-Tree, r-Dimensional k-Matching and Graph Motif problems, including their weighted versions, from $O^*(2.619^k)$, $O^*(2.619^k)$, $O^*(2.619^{(r-1)k})$ and $O^*(2.619^{2k})$ to $O^*(2.597^k)$, $O^*(2.597^k)$, $O^*(2.597^{(r-1)k})$ and $O^*(2.597^{2k})$, respectively. Finally, we solve the Weighted 3-Set k-Packing problem in deterministic time $O^*(8.097^k)$, improving upon the previous best $O^*(12.155^k)$ deterministic time.

### Gowers Norm, Function Limits, and Parameter Estimation

Authors: Yuichi Yoshida
Abstract: Let $\{f_i:\mathbb{F}_p^i \to \{0,1\}\}$ be a sequence of functions, where $p$ is a fixed prime and $\mathbb{F}_p$ is the finite field of order $p$. The limit of the sequence can be syntactically defined using the notion of ultralimit. Inspired by the Gowers norm, we introduce a metric over limits of function sequences, and study properties of it. One application of this metric is that it provides a characterization of affine-invariant parameters of functions that are constant-query estimable. Using this characterization, we provide (alternative) proofs of the constant-query testability of several affine-invariant properties, including low-degree polynomials.

### Decidable Fragments of Logics Based on Team Semantics

Authors: Juha Kontinen, Antti Kuusisto, Jonni Virtema
Abstract: We study the complexity of variants of dependence logic defined by generalized dependency atoms. Let FOC^2 denote two-variable logic with counting, and let ESO(FOC^2) be the extension of FOC^2 with existential second-order prenex quantification. We show that for any finite collection A of atoms that are definable in ESO(FOC^2), the satisfiability problem of the two-variable fragment of FO(A) is NEXPTIME-complete. We also study satisfiability of sentences of FO(A) in the Bernays-Sch\"onfinkel-Ramsey prefix class. Our results show that, analogously to the first-order case, this problem is decidable assuming the atoms in A are uniformly polynomial time computable and closed under substructures. We establish inclusion in 2NEXPTIME. For fixed arity vocabularies, we establish NEXPTIME-completeness.

### Linearizability is EXPSPACE-complete

Abstract: It was shown in Alur et al. [1] that the problem of verifying finite concurrent systems through Linearizability is in EXPSPACE. However, there was still a complexity gap between the easy to obtain PSPACE lower bound and the EXPSPACE upper bound. We show in this paper that Linearizability is EXPSPACE-complete.

### On Succinct Representations of Binary Trees

Authors: Pooya Davoodi, Rajeev Raman, Srinivasa Rao Satti
Abstract: We observe that a standard transformation between \emph{ordinal} trees (arbitrary rooted trees with ordered children) and binary trees leads to interesting succinct binary tree representations. There are four symmetric versions of these transformations. Via these transformations we get four succinct representations of $n$-node binary trees that use $2n + n/(\log n)^{O(1)}$ bits and support (among other operations) navigation, inorder numbering, one of pre- or post-order numbering, subtree size and lowest common ancestor (LCA) queries. The ability to support inorder numbering is crucial for the well-known range-minimum query (RMQ) problem on an array $A$ of $n$ ordered values. While this functionality, and more, is also supported in $O(1)$ time using $2n + o(n)$ bits by Davoodi et al.'s (\emph{Phil. Trans. Royal Soc. A} \textbf{372} (2014)) extension of a representation by Farzan and Munro (\emph{Algorithmica} \textbf{6} (2014)), their \emph{redundancy}, or the $o(n)$ term, is much larger, and their approach may not be suitable for practical implementations.

One of these transformations is related to the Zaks' sequence (S.~Zaks, \emph{Theor. Comput. Sci.} \textbf{10} (1980)) for encoding binary trees, and we thus provide the first succinct binary tree representation based on Zaks' sequence. Another of these transformations is equivalent to Fischer and Heun's (\emph{SIAM J. Comput.} \textbf{40} (2011)) \minheap\ structure for this problem. Yet another variant allows an encoding of the Cartesian tree of $A$ to be constructed from $A$ using only $O(\sqrt{n} \log n)$ bits of working space.

### Settling the Randomized k-sever Conjecture on Some Special Metrics

Authors: Wenbin Chen
Abstract: In this paper, we settle the randomized $k$-sever conjecture for the following metric spaces: line, circle, Hierarchically well-separated tree (HST), if $k=2$ or $n=k+1$ for arbitrary metric spaces. Specially, we show that there are $O(\log k)$-competitive randomized $k$-sever algorithms for above metric spaces. For any general metric space with $n$ points, we show that there is an $O( \log k \log n)$-competitive randomized $k$-sever algorithm.

### Finitely unstable theories and computational complexity

Authors: Tuomo Kauranne
Abstract: The complexity class $NP$ can be logically characterized both through existential second order logic $SO\exists$, as proven by Fagin, and through simulating a Turing machine via the satisfiability problem of propositional logic SAT, as proven by Cook. Both theorems involve encoding a Turing machine by a formula in the corresponding logic and stating that a model of this formula exists if and only if the Turing machine halts, i.e. the formula is satisfiable iff the Turing machine accepts its input. Trakhtenbrot's theorem does the same in first order logic $FO$. Such different orders of encoding are possible because the set of all possible configurations of any Turing machine up to any given finite time instant can be defined by a finite set of propositional variables, or is locally represented by a model of fixed finite size. In the current paper, we first encode such time-limited computations of a deterministic Turing machine (DTM) in first order logic. We then take a closer look at DTMs that solve SAT. When the length of the input string to such a DTM that contains effectively encoded instances of SAT is parameterized by the natural number $M$, we proceed to show that the corresponding $FO$ theory $SAT_M$ has a lower bound on the size of its models that grows almost exponentially with $M$. This lower bound on model size also translates into a lower bound on the deterministic time complexity of SAT.

### A Multilevel Bilinear Programming Algorithm For the Vertex Separator Problem

Authors: William W. Hager, James T. Hungerford, Ilya Safro
Abstract: The Vertex Separator Problem for a graph is to find the smallest collection of vertices whose removal breaks the graph into two disconnected subsets that satisfy specified size constraints. In the paper 10.1016/j.ejor.2014.05.042, the Vertex Separator Problem was formulated as a continuous (non-concave/non-convex) bilinear quadratic program. In this paper, we develop a more general continuous bilinear program which incorporates vertex weights, and which applies to the coarse graphs that are generated in a multilevel compression of the original Vertex Separator Problem. A Mountain Climbing Algorithm is used to find a stationary point of the continuous bilinear quadratic program, while second-order optimality conditions and perturbation techniques are used to escape from either a stationary point or a local maximizer. The algorithms for solving the continuous bilinear program are employed during the solution and refinement phases in a multilevel scheme. Computational results and comparisons demonstrate the advantage of the proposed algorithm.

### Geometric Algorithms for Minimal Enclosing Discs in Strictly Convex Normed Planes

Authors: Thomas Jahn
Abstract: With the geometric background provided by Alonso, Martini, and Spirova, we show the validity of the Elzinga--Hearn algorithm and the Shamos--Hoey algorithm for solving the minimal enclosing disc problem in strictly convex normed planes.

### Statistical Mechanics of the Minimum Dominating Set Problem

Authors: Jin-Hua Zhao, Yusupjan Habibulla, Hai-Jun Zhou
Abstract: The minimum dominating set problem has wide applications in network science and related fields. It consists of assembling a node set of global minimum size such that any node of the network is either in this set or is adjacent to at least one node of this set. Although this is a difficult optimization problem in general, we show it can be exactly solved by a generalized leaf-removal process if the network contains no core. If the network has an extensive core, we estimate the size of minimum dominating sets by a mean-field theory and implement a belief-propagation algorithm to obtain nearly optimal solutions. Our algorithms also perform well on real-world network instances.

### Online bipartite matching in offline time

In 1973 Hopcroft and Karp gave a very nice time algorithm computing a maximum matching in unweighted bipartite graphs. This algorithm turned out to be the milestone that is hard to beat. The bipartite maximum matching problem has been studied in many different flavors such as online, approximate, dynamic, randomized or the combination of the above. The HK algorithm was improved for sufficiently dense and sufficiently sparse graphs. Nevertheless, for the general case, despite of the wide interest, little improvement over HK was obtained. This is somewhat intriguing, as no reasonable example certifies that the bound for the running time of HK is in fact tight. The HK algorithm is of offline nature and relies heavily on receiving the whole graph before processing it. On the quest for making some progress on the subject matter we aimed for the dynamic setting. Say the vertices need to be matched as they show up in the graph, so some re-matching is allowed and the maximum matching needs to be maintained at all times. Can one do better than simply finding any augmenting path each time a new vertex appears?

Let us narrow down the dynamic scenario we consider: say only the vertices of one side of the graph come in online, and at the time they show up they reveal all their adjacent edges. This scenario is easily motivated as follows.
There is a set of servers and a set of jobs to be executed on these servers. Every job comes with a list of servers capable of performing the job. Of course it is reasonable to serve as many jobs as possible, hence the maximum job-server matching is highly desired. Having that motivation in mind, an online scenario seems to be the most natural: jobs come in online one at the time, and request to be matched to one of the chosen servers. We care to match the job whenever its possible, so we allow some busy servers to be reallocated.
Now the question is, what is a good way of reallocating the servers, so that the dynamic algorithm can benefit from it? We adopt the following measure: each reallocation involves some reallocating cost. We want to minimize the cost of reallocating the servers.

We associate with each server an attribute called , which states how many times the server has been reallocated in the entire process. The parameter stands for time. We see the entire process of adding jobs as a sequence of turns, in each turn a new job appears with the list of eligible servers. The attribute describes the number of times was reallocated up to turn . These attributes guide us when we search for augmenting paths. We try to avoid servers with high ranks. This should distribute the necessary reallocations more or less evenly among the servers.

In order to follow this approach, a certain greedy strategy comes to mind. When trying to match a new job, choose the augmenting path which minimizes the maximum rank of a server along this path. This strategy has one substantial disadvantage. If any augmenting path that we can choose to match the new job contains a vertex of high rank , then we are allowed to rematch all servers of ranks at most . That is clearly an overhead. We hence define another attribute, , for every job . This attribute says what is the rank of the lowest ranked path from to any unmatched server. When we try to match job , we search for the alternating path along which the tiers of jobs do not increase. We call such a path a tiered path. In other words, a tiered path minimizes the maximal rank on its every suffix. This seems natural: why to re-enter vertices of high rank when we can avoid them.

It turns out that this simple strategy does quite well: the ranks (and hence also the tiers) do not grow above . That means, that each server gets reallocated at most times. This is already interesting. Moreover, if we knew how to efficiently choose the right augmenting paths, the total work would be . We have an algorithm that finds all the augmenting paths in the total time , what matches the offline time of HK.

So let us first take a look on how the bound on the maximum rank is obtained. First of all, we direct the edges of the graph according to the current matching: the matched edges point from servers to jobs, while the unmatched edges point the other way around. Now, directed paths are alternating, so in each turn we need to find a directed path from the new job to a free server and reverse the edges along the path. We first show that the servers of high ranks are far from the unoccupied servers: the directed distance from any server to an unmatched server in turn is at least .

We now look at any set of vertex disjoint directed paths covering all free servers in turn before applying the augmenting path. Note, that there are no outgoing edges from free servers, so the paths end there. The rank of the directed path present in the graph in turn is the maximum rank of a server on it. Let's call the augmenting path applied in turn . We analyze the augmentation process backwards. In turn , before applying , there exists a set of vertex disjoint paths covering free servers, such that:

• every path has its counterpart , where is an injection
• has rank at least as high as , unless 's rank is smaller or equal to one plus the rank of : then the rank of may be one less then the rank of
• there is a path in that is not in the image of and has rank at least the rank of

This observation may be translated as follows. Let us, for every path in , draw a vertical bar of height equal to its rank. Let us now sort the bars in descending order and put them next to each other, as shown in Figure 1 to the left. These bars are the ranks of the paths in turn . When we take a step back to turn , we have another set of bars corresponding to paths from turn , where one additional bar pops out. Moreover, some bars may have decreased by one, but all the bars that decreased are dominated (with respect to height) by the newly added bar. This is shown in Figure 1 to the right. The process ends when we reach turn , and there is bars of height zero.

Now we move to bounding the maximum rank. The maximum rank, say , will appear on some path in some turn . We take a look at set consisting of this single path. There is only one bar of height . In the previous turn, either there is still a bar of the height , or there are two bars of height . Every time the bars decrease, there comes another bar that dominates the decreased bars. Somewhere on the way back to turn there is a set of bars with the sum of heights quadratic in . The bars, however, correspond to vertex disjoint paths, and the heights of the bars are the lower bounds on the lengths of these paths. Hence, there is vertices in the graph and .

The question that remains is whether we are able to efficiently find these paths. The main problem here is that we need augmenting paths where the tiers of jobs along the path do not increase. This is not a good news: the tiers are difficult to maintain upon the reversal of the edges on the entire augmenting path. The idea is to maintain them in a lazy manner. For each job , instead of its actual tier, the algorithm maintains an attribute . Subscript LB stands for lower bound, as we maintain the invariant that . When a new vertex turns up in some turn, is set to . The algorithm repeatedly tries to find (in the directed graph) a tiered (according to the maintained lower bounds for tiers) directed path from to a free server. It executes a search routine from , traversing only the vertices with ranks and 's bounded by . Once a job with is discovered, the upper bound on the ranks and 's of vertices visited next is recursively set to . This goes on until one of the two things happen. It might be that a free server is discovered. Then we found an augmenting path, along which the 's of the vertices are their actual tiers (the path that we found is a witness for that). We reverse the edges along the augmenting path and increase the ranks of the reallocated servers. It might also happen that the search fails. This means, that the algorithm detects a group of vertices whose 's are lower than their actual tiers. The algorithm then rightfully increases the 's associated with these vertices. It continues the search from the point where it failed. The difference is that now it can search further, as it is allowed to visit vertices with higher 's than before. The general idea is that whenever a vertex is visited by the algorithm, either its or its rank is increased. Unfortunately upon every such visit the algorithm may touch all the edges adjacent to the visited vertex. These edges, however, will be touched in total times each. The total time amounts to .

by Anna Zych at October 19, 2014 02:09 PM UTC

### Making academic contacts (some thoughts for new researchers)

Say you've never written a paper, and may not yet have the time or readiness to solve major problems on your own; but you want to have real scientific conversations and perhaps even collaboration with a busy researcher you admire.  What could you possibly talk about?  What can you offer them?   Below is my advice.

***

1)  In my view, the best approach to making contacts is closely related to how I'd recommend spending your own study time as a beginning researcher:  (a) start reading research papers as soon as possible, and (b) try diligently to ask interesting follow-up questions to the papers you like.

Asking questions is a central research skill.  It is one you can start learning early on because, even in technically difficult fields, simple patterns of questioning often recur in many forms across papers.  E.g., in the theory of computing, if there is a new model of computation being studied, it is likely to have randomized or nondeterministic versions that can be studied next.  Or if there is an algorithmic problem, it might have variant problems to be solved in, say, the communication protocol or decision-tree models.  And so on.

Even though it is not so difficult to produce these variations, few people do so systematically.  If you keep at it, and keep trying to learn and adopt more patterns of questioning, you will hit upon interesting and solvable problems.  You will also start to develop a taste about which problems are likely to be most interesting, which are too hard, and so on.  (Side note---I believe that keeping a research journal with your questions greatly helps this process.)

2)  Now returning to the goal of making contacts, I think that one of the best kind of emails you can send is one that contains a good research question, that's reasonably related to the person's research area.  If you can do this and pique their interest, they may well enter into a dialogue that could become a full-fledged collaboration---regardless of your credentials on paper.  After all, you've already brought something important to the table.

So you don't have to worry about choosing the exact right question to represent yourself, as long as it is good and leads to discussion.  In this respect it's less stressful than trying to introduce yourself by defining your whole research outlook.  And it's certainly more promising than suggesting a collaboration based on your GPA or work experience.

Of course, asking good questions isn't easy and takes work. You should think carefully about them before sending, try your best to answer them yourself, and see if there are initial observations or partial solutions you can provide with your question to show you're serious.   Maybe in the end it will be a question they can answer right away; but again, it could still lead to other questions.  There is little risk in trying and it is likely to at least be a useful exercise.

by Andy D (noreply@blogger.com) at October 18, 2014 08:19 PM UTC

### TR14-131 | A game characterisation of tree-like Q-Resolution size | Leroy Chew, Karteek Sreenivasaiah, Olaf Beyersdorff

from ECCC papers

We provide a characterisation for the size of proofs in tree-like Q-Resolution by a Prover-Delayer game, which is inspired by a similar characterisation for the proof size in classical tree-like Resolution. This gives the first successful transfer of one of the lower bound techniques for classical proof systems to QBF proof systems. We apply our technique to show the hardness of two classes of formulas for tree-like Q-Resolution. In particular, we give a proof of the hardness of the formulas of Kleine Buning et al. for tree-like Q-Resolution.

### A New Provable Factoring Algorithm

from Richard Lipton

Factoring, factoring, the whole day through, keeps on my mind—apologies to Hoagy Carmichael and Stuart Gorrell

 Waterloo Mathematics source

Michael Rubinstein is an expert on number theory, who is on the faculty of the University of Waterloo. He is one of the organizers of a 61${^{st}}$-birthday symposium being held December 15–19 in Princeton for my friend and former colleague, Peter Sarnak. I guess it is a matter of taste for a number theorist whether to observe a birthday with a lot of factors (60) or a prime (59 or 61). Rubinstein also does extensive experimental mathematics and lists several code libraries below his publications on his website, which also has interesting articles on the math, history, and practice of musical tuning.

Today Ken and I wish to discuss a paper of his on one of my favorite problems: integer factoring.

The paper appears in the 2013 volume of the electronic journal INTEGERS, one of whose sponsors is the University of West Georgia. It is titled, “The distribution of solutions to ${xy = N \pmod{a}}$ with an application to factoring integers.” He studies the structure of solutions to ${xy = N}$ (mod a), and uses this to prove the following result:

Theorem 1 For any ${\epsilon>0}$, there is a deterministic factoring algorithm that runs in ${O(N^{1/3+\epsilon})}$ time.

The “${+ \epsilon}$” hides sub-linear terms including ${\exp(O(\frac{\ln n}{\ln\ln n}))}$ coming from the divisor bound, logarithmic terms from the overhead in nearly-linear time integer multiplication, and related sources.

## The Factoring Divide

Factoring algorithms partition into two types: unprovable and provable. The unprovable algorithm usually use randomness and/or rely for their correctness on unproved hypotheses, yet are observed to be the fastest in practice for numbers of substantial size. The provable algorithms are usually deterministic, but their key feature is that their correctness is unconditional.

For those trying to factor numbers, to break codes for example, they use the fastest unprovable algorithms such as the general number field sieve (GNFS). The cool part of factoring is that one can always check the result of any algorithm quickly, so anytime an unprovable algorithm fails, it fails in a visible manner.

Why care then about slower algorithms that are provable? Indeed. The answer is that we would like to know the best provable algorithm for every problem, and that includes factoring. We are also interested in these algorithms because they often use clever tricks that might be useable elsewhere in computational number theory. But for factoring there is a special reason that is sometimes hidden by the notation. The GNFS has postulated runtime

$\displaystyle L_N[1/3,c] = \exp((c + o(1))(\ln N)^{1/3}(\ln\ln N)^{2/3})$

where ${c = \sqrt{64/9}{3} < 2}$. This is not a similar order to ${N^{1/3}}$. To see this more clearly, let ${n}$ be the length of ${N}$ in binary, so ${N \approx 2^n}$. Then the GNFS is roughly and slightly above ${2^{n^{1/3}}}$, but ${N^{1/3}}$ is ${2^{\frac{1}{3}n}}$, which is not only miles bigger, it is a properly exponential function.

Nobody knows a deterministic factoring algorithm that beats properly exponential time.

The unprovable algorithms taunt and tease us, because they hold out the promise of being able to beat exponential time, but nobody knows how to prove it. Indeed, as Rubinstein remarks in his intro, each “teaser” is a conceptual child of one of the exponential algorithms. A reason to care about his new algorithm is its potential to be a new way to attack factoring, even though it currently loses to the best known provable methods. These are all slight variations of the Pollard-Strassen method, all running in ${O(N^{1/4+\epsilon})}$-type times; there are also ${O(N^{1/5+\epsilon})}$ algorithms assuming the generalized Riemann hypothesis. See this for details.

## The New Factoring Algorithm

Most factoring algorithms—even Peter Shor’s quantum algorithm—use the idea of choosing a number ${a \ll N}$ and working modulo ${a}$. If ${a}$ and ${N}$ share a factor then we can quickly find it by Euclid’s gcd algorithm, while otherwise the problem of finding ${x,y < a}$ such that ${xy \equiv N \pmod{a}}$ provides useful information. The starting point of Rubinstein’s algorithm is to do this for values ${a}$ that are right near each other, and compare the values obtained.

In its outermost structure, it uses this fact: Suppose ${N = pq}$ where ${p}$ and ${q}$ are primes of the same length, so ${p < q < 2p}$. Suppose ${a \approx N^{1/3}}$. Then if we write

$\displaystyle \begin{array}{rcl} p &=& u_1 a + u_0\\ q &=& v_1 a + v_0, \end{array}$

with ${u_0,v_0 < a}$ (note they are relatively prime to ${a}$ or else gcd gives us a factor) we get that ${u_1}$ and ${v_1}$ are fairly small, about ${N^{1/6}}$. They are also roughly bounded by ${p^{1/3}}$ and by ${a^{1/2}}$. Multiples of them will stay small. So now let us work modulo ${a - \delta}$ for ${\delta = 1,2,3\dots}$. We have:

$\displaystyle \begin{array}{rcl} p &=& u_1 a + u_0 = u_1(a - \delta) + (u_0 + \delta u_1)\\ q &=& v_1 a + v_0 = v_1(a - \delta) + (v_0 + \delta v_1), \end{array}$

so

$\displaystyle N \equiv (u_0 + \delta u_1)(v_0 + \delta v_1) \pmod{a - \delta}.$

Now an issue is that the values ${x_{\delta},y_{\delta}}$ giving ${x_{\delta}y_{\delta} \equiv N \pmod{a - \delta}}$ are far from unique. However, among them as ${\delta = 0,1,2,3\dots}$ will be the collinear points

$\displaystyle (u_0,v_0),\;(u_0 + u_1, v_0 + v_1),\;(u_0 + 2u_1,v_0 + 2v_1),\; (u_0 + 3u_1,v_0 + 3v_1).$

The increments ${u_1,v_1}$ are small enough that the points stay close to each other in Euclidean space. If we divide the space into boxes of the right size and offset, they will all stay inside one box. If we can search a box well enough to find them and get all of ${u_0,u_1,v_0,v_1}$ exactly, then we get ${p}$ and ${q}$. Moreover—and this is why I like factoring—once we find them we can verify that we have the right ones; if the check fails and we were fooled by ${\delta}$-many other points we can move on.

Using ${u_1,v_1 < a^{1/2}}$, Rubinstein is able to show that the amortized number of “foolers” in a ${a^{1/2} \times a^{1/2}}$ square is ${O(1)}$. Since there are ${O(a)}$-many such squares and ${a \approx N^{1/3}}$, we get the target runtime. Note this is amortized, not just expected, so the algorithm is deterministic. The most clever and painstaking aspect is that estimates of the asymptotic convergence of solutions of ${xy \equiv N \pmod{a}}$ to uniform distribution on ${[a] \times [a]}$ are needed to get the “amortized” part. The details become complicated, but Rubinstein writes in an engaging top-down manner, and he includes a section on how this might—might—be used to break the sub-exponential barrier.

## A Related Question

I found this work interesting not just because it is a new approach to factoring. I have tried in the past to prove the following type of result: Is there an asymmetric cryptosystem that is breakable if and only if factoring can be done in polynomial time?

I want to replace systems like AES with ones that uses the hardness of factoring for their security. Systems like AES rely on intuition and experimental testing for their security—there is not even a conditional proof that they are secure.

My goal is really trivial. Any public-key system can be viewed as an asymmetric system. But what I want is that the encryption and decryption should be very fast. This is one of the reasons that modern systems use private-key systems to create symmetric keys: performance. Using public-key systems for all messages is too slow.

My idea is not far in spirit from what Rubinstein does in his factoring algorithm. This is what struck me when I first read his paper. His algorithm is slow because it has no idea which “box” to look at. Can we share some secret that would allow ${N}$ to be factored faster, yet still make it hard for those without the secret?

## Open Problems

Can we extend Rubinstein’s algorithm to break the ${N^{1/4}}$ barrier? Can his methods be used as described above to create asymmetric systems that are based on factoring? What is the real cost of factoring?

### FOCS 2014 is starting

Hope everyone has a great FOCS! In the previous post we mentioned the two workshops on different aspects of the Fourier transforms occurring today. I also wanted to mention the Tutorial on obfuscation today with talks by  Amit Sahai, Allison Lewko and Dan Boneh. The new constructions of obfuscation and their applications form one of the most exciting and rapidly developing research topics in cryptography (and all of theoretical CS) today, and this would be a great opportunity for non-specialists to catch up on some of these advances.

by Boaz Barak at October 18, 2014 11:47 AM UTC

### TR14-130 | Algebraic Geometric Techniques for Depth-4 PIT &amp; Sylvester-Gallai Conjectures for Varieties | Ankit Gupta

from ECCC papers

We present an algebraic-geometric approach for devising a deterministic polynomial time blackbox identity testing (PIT) algorithm for depth-4 circuits with bounded top fanin. Using our approach, we devise such an algorithm for the case when such circuits have bounded bottom fanin and satisfy a certain non-degeneracy condition. In particular, we present an algorithm that, given blackboxes to $P_1\cdots P_d$, $Q_{11}\cdots Q_{1d_1}$, $\ldots$ , $Q_{k1}\cdots Q_{kd_k}$ where $k$ and the degrees of $P_i$'s and $Q_{ij}$'s are bounded, determines the membership of $P_1\cdots P_d$ in the radical of the ideal generated by $Q_{11}\cdots Q_{1d_1}$, $\ldots$ , $Q_{k1}\cdots Q_{kd_k}$ in deterministic poly($n,d,\max_i(d_i)$)-time. We also give a Dvir-Shpilka (STOC 2005)-like approach to resolve the degenerate case and, in the process, initiate a new direction in $\textit{incidence geometry for non-linear varieties}$. This approach consists of a series of Sylvester-Gallai type conjectures for bounded-degree varieties and, if true, imply a complete derandomization in the bounded bottom fanin case. To the best of our knowledge, these problems have not been posed before.

### Sunshine In = Earthshine Out

from bit-player

No computer simulations have ever had broader consequences for human life than the current generation of climate models. The models tell us that rising levels of atmospheric carbon dioxide and other greenhouse gases can trigger abrupt shifts in the planet’s climate; to avert those changes or mitigate their effects, the entire human population is urged to make fundamental economic and technological adjustments. In particular, we may have to forgo exploiting most of the world’s remaining reserves of fossil fuels. It’s not every day that the output of a computer program leads to a call for seven billion people to change their behavior.

Thus sayeth I in my latest American Scientist column (HTML, PDF). Climate is a subject I take up with a certain foreboding. The public “debate” over global warming has become so shrill and dysfunctional that I can barely force myself to pay attention, much less join the fray. As I worked on writing the column, I found myself tiptoeing through the polemical minefield, carefully avoiding any phrase that might be picked up by “the other side” and used against me. (“Even a writer for American Scientist has doubts about . . .”). When I handed in the text, my editors went over it with the same cautious anxiety—and they found a few places where they thought I hadn’t been careful enough.

This is not the kind of science I enjoy. I would much prefer to dwell in less-contentious corners of the cosmos, where I can play with my sticky spheres or my crinkly curves, and never give a thought to “the other side.” But now and then one must return to the home planet. Besides, the computer modeling that plays a major role in climate science is just my kind of thing.

So, for the past few months climate models have been my breakfast, lunch, and dinner, and my bedtime snack. I’ve been reading in the literature, and poring over source code; I’ve managed to get a couple of serious models running on a laptop. The American Scientist column says more about the rewards and frustrations of all these undertakings. Here I want to talk about a lighter side of the project: a little climate model of my own. The image below is just a static screen grab, but you can go play with the real thing if you’d like.

Okay, it’s not really all my own. The physics behind the model was explored more than 100 years ago by Svante Arrhenius. The first computer implementations were done by M. I. Budyko and William Sellers in 1969, and a third version was published by Stephen Schneider and Tevi Gal-Chen in 1973. But the JavaScript is mine. (Any mistakes are mine, too.)

The model is a simple one. The planet it describes is not the Earth we know and love but a bald sphere without continents or oceans, seasons or storms, or even day and night. Temperature is the only climatic variable. The globe is divided into latitudinal stripes five degrees wide, and temperatures are always uniform throughout a stripe. Other than warming and cooling, the only thing that can happen on this planet is freezing: If the temperature in a stripe falls below –10 degrees Celsius, it grows an ice sheet.

Why pay any attention to such a primitive model? Although a zillion details are missing, some important physical principles emerge with particular clarity. At the heart of the model is the concept of energy balance: If the Earth is to remain in thermal equilibrium with its surroundings, then it must radiate away as much energy as it receives from the Sun. The planet’s temperature will rise or fall in order to maintain this balance. The governing equation is:

$Q (1 - \alpha) = \sigma T^{4}.$

Here $Q$ is the average intensity of incoming solar radiation in watts per square meter, $\alpha$ is the albedo, or reflectivity, and $T$ is temperature in Kelvins; $\sigma$ is the Stefan-Boltzmann constant, which relates thermal emission to temperature. The numerical value of $\sigma$ is $5.67 \times 10^{-8} \mathrm{W m^{-2} K^{-4}}$. In other words, sunshine in = earthshine out.

If we know the solar input, we can calculate the Earth’s temperature at equilibrium by solving for $T$:

$T = \sqrt[4]{\frac{Q (1 – \alpha)}{\sigma}}$

This is exactly what the energy-balance model does.

Two more effects need to be taken into account. First, most of the sun’s energy is received in the tropics, but it doesn’t all stay there. On the Earth, heat is redistributed by the process we call weather—evaporation and condensation, winds, storms, etc.—and also by ocean currents. In the model, the effect of all that swirly fluid dynamics is crudely approximated by a diffusive flow that simply smooths out temperature gradients.

Finally, there’s the greenhouse effect. Solar radiation at visible wavelengths passes through the Earth’s atmosphere to warm the surface, but the Earth emits at longer wavelengths, in the infrared; radiation in that part of the spectrum is absorbed by water vapor, carbon dioxide, and other minor constituents of the atmosphere. The blocked infrared emission raises the temperature at the surface by 30 degrees Celsius or more. The Earth would be a very chilly place without this effect, but the burning issue of the moment is how to avoid overheating. The model sidesteps all the complexities of atmospheric chemistry and absorption spectra; a single parameter, H, simply determines the fraction of outgoing radiation trapped by greenhouse gases.

The interface to the model has four controls—sliders that adjust the incident solar flux, the albedo of land, the albedo of ice-covered regions, and the greenhouse parameter. While playing with the slider settings, it’s not hard to get the model into a state from which there is no easy recovery. That’s what the reset button is for. (Too bad the real planet doesn’t have one.)

Some experiments you might try:

• The default greenhouse setting is H = 0.4, meaning that 40 percent of the outgoing radiation is intercepted. Lower the slider to below 0.2. The model enters a “snowball Earth” state, where ice sheets descend all the way to the Equator. Now return the greenhouse slider to the default setting of 0.4. The ice persists, and it will not melt away until the control is moved to a still higher setting. When the thaw does come, it is sudden and overshoots, leaving the planet in a much warmer state.
• Raise the greenhouse slider to about 0.45, where the polar ice cap disappears. Returning the slider to 0.4 does not restore the ice cap, and the polar areas remain several degrees warmer than they were before the greenhouse excursion.
• Raising the land albedo (so that more sunlight is reflected from snowfree surfaces, and less is absorbed) reveals another “ratchet” mechanism. Once the planet becomes totally icebound, further changes in the land albedo have no effect at all. The reason is simply that no ice-free land is exposed.
• Push the greenhouse slider toward the top of the scale. Beyond H = 0.75, tropical temperatures approach the boiling point of water, and the planet has obviously become uninhabitable. Question: What will happen at H = 1.0, where no radiation at all can escape the atmosphere?

Some of the extreme parameter values mentioned above yield fanciful results that would never be seen on the Earth. But certain interesting aspects of the model seem quite plausible. I am particularly intrigued by the presence of abrupt changes of state that look much like phase transitions. If we consider just the value of the greenhouse parameter H and the average global temperature T, we can draw a two-dimensional phase diagram in the (H, T) plane. The plot below traces the system’s trajectory as H is lowered from 0.4 to 0.2, then raised to 0.5, and finally returned to the initial setting of 0.4.

That four-sided loop is the hallmark of hysteresis (a term first introduced in the study of magnetic materials). Initially, as the greenhouse effect weakens, temperature falls off linearly. Then, at about H = 0.3, the curve steepens. (The stairsteps represent the freezing of successive zones of latitude.) Just below H = 0.218, the temperature falls off a cliff, dropping suddenly by 20 degrees Celsius. On the next segment of the curve, as H increases again, the temperature again responds linearly, but in a much colder regime. Only when H reaches 0.459 is warmth restored to the world, and this time there’s an abrupt upward jump of almost 35 degrees.

It’s no mystery what’s causing this behavior. There’s a strong feedback effect between cooling/freezing and warming/thawing. When the temperature in a latitude band falls below the –10 degree threshold, the zone ices over; the ice-covered surface is more reflective, and so less heat is absorbed, cooling the planet still more. Going in the other direction, when the ice melts, the exposed land absorbs more heat and brings still more warming.

The sharp, discontinuous transitions in the graph above could not happen on the real planet. They are possible in the model because it has no notion of heat capacity or latent heat; after every perturbation, the system instantly snaps back to equilibrium. But if the hysteresis loop in the model has unrealistically sharp corners, its basic shape is not impossible on a physical planet. What’s most important about the loop is that over a wide range of greenhouse parameters, the system has two stable states. At H = 0.4, for example, the world can have an average temperature of either 14 degrees of –22 degrees. That kind of bistability may well be possible in terrestrial climate.

Snowball Earth is not a fate we need to worry about anytime soon, but there is evidence that the planet actually went through such frozen states early in its history. The runaway greenhouse effect that would boil away the oceans is also not an immediate threat. So can we rest easy about living on a sedate, linear segment of the H-T curve? That’s a question that climate models are supposed to answer, but it’s beyond the scope of this particular model.

by Brian Hayes at October 17, 2014 12:35 PM UTC

### First CFP for ICALP 2015

from Luca Aceto

The first call for papers for ICALP 2015, which will be held in Kyoto in the period 6-10 July 2015, is available here.

I hope that you will consider submitting your best work to the conference. The event will be rich of scientific events and will be co-located with LICS 2015. To whet your appetite, here is the list of invited speakers and invited tutorials:

Invited Speakers

Ken Kawarabayashi, NII, Japan
Valerie King, University of Victoria, Canada
Thomas Moscibroda, MSR Asia, China
Anca Muscholl, University of Bordeaux, France (Joint with LICS)
Peter O'Hearn, Facebook, UK (Joint with LICS)

Invited Tutorial Speakers (Joint with LICS)

Piotr Indyk, MIT, USA
Andrew Pitts, University of Cambridge, UK
Geoffrey Smith, Florida International University, USA

Masterclass speaker

Ryuhei Uehara, JAIST, Japan

by Luca Aceto (noreply@blogger.com) at October 17, 2014 10:37 AM UTC

### TR14-129 | Leakage-resilient non-malleable codes | Divesh Aggarwal, Stefan Dziembowski, Tomasz Kazana , Maciej Obremski

from ECCC papers

A recent trend in cryptography is to construct cryptosystems that are secure against physical attacks. Such attacks are usually divided into two classes: the \emph{leakage} attacks in which the adversary obtains some information about the internal state of the machine, and the \emph{tampering} attacks where the adversary can modify this state. One of the popular tools used to provide tamper-resistance are the \emph{non-malleable codes} introduced by Dziembowski, Pietrzak and Wichs (ICS 2010). These codes can be defined in several variants, but arguably the most natural of them are the information-theoretically secure codes in the \emph{$k$-split-state model} (the most desired case being $k=2$). Such codes were constucted recently by Aggarwal et al.~(STOC 2014). Unfortunately, unlike the earlier, computationally-secure constructions (Liu and Lysyanskaya, CRYPTO 2012) these codes are not known to be resilient to leakage. This is unsatisfactory, since in practice one always aims at providing resilience against \emph{both} leakage and tampering (especially considering tampering without leakage is problematic, since the leakage attacks are usually much easier to perform than the tampering attacks). In this paper we close this gap by showing a non-malleable code in the $2$-split state model that is secure against leaking almost a $1/12$-th fraction of the bits from the codeword (in the bounded-leakage model). This is achieved via a generic transformation that takes as input any non-malleable code $(\Enc,\Dec)$ in the $2$-split state model, and constructs out of it another non-malleable code $(\Enc',\Dec')$ in the $2$-split state model that is additionally leakage-resilient. The rate of $(\Enc',\Dec')$ is linear in the rate of $(\Enc,\Dec)$. Our construction requires that $\Dec$ is \emph{symmetric}, i.e., for all $x, y$, it is the case that $\Dec(x,y) = \Dec(y,x)$, but this property holds for all currently known information-theoretically secure codes in the $2$-split state model. In particular, we can apply our transformation to the code of Aggarwal et al., obtaining the first leakage-resilient code secure in the split-state model. Our transformation can be applied to other codes (in particular it can also be applied to a recent code of Aggarwal, Dodis, Kazana and Obremski constructed in the work subsequent to this one).

### TR14-128 | Non-malleable Reductions and Applications | Divesh Aggarwal, Yevgeniy Dodis, Tomasz Kazana , Maciej Obremski

from ECCC papers

Non-malleable codes, introduced by Dziembowski, Pietrzak and Wichs~\cite{DPW10}, provide a useful message integrity guarantee in situations where traditional error-correction (and even error-detection) is impossible; for example, when the attacker can completely overwrite the encoded message. Informally, a code is non-malleable if the message contained in a modified codeword is either the original message, or a completely unrelated value''. Although such codes do not exist if the family of tampering functions'' $\cF$ allowed to modify the original codeword is completely unrestricted, they are known to exist for many broad tampering families $\cF$. The family which received the most attention~\cite{DPW10,LL12,DKO13,ADL14,CG14a,CG14b} is the family of tampering functions in the so called {\em split-state} model: here the message $x$ is encoded into two shares $L$ and $R$, %of length $N$ each, and the attacker is allowed to {\em arbitrarily} tamper with each $L$ and $R$ {\em individually}. % Despite this attention, the following problem remained open: \begin{center} {\em Build efficient, information-theoretically secure non-malleable codes in the split-state model with constant encoding rate}: $|L|=|R|=O(|x|)$. \end{center} In this work, we resolve this open problem. Our technique for getting our main result is of independent interest. We \begin{itemize} \item[(a)] develop a generalization of non-malleable codes, called {\em non-malleable reductions}; \item[(b)] show simple composition theorem for non-malleable reductions; \item[(c)] build a variety of such reductions connecting various (independently interesting) tampering families $\cF$ to each other; and \item[(d)] construct our final, constant-rate, non-malleable code in the split-state model by applying the composition theorem to a series of easy to understand reductions. \end{itemize}

### Weighted sampling of outer products

Authors: Daniel Hsu
Abstract: This note gives a simple analysis of the randomized approximation scheme for matrix multiplication of Drineas et al (2006) with a particular sampling distribution over outer products. The result follows from a matrix version of Bernstein's inequality. To approximate the matrix product $AB^\top$ to spectral norm error $\varepsilon\|A\|\|B\|$, it suffices to sample on the order of $(\mathrm{sr}(A) \vee \mathrm{sr}(B)) \log(\mathrm{sr}(A) \wedge \mathrm{sr}(B)) / \varepsilon^2$ outer products, where $\mathrm{sr}(M)$ is the stable rank of a matrix $M$.

### An Efficient Algorithm for Unweighted Spectral Graph Sparsification

Authors: David G. Anderson, Ming Gu, Christopher Melgaard
Abstract: Spectral graph sparsification has emerged as a useful tool in the analysis of large-scale networks by reducing the overall number of edges, while maintaining a comparable graph Laplacian matrix. In this paper, we present an efficient algorithm for the construction of a new type of spectral sparsifier, the unweighted spectral sparsifier. Given a general unweighted graph $G = \left( V, E \right)$ and an integer $\ell < |E|$ (the number of edges in $E$), we compute an unweighted graph $H = \left( V, F \right)$ with $F \subset E$ and $|F| = \ell$ such that for every $x \in \mathbb{R}^{V}$ ${\displaystyle \frac{x^T L_G x}{\kappa} \leq x^T L_H x \leq x^T L_G x,}$ where $L_G$ and $L_H$ are the Laplacian matrices for $G$ and $H$, respectively, and $\kappa \geq 1$ is a slowly-varying function of $|V|, |E|$ and $\ell$. This work addresses an open question of the existence of unweighted graph sparsifiers for unweighted graphs. Additionally, our algorithm can efficiently compute unweighted graph sparsifiers for weighted graphs, leading to sparsified graphs that retain the weights of the original graphs.

### Consistent Weighted Sampling Made Fast, Small, and Easy

Authors: Bernhard Haeupler, Mark Manasse, Kunal Talwar
Abstract: Document sketching using Jaccard similarity has been a workable effective technique in reducing near-duplicates in Web page and image search results, and has also proven useful in file system synchronization, compression and learning applications.

Min-wise sampling can be used to derive an unbiased estimator for Jaccard similarity and taking a few hundred independent consistent samples leads to compact sketches which provide good estimates of pairwise-similarity. Subsequent works extended this technique to weighted sets and show how to produce samples with only a constant number of hash evaluations for any element, independent of its weight. Another improvement by Li et al. shows how to speedup sketch computations by computing many (near-)independent samples in one shot. Unfortunately this latter improvement works only for the unweighted case.

In this paper we give a simple, fast and accurate procedure which reduces weighted sets to unweighted sets with small impact on the Jaccard similarity. This leads to compact sketches consisting of many (near-)independent weighted samples which can be computed with just a small constant number of hash function evaluations per weighted element. The size of the produced unweighted set is furthermore a tunable parameter which enables us to run the unweighted scheme of Li et al. in the regime where it is most efficient. Even when the sets involved are unweighted, our approach gives a simple solution to the densification problem that other works attempted to address.

Unlike previously known schemes, ours does not result in an unbiased estimator. However, we prove that the bias introduced by our reduction is negligible and that the standard deviation is comparable to the unweighted case. We also empirically evaluate our scheme and show that it gives significant gains in computational efficiency, without any measurable loss in accuracy.

### LP/SDP Hierarchy Lower Bounds for Decoding Random LDPC Codes

Abstract: Random (dv,dc)-regular LDPC codes are well-known to achieve the Shannon capacity of the binary symmetric channel (for sufficiently large dv and dc) under exponential time decoding. However, polynomial time algorithms are only known to correct a much smaller fraction of errors. One of the most powerful polynomial-time algorithms with a formal analysis is the LP decoding algorithm of Feldman et al. which is known to correct an Omega(1/dc) fraction of errors. In this work, we show that fairly powerful extensions of LP decoding, based on the Sherali-Adams and Lasserre hierarchies, fail to correct much more errors than the basic LP-decoder. In particular, we show that:

1) For any values of dv and dc, a linear number of rounds of the Sherali-Adams LP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv,dc)-regular LDPC code.

2) For any value of dv and infinitely many values of dc, a linear number of rounds of the Lasserre SDP hierarchy cannot correct more than an O(1/dc) fraction of errors on a random (dv,dc)-regular LDPC code.

Our proofs use a new stretching and collapsing technique that allows us to leverage recent progress in the study of the limitations of LP/SDP hierarchies for Maximum Constraint Satisfaction Problems (Max-CSPs). The problem then reduces to the construction of special balanced pairwise independent distributions for Sherali-Adams and special cosets of balanced pairwise independent subgroups for Lasserre.

Some of our techniques are more generally applicable to a large class of Boolean CSPs called Min-Ones. In particular, for k-Hypergraph Vertex Cover, we obtain an improved integrality gap of $k-1-\epsilon$ that holds after a \emph{linear} number of rounds of the Lasserre hierarchy, for any k = q+1 with q an arbitrary prime power. The best previous gap for a linear number of rounds was equal to $2-\epsilon$ and due to Schoenebeck.

### Online Network Design Algorithms via Hierarchical Decompositions

Authors: Seeun Umboh
Abstract: We develop a new approach for online network design and obtain improved competitive ratios for several problems. Our approach gives natural deterministic algorithms and simple analyses. At the heart of our work is a novel application of embeddings into hierarchically well-separated trees (HSTs) to the analysis of online network design algorithms --- we charge the cost of the algorithm to the cost of the optimal solution on any HST embedding of the terminals. This analysis technique is widely applicable to many problems and gives a unified framework for online network design.

In a sense, our work brings together two of the main approaches to online network design. The first uses greedy-like algorithms and analyzes them using dual-fitting. The second uses tree embeddings and results in randomized $O(\log n)$-competitive algorithms, where $n$ is the total number of vertices in the graph. Our approach uses deterministic greedy-like algorithms but analyzes them via HST embeddings of the terminals. Our proofs are simpler as we do not need to carefully construct dual solutions and we get $O(\log k)$ competitive ratios, where $k$ is the number of terminals.

In this paper, we apply our approach to obtain deterministic $O(\log k)$-competitive online algorithms for the following problems.

- Steiner network with edge duplication. Previously, only a randomized $O(\log n)$-competitive algorithm was known.

- Rent-or-buy. Previously, only deterministic $O(\log^2 k)$-competitive and randomized $O(\log k)$-competitive algorithms by Awerbuch, Azar and Bartal (2004) were known.

- Connected facility location. Previously, only a randomized $O(\log^2 k)$-competitive algorithm by San Felice, Williamson and Lee (2014) was known.

- Prize-collecting Steiner forest. We match the competitive ratio first achieved by Qian and Williamson (2011) and give a simpler analysis.

### Models for the k-metric dimension

Abstract: For an undirected graph G=(V,E), a vertex x \in V separates vertices u and v (where u,v \in V, u \neq v) if their distances to x are not equal. Given an integer parameter k \geq 1, a set of vertices L \subseteq V is a feasible solution if for every pair of distinct vertices, u,v, there are at least k distinct vertices x_1,x_2,...,x_k \in L each separating u and v. Such a feasible solution is called a "landmark set", and the k-metric dimension of a graph is the minimal cardinality of a landmark set for the parameter k. The case k=1 is a classic problem, where in its weighted version, each vertex v has a non-negative weight, and the goal is to find a landmark set with minimal total weight. We generalize the problem for k \geq 2, introducing two models, and we seek for solutions to both the weighted version and the unweighted version of this more general problem. In the model of all-pairs (AP), k separations are needed for every pair of distinct vertices of V, while in the non-landmarks model (NL), such separations are required only for pairs of distinct vertices in V \setminus L.

We study the weighted and unweighted versions for both models (AP and NL), for path graphs, complete graphs, complete bipartite graphs, and complete wheel graphs, for all values of k \geq 2. We present algorithms for these cases, thus demonstrating the difference between the two new models, and the differences between the cases k=1 and k \geq 2.

### Optimal proof systems — a survey (slides by Olaf Beyersdorff)

Olaf Beyersdorff surveys Optimal Proof Systems in the attached slides presented at the October 12-17, 2014 Dagstuhl Seminar on Optimal algorithms and proofs.

by huntermonroe at October 16, 2014 07:28 PM UTC

### On Some Conjectures in Proof Complexity (slides by Pavel Pudlák)

Pavel Pudlák surveys open problems in Proof Complexity in the attached slides presented at the October 12-17, 2014 Dagstuhl Seminar on Optimal algorithms and proofs.

by huntermonroe at October 16, 2014 07:22 PM UTC