# Theory of Computing Blog Aggregator

at November 27, 2014 07:33 PM UTC

at November 27, 2014 06:30 PM UTC

at November 27, 2014 12:25 PM UTC

at November 27, 2014 08:32 AM UTC

at November 27, 2014 08:17 AM UTC

Ok, but if you're so concerned about bandwidth then maybe you should use a more clever routing scheme that spreads your messages across multiple paths to get even more bandwidth. This can be modeled as a network flow, and the bottleneck to getting the most bandwidth is no longer a single edge. Instead, the max-flow min-cut theorem tells you that the bottleneck takes the form of a cut: a partition of the graphs into two disjoint subsets, whose bandwidth is the sum of the bandwidths of the edges crossing the cut.

Despite all this added complexity, it turns out that the bandwidth in this sort of multi-path routing scheme can still be described by a single tree. That is, there's a tree whose vertices are the vertices of your graph (but whose edges and edge weights are no longer those of the graph) such that the bandwidth you can get from one vertex to another by routing data along multiple paths in the graph is the same as the bandwidth of the single path between the same two vertices in the tree. More, the edges of the tree can be labeled by cuts in the graph such that the weakest link in the tree path between any two vertices is labeled by the minimum cut that separates those vertices in the original graph. This tree is called the Gomory–Hu tree of the given (undirected and edge-weighted) graph. Using the same Cartesian tree ancestor technique, you can look up the bandwidth between any pair of vertices, in constant time per query.

My latest arXiv preprint, All-Pairs Minimum Cuts in Near-Linear Time for Surface-Embedded Graphs (arXiv:1411.7055, with Cora Borradaile and new co-authors Amir Nayyeri and Christian Wulff-Nilsen) is on exactly these trees. For arbitrary graphs they can be found in polynomial time, but slowly, because the computation involves multiple flow computations. For planar graphs it was known how to find the Gomory–Hu tree much more quickly, in O(

*n*log

^{3}

*n*) time; we shave a log off this time bound. Then, we extend this result to a larger class of graphs, the graphs of bounded genus, by showing how to slice the bounded-genus surface up (in a number of ways that's exponential in the genus) into planar pieces such that, for every pair of vertices, one of the pieces contains the minimum cut. That gives us exponentially many Gomory-Hu trees, one for each piece, but it turns out that these can all be combined into a single tree for the whole graph.

One curious difference between the planar and higher-genus graphs is that, for planar graphs, the set of cuts given by the Gomory–Hu tree also solves a different problem: it's the minimum-weight cycle basis of the dual graph. In higher-genus graphs, we don't quite have enough cuts to generate the dual cycle space (we're off by the genus) but more importantly some of the optimal cycle basis members might not be cuts. So although the new preprint also improves the time for finding cycle bases in planar graphs, making a similar improvement in the higher genus case remains open.

at November 27, 2014 07:25 AM UTC

**Authors: **Arash Farzan, Alejandro López-Ortiz, Patrick K. Nicholson, Alejandro Salinger **Download:** PDF**Abstract: **The effective use of parallel computing resources to speed up algorithms in
current multi-core parallel architectures remains a difficult challenge, with
ease of programming playing a key role in the eventual success of various
parallel architectures. In this paper we consider an alternative view of
parallelism in the form of an ultra-wide word processor. We introduce the
Ultra-Wide Word architecture and model, an extension of the word-RAM model that
allows for constant time operations on thousands of bits in parallel. Word
parallelism as exploited by the word-RAM model does not suffer from the more
difficult aspects of parallel programming, namely synchronization and
concurrency. For the standard word-RAM algorithms, the speedups obtained are
moderate, as they are limited by the word size. We argue that a large class of
word-RAM algorithms can be implemented in the Ultra-Wide Word model, obtaining
speedups comparable to multi-threaded computations while keeping the simplicity
of programming of the sequential RAM model. We show that this is the case by
describing implementations of Ultra-Wide Word algorithms for dynamic
programming and string searching. In addition, we show that the Ultra-Wide Word
model can be used to implement a nonstandard memory architecture, which enables
the sidestepping of lower bounds of important data structure problems such as
priority queues and dynamic prefix sums. While similar ideas about operating on
large words have been mentioned before in the context of multimedia processors
[Thorup 2003], it is only recently that an architecture like the one we propose
has become feasible and that details can be worked out.

at November 27, 2014 01:41 AM UTC

**Authors: **Jayadev Acharya, Clément L. Canonne, Gautam Kamath **Download:** PDF**Abstract: **A recent model for property testing of probability distributions enables
tremendous savings in the sample complexity of testing algorithms, by allowing
them to condition the sampling on subsets of the domain.

In particular, Canonne et al. showed that, in this setting, testing identity of an unknown distribution $D$ (i.e., whether $D=D^\ast$ for an explicitly known $D^\ast$) can be done with a constant number of samples, independent of the support size $n$ -- in contrast to the required $\sqrt{n}$ in the standard sampling model. However, it was unclear whether the same held for the case of testing equivalence, where both distributions are unknown. Indeed, while the best known upper bound for equivalence testing is ${\rm polylog}(n)$, whether a dependence on the domain size $n$ is necessary was still open, and explicitly posed at the Bertinoro Workshop on Sublinear Algorithms. In this work, we answer the question in the positive, showing that any testing algorithm for equivalence must make $\Omega(\sqrt{\log\log n})$ queries in the conditional sampling model. Interestingly, this demonstrates an intrinsic qualitative gap between identity and equivalence testing, absent in the standard sampling model (where both problems have sampling complexity $n^{\Theta(1)}$).

Turning to another question, we strengthen a result of Ron and Tsur on support size estimation in the conditional sampling model, with an algorithm to approximate the support size of an arbitrary distribution. This result matches the previously known upper bound in the restricted case where the distribution is guaranteed to be uniform over a subset. Furthermore, we settle a related open problem of theirs, proving tight lower bounds on support size estimation with non-adaptive queries.

at November 27, 2014 12:00 AM UTC

**Authors: **Rohit Gurjar, Arpita Korwar, Nitin Saxena, Thomas Thierauf **Download:** PDF**Abstract: **A read once ABP is an arithmetic branching program with each variable
occurring in at most one layer. We give the first polynomial time whitebox
identity test for a polynomial computed by a sum of constantly many ROABPs. We
also give a corresponding blackbox algorithm with quasi-polynomial time
complexity, i.e. $n^{O(\log n)}$. The motivating special case of this model is
sum of constantly many set-multilinear depth-$3$ circuits. The prior results
for that model were only slightly better than brute-force (i.e.
exponential-time).

Our techniques are a new interplay of three concepts for ROABP: low evaluation dimension, basis isolating weight assignment and low-support rank concentration.

at November 27, 2014 01:40 AM UTC

**Authors: **Daniel Irving Bernstein, Lam Si Tung Ho, Colby Long, Mike Steel, Katherine St. John, Seth Sullivant **Download:** PDF**Abstract: **We prove polynomial upper and lower bounds on the expected size of the
maximum agreement subtree of two random binary phylogenetic trees under both
the uniform distribution and Yule-Harding distribution. This positively answers
a question posed in earlier work. Determining tight upper and lower bounds
remains an open problem.

at November 27, 2014 01:42 AM UTC

**Authors: **Jennifer Gamble, Harish Chintakunta, Hamid Krim **Download:** PDF**Abstract: **We present a novel set of methods for analyzing coverage properties in
dynamic sensor networks. The dynamic sensor network under consideration is
studied through a series of snapshots, and is represented by a sequence of
simplicial complexes, built from the communication graph at each time point. A
method from computational topology called zigzag persistent homology takes this
sequence of simplicial complexes as input, and returns a `barcode' containing
the birth and death times of homological features in this sequence. We derive
useful statistics from this output for analyzing time-varying coverage
properties. Further, we propose a method which returns specific representative
cycles for these homological features, at each point along the birth-death
intervals. These representative cycles are then used to track coverage holes in
the network, and obtain size estimates for individual holes at each time point.
A weighted barcode, incorporating the size information, is then used as a
visual and quantitative descriptor of the dynamic network coverage.

at November 27, 2014 01:42 AM UTC

**Authors: **Barna Saha **Download:** PDF**Abstract: **Given a context free language $L(G)$ over alphabet $\Sigma$ and a string $s
\in \Sigma^*$, the language edit distance (Lan-ED) problem seeks the minimum
number of edits (insertions, deletions and substitutions) required to convert
$s$ into a valid member of $L(G)$. The well-known dynamic programming algorithm
solves this problem in $O(n^3)$ time (ignoring grammar size) where $n$ is the
string length [Aho, Peterson 1972, Myers 1985]. Despite its vast number of
applications, there is no algorithm known till date that computes or
approximates Lan-ED in true sub-cubic time.

In this paper we give the first such algorithm that computes Lan-ED almost optimally. For any arbitrary $\epsilon > 0$, our algorithm runs in $\tilde{O}(\frac{n^{\omega}}{poly(\epsilon)})$ time and returns an estimate within a multiplicative approximation factor of $(1+\epsilon)$, where $\omega$ is the exponent of ordinary matrix multiplication of $n$ dimensional square matrices. It also computes the edit script. Further, for all substrings of $s$, we can estimate their Lan-ED within $(1\pm \epsilon)$ factor in $\tilde{O}(\frac{n^{\omega}}{poly(\epsilon)})$ time with high probability. We also design the very first sub-cubic ($\tilde{O}(n^\omega)$) algorithm to handle arbitrary stochastic context free grammar (SCFG) parsing. SCFGs lie the foundation of statistical natural language processing, they generalize hidden Markov models, and have found widespread applications.

To complement our upper bound result, we show that exact computation of Lan-ED in true sub-cubic time will imply a truly sub-cubic algorithm for all-pairs shortest paths. This will result in a breakthrough for a large range of problems in graphs and matrices due to sub-cubic equivalence. By a known lower bound result [Lee 2002], improving upon our time bound of $O(n^\omega)$ for any nontrivial multiplicative approximation is (almost) not possible.

at November 27, 2014 01:42 AM UTC

**Authors: **Jedrzej Kaniewski, Troy Lee, Ronald de Wolf **Download:** PDF**Abstract: **We study the query complexity of computing a function f:{0,1}^n-->R_+ in
expectation. This requires the algorithm on input x to output a nonnegative
random variable whose expectation equals f(x), using as few queries to the
input x as possible. We exactly characterize both the randomized and the
quantum query complexity by two polynomial degrees, the nonnegative literal
degree and the sum-of-squares degree, respectively. We observe that the quantum
complexity can be unboundedly smaller than the classical complexity for some
functions, but can be at most polynomially smaller for functions with range
{0,1}.

These query complexities relate to (and are motivated by) the extension complexity of polytopes. The linear extension complexity of a polytope is characterized by the randomized communication complexity of computing its slack matrix in expectation, and the semidefinite (psd) extension complexity is characterized by the analogous quantum model. Since query complexity can be used to upper bound communication complexity of related functions, we can derive some upper bounds on psd extension complexity by constructing efficient quantum query algorithms. As an example we give an exponentially-close entrywise approximation of the slack matrix of the perfect matching polytope with psd-rank only 2^{n^{1/2+epsilon}}. Finally, we show there is a precise sense in which randomized/quantum query complexity in expectation corresponds to the Sherali-Adams and Lasserre hierarchies, respectively.

at November 27, 2014 01:41 AM UTC

**Authors: **Therese Biedl, Martin Derka **Download:** PDF**Abstract: **In this paper, we prove that every planar graph has a 1-string $B_2$-VPG
representation---a string representation using paths in a rectangular grid that
contain at most two bends. Furthermore, two paths representing vertices $u,v$
intersect precisely once whenever there is an edge between $u$ and $v$.

at November 27, 2014 12:00 AM UTC

**Authors: **Rinat Ben-Avraham, Matthias Henze, Rafel Jaume, Balázs Keszegh, Orit E. Raz, Micha Sharir, Igor Tubis **Download:** PDF**Abstract: **We consider the RMS distance (sum of squared distances between pairs of
points) under translation between two point sets in the plane, in two different
setups. In the partial-matching setup, each point in the smaller set is matched
to a distinct point in the bigger set. Although the problem is not known to be
polynomial, we establish several structural properties of the underlying
subdivision of the plane and derive improved bounds on its complexity. These
results lead to the best known algorithm for finding a translation for which
the partial-matching RMS distance between the point sets is minimized. In
addition, we show how to compute a local minimum of the partial-matching RMS
distance under translation, in polynomial time. In the Hausdorff setup, each
point is paired to its nearest neighbor in the other set. We develop algorithms
for finding a local minimum of the Hausdorff RMS distance in nearly linear time
on the line, and in nearly quadratic time in the plane. These improve
substantially the worst-case behavior of the popular ICP heuristics for solving
this problem.

at November 27, 2014 01:42 AM UTC

**Authors: **Takanori Maehara, Mitsuru Kusumoto, Ken-ichi Kawarabayashi **Download:** PDF**Abstract: **SimRank, proposed by Jeh and Widom, provides a good similarity measure that
has been successfully used in numerous applications. While there are many
algorithms proposed for computing SimRank, their computational costs are very
high. In this paper, we propose a new computational technique, "SimRank
linearization," for computing SimRank, which converts the SimRank problem to a
linear equation problem. By using this technique, we can solve many SimRank
problems, such as single-pair compuation, single-source computation, all-pairs
computation, top k searching, and similarity join problems, efficiently.

at November 27, 2014 01:41 AM UTC

**Authors: **Søren Dahlgaard, Mathias Bæk Tejs Knudsen, Eva Rotenberg, Mikkel Thorup **Download:** PDF**Abstract: **In this paper we propose a hash function for $k$-partitioning a set into bins
so that we get good concentration bounds when combining statistics from
different bins.

To understand this point, suppose we have a fully random hash function applied to a set $X$ of red and blue balls. We want to estimate the fraction $f$ of red balls. The idea of MinHash is to sample the ball with the smallest hash value. This sample is uniformly random and is red with probability $f$. The standard method is to repeat the experiment $k$ times with independent hash functions to reduce variance.

Consider the alternative experiment using a single hash function, where we use some bits of the hash value to partition $X$ into $k$ bins, and then use the remaining bits as a local hash value. We pick the ball with the smallest hash value in each bin.

The big difference between the two schemes is that the second one runs $\Omega(k)$ times faster. In the first experiment, each ball participated in $k$ independent experiments, but in the second one with $k$-partitions, each ball picks its bin, and then only participates in the local experiment for that bin. Thus, essentially, we get $k$ experiments for the price of one. However, no realistic hash function is known to give the desired concentration bounds because the contents of different bins may be too correlated even if the marginal distribution for a single bin is random.

Here, we present and analyze a hash function showing that it does yields statistics similar to that of a fully random hash function when $k$-partitioning a set into bins. In this process we also give more insight into simple tabulation and show new results regarding the power of choice and moment estimation.

at November 27, 2014 01:42 AM UTC

**Authors: **Nitish Umang, Alan L. Erera, Michel Bierlaire **Download:** PDF**Abstract: **In this work, we study the single machine scheduling problem with uncertain
release times and processing times of jobs. We adopt a robust scheduling
approach, in which the measure of robustness to be minimized for a given
sequence of jobs is the worst-case objective function value from the set of all
possible realizations of release and processing times. The objective function
value is the total flow time of all jobs. We discuss some important properties
of robust schedules for zero and non-zero release times, and illustrate the
added complexity in robust scheduling given non-zero release times. We propose
heuristics based on variable neighborhood search and iterated local search to
solve the problem and generate robust schedules. The algorithms are tested and
their solution performance is compared with optimal solutions or lower bounds
through numerical experiments based on synthetic data.

at November 27, 2014 01:41 AM UTC

**Authors: **Glencora Borradaile, David Eppstein, Amir Nayyeri, Christian Wulff-Nilsen **Download:** PDF**Abstract: **For an undirected $n$-vertex graph $G$ with non-negative edge-weights, we
consider the following type of query: given two vertices $s$ and $t$ in $G$,
what is the weight of a minimum $st$-cut in $G$? We solve this problem in
preprocessing time $O(n\log^3 n)$ for graphs of bounded genus, giving the first
sub-quadratic time algorithm for this class of graphs. Our result also improves
by a logarithmic factor a previous algorithm by Borradaile, Sankowski and
Wulff-Nilsen (FOCS 2010) that applied only to planar graphs. Our algorithm
constructs a Gomory-Hu tree for the given graph, providing a data structure
with space $O(n)$ that can answer minimum-cut queries in constant time. The
dependence on the genus of the input graph in our preprocessing time is
$2^{O(g^2)}$.

at November 27, 2014 12:00 AM UTC

**Authors: **Venkatesan Guruswami, Ameya Velingker **Download:** PDF**Abstract: **We prove a lower estimate on the increase in entropy when two copies of a
conditional random variable $X | Y$, with $X$ supported on
$\mathbb{Z}_q=\{0,1,\dots,q-1\}$ for prime $q$, are summed modulo $q$.
Specifically, given two i.i.d copies $(X_1,Y_1)$ and $(X_2,Y_2)$ of a pair of
random variables $(X,Y)$, with $X$ taking values in $\mathbb{Z}_q$, we show \[
H(X_1 + X_2 \mid Y_1, Y_2) - H(X|Y) \ge \alpha(q) \cdot H(X|Y) (1-H(X|Y)) \]
for some $\alpha(q) > 0$, where $H(\cdot)$ is the normalized (by factor $\log_2
q$) entropy. Our motivation is an effective analysis of the finite-length
behavior of polar codes, and the assumption of $q$ being prime is necessary.
For $X$ supported on infinite groups without a finite subgroup and no
conditioning, a sumset inequality for the absolute increase in (unnormalized)
entropy was shown by Tao (2010).

We use our sumset inequality to analyze Ar{\i}kan's construction of polar codes and prove that for any $q$-ary source $X$, where $q$ is any fixed prime, and any $\epsilon > 0$, polar codes allow {\em efficient} data compression of $N$ i.i.d. copies of $X$ into $(H(X)+\epsilon)N$ $q$-ary symbols, as soon as $N$ is polynomially large in $1/\epsilon$. We can get capacity-achieving source codes with similar guarantees for composite alphabets, by factoring $q$ into primes and combining different polar codes for each prime in factorization.

A consequence of our result for noisy channel coding is that for {\em all} discrete memoryless channels, there are explicit codes enabling reliable communication within $\epsilon > 0$ of the symmetric Shannon capacity for a block length and decoding complexity bounded by a polynomial in $1/\epsilon$. The result was previously shown for the special case of binary input channels (Guruswami-Xia '13 and Hassani-Alishahi-Urbanke '13), and this work extends the result to channels over any alphabet.

at November 27, 2014 01:40 AM UTC

* Plus a long-promised discussion on diagonalization *

TRUST security source |

Dexter Kozen has been on the faculty of computer science at Cornell for almost 30 of the department’s 50 years. He first came to Cornell 40 years ago as a graduate student and finished a PhD under Juris Hartmanis in just over 2 years. He was named to the Joseph Newton Pew, Jr., professorship 20 years ago, and celebrated his 60th birthday in 2012. Besides many research achievements he co-authored an award-winning book on Dynamic Logic.

Today we salute the 50th anniversary of Cornell’s department and keep a promise we made 5 years ago to talk about a diagonalization theorem by Dexter. It yields what may be an interesting finite puzzle.

The 50th anniversary symposium earlier this fall was a great occasion; I wish I’d been able to drive over for it. There were two days of talks by Cornell faculty and alumni. It coincided with the department moving into a new building, Gates Hall, named for—who else?—Bill and Melinda Gates as principal donors. Bill Gates came for the dedication and engaged Cornell president David Skorton in a one-hour conversation on how to serve students best.

I have fond memories of my time at Cornell in 1986–7 and 1988–9 split with time at Oxford. I was given a home in the department though my postdoc came from Cornell’s Mathematical Sciences Institute, and I was treated incredibly well. It was a great personal as well as professional time for me. When I last visited two years ago, Gates Hall was just going up across the street, beyond the left-field fence of the baseball field I viewed from my office window in the 1980s. Dick and I wish them the best for the next 50 years.

“Innovative Departments” source |

## 1982

Dexter is on sabbatical in the Netherlands and Denmark this academic year. I first met him in Denmark, at ICALP 1982 in Aarhus. We took part in a local tradition of performing musical numbers at the conference banquet. He had a band called the “Steamin’ Weenies” when I was at Cornell. He has kept his music up with bands of various names through the “Katatonics,” which performed in a Superstorm Sandy benefit two years ago at Ithaca’s club “The Gates” (not named for—who else?—Bill and Melinda Gates).

It is hard to believe, but summer 1982 is three-fourths of the way back to Steve Cook’s 1971 paper which put the versus question on everyone’s map. Back then we knew it was hard but there was more optimism. I have told the story of sharing a train car with Mike Sipser on the way to that conference and hearing Mike’s confidence in being able to solve the question.

The aspect that captivated me that summer was formal logic issues involved in separating complexity classes. They can be approached in two ways: as sets of languages and as subsets of machines. The former I tried to conceptualize as a topological space. As with the Zariski topology of algebraic sets employed by Alexander Grothendieck, it satisfies only the axiom and so is not a Hausdorff space. The latter view was developed by Dexter’s 1979 paper, “Indexings of Subrecursive Classes.”

Dexter’s paper cut to the chase away from logic or topology by treating the problem as one about *programming systems*, i.e., recursive enumerations of machines that have nice properties like efficient substitution and composition. He showed a tradeoff between *power* and *niceness* of what one can do with them. The niftiest theorem, in section 7 of his paper, shows that if you insist on representing by machines that mark cells on a tape as a polynomial time clock, and insist on a composition operator giving only a constant-factor overhead in program size, then both universal simulation and diagonalization need more than polynomial **space**. Thus such representations of will not support a proof of different from , let alone . But in the previous section he gave a theorem showing that if you give up all efficient closure properties, then you can in principle achieve any diagonalization you like.

## Kozen’s Theorem

The only property of the class that is used by the theorem is that it is closed under finite differences: if is different from a language by a finite set, meaning that the symmetric difference is finite, then is in . And of course it uses that has an effective programming system, which is what distinguished bounded closed sets in my topological view.

Theorem 1Let be any enumeration of by machines, and let be any language outside of . Then we can define a function such that

- , and
- where we define .

Moreover, any reasonable formal system that can prove can prove statements 1 and 2. Indeed, we can make a permutation, so that the new indexing involves the same machines as the original, only scrambled. In the case , this yields his prose conclusion:

If is provable at all, then it is provable by diagonalization.

As he was quick to add, this doesn’t say that the mere fact of enables diagonalization, only that working by diagonalization does not impose any additional burden on a reasonable formal system.

*Proof:* We define in stages. At each stage we have “marked” the values for . At stage , take to be the least unmarked value such that

and define . This also marks . A suitable always exists since infinitely many languages in include , which handles the case , and infinitely many exclude , so there’s always a when too. Also clearly is one-to-one since we mark each value. To see that is onto, let be the least unmarked value at any stage . Since and differ by an infinite set, there will always be a in the symmetric difference, and the algorithm will set for the least such .

## Interpretations

The proof works even if is undecidable—we just get that is uncomputable—and there are uncountably many ‘s to go with uncountably many ‘s. When is computable the in the algorithm is computable, and if the indexing includes many copies of machines accepting or then we can get or lower.

The inverse of , that is, the mapping , however, may have explosive growth for infinitely many , depending on how sparse the symmetric difference of with some languages in is. Still, if the statement is provable in a given formal system, then the inverse is provably total, so the diagonalization can be verified. Another way of putting this is that the formal system is able to verify that every language in —that is, every , is eventually enumerated, so the formal system can tell that the class being diagonalized against is all of .

The ease of the proof and its relation to oracle results contributed to controversy over how to interpret it. I’ve mostly felt that the logical “horse” was being put behind or at best alongside the “cart” of combinatorial proof methods. Recently I’ve appreciated how the proof focuses the question on *how large your idea of “*” is rather than how hard is, which was a key issue in the attempted proof by Vinay Deolalikar. The oracle result showing for some computable languages (any -complete language will do) was supposed to argue that diagonalization against the class had no special power as a tool for .

The proof relativizes by taking to be an ensemble of polynomial-time oracle Turing machines giving for each oracle set , and by taking a fixed oracle TM such that is -complete for each . We get a fixed oracle transducer such that executes the algorithm for . Whenever it computes a total function whose diagonal is . If you think of “” as “ relativized to ” then this seems like a recipe for contradiction if the unrelativized is total and . But what happens when is just that computes an undefined function—indeed it doesn’t halt. To make an algebraic analogy, should be parsed as not , so “the diagram does not commute” and there is no problem.

## Variations

I came back to Dexter’s theorem this fall term while re-thinking how best to introduce diagonalization in an undergrad or grad theory course. The classical way is

where is the “Gödel Number” of the machine . My own usual style is to identify a machine or program with its code as a string, thus writing

This removes any need to talk about the correspondence between strings and numbers, Gödel or any kind of numbers. However, styling this via programming raises questions such as whether “” means the source or compiled code, and does it matter how they differ?

Recently I’ve preferred to think of as an *object*, indeed analogizing components to fields of a class. Then “” re-appears as an *encoding* of the object by a (number or) string. We define:

Now it doesn’t matter if we say is the source code or the compiled executable, and it can be anything—we can downplay the “self-reference” aspect if we wish. The encoding function need not be 1-to-1, provided it is “extensional” in the sense that

We still get the diagonal contradiction: if , then contradicting . And , which implies that there is some such that , but by extensionality we have and again that is a contradiction. (Well, you don’t have to tell students this more-complicated proof—just say that is 1-to-1 and it’s just as quick as the usual diagonal proof.)

Returning to Dexter’s diagonal set , we see it is the same as with . Looking at by itself, much as we can relax being 1-to-1, we can relax being onto, so long as is “functionally onto” the languages, in keeping with statement 1 of Theorem 1. Indeed, when the programming system repeats each language infinitely often, we could redo the proof to make an increasing function.

We can abstract this by considering any function from a set into its power set and functions on . It is interesting to try to formalize exactly when , that is,

with being extensional with respect to and being onto the image of . One interesting requirement is that when is not onto , must cover , that is:

Again I wonder if there is a useful analogy in abstract algebra or category theory for this situation. Given the function and , we can define for some choice of such that . For other we can put for any such that . Given the function , we can define for any by taking such that , since is functionally onto , and define .

## A Finite Puzzle

The abstraction nicely gives a concrete puzzle when is a finite set. Then we don’t have Dexter’s property of being closed under finite differences, but we can still ask:

Is every unindexed subset a diagonal? That is, for all with , does there exist such that ?

Equivalently, does there exist such that ? If is 1-to-1, then must be onto, which means must be a permutation since is finite, and likewise must be its inverse. There are interesting cases where is not 1-to-1, in which the extra latitude for and becomes important.

For example, let and let , , and . Then is 1-to-1, so we have six permutations to consider. They become the six columns after the first in the following table:

Every subset not in the range appears; curiously appears twice. If instead we define only, then only three permutations are relevant, but having gives us three other functions to consider:

Once again we have all eight subsets between the range and the diagonals, this time with no repetition.

Which functions have this “pan-diagonal” property? If some element belongs to every set then we can never get into any diagonal, so except for some small- cases the answer is ‘no’ for such . Note that the complementary function gives equivalent results by duality. Hence the answer is also generally ‘no’ when some element is excluded from all subsets . This extends to say that if some elements are collectively included in or fewer subsets, and is one-to-one, then it is impossible to get as a diagonal, so the answer is ‘no’ unless is already part of the range. Note, however, that our second example shows that success is still possible if is not 1-to-1.

Is there an easily-stated criterion for to be pan-diagonal? Or is -hardness lurking about? That is the puzzle. One can also pose it for infinite , when the range of is not closed under finite differences.

## Open Problems

How powerful is diagonalization? Does the puzzle have a simple answer?

We also wish everyone a Happy Thanksgiving.

by KWRegan at November 26, 2014 11:00 PM UTC

at November 26, 2014 08:08 PM UTC

**Authors: **Henning Fernau, Alejandro López-Ortiz, Jazmín Romero **Download:** PDF**Abstract: **We consider the problem of discovering overlapping communities in networks
which we model as generalizations of the Set and Graph Packing problems with
overlap.

As usual for Set Packing problems we seek a collection $\mathcal{S}$ consisting of at least $k$ sets subject to certain disjointness restrictions. In a Set Packing with $t$-Membership, each element of $\mathcal{U}$ belongs to at most $t$ sets while in a Set Packing with $t$-Overlap each pair of sets overlaps in at most $t$ elements. For both problems, each set of $\mathcal{S}$ has at most $r$ elements, and $t$ and $r$ are constants.

Similarly, both of our graph packing problems seek a collection of at least $k$ subgraphs in a graph $G$ each isomorphic to a graph $H \in \mathcal{H}$. In an $\mathcal{H}$-Packing with $t$-Membership, each vertex of $G$ belongs to at most $t$ subgraphs while in an $\mathcal{H}$-Packing with $t$-Overlap each pair of subgraphs overlaps in at most $t$ vertices. For both problems, each member of $\mathcal{H}$ has at most $r$ vertices, and $t$ and $r$ are constants.

We provide NP-Completeness results for all of our packing problems. Given that, we reduce the Set Packing with $t$-Overlap to an $O(r^r k^{r-t-1})$ problem kernel while we achieve an $O(r^r k^{r-1})$ problem kernel for the Set Packing with $t$-Membership. In addition, we reduce the $\mathcal{H}$-Packing with $t$-Membership and its induced version to an $O(r^r k^{r-1})$ kernel. Moreover, we give an $O(r^{2r^2} k^{{r^2}-1})$ kernel for its edge version. On the other hand, we achieve an $O(r^r k^{r-t-1})$ kernel for the $\mathcal{H}$-Packing with $t$-Overlap and its induced version while we provide an $O(r^{2r^2} k^{r^2-t-1})$ kernel for its edge version. Our kernel results match the best kernel for Set and Graph Packing.

at November 26, 2014 01:41 AM UTC

**Authors: **Romeo Rizzi, Gustavo Sacomoto, Marie-France Sagot **Download:** PDF**Abstract: **The problem of listing the $K$ shortest simple (loopless) $st$-paths in a
graph has been studied since the early 1960s. For a non-negatively weighted
graph with $n$ vertices and $m$ edges, the most efficient solution is an
$O(K(mn + n^2 \log n))$ algorithm for directed graphs by Yen and Lawler
[Management Science, 1971 and 1972], and an $O(K(m+n \log n))$ algorithm for
the undirected version by Katoh et al. [Networks, 1982], both using $O(Kn + m)$
space. In this work, we consider a different parameterization for this problem:
instead of bounding the number of $st$-paths output, we bound their length. For
the bounded length parameterization, we propose new non-trivial algorithms
matching the time complexity of the classic algorithms but using only $O(m+n)$
space. Moreover, we provide a unified framework such that the solutions to both
parameterizations -- the classic $K$-shortest and the new length-bounded paths
-- can be seen as two different traversals of a same tree, a Dijkstra-like and
a DFS-like traversal, respectively.

at November 26, 2014 01:41 AM UTC

**Authors: **Leslie Ann Goldberg, Rob Gysel, John Lapinskas **Download:** PDF**Abstract: **A locally-optimal structure is a combinatorial structure such as a maximal
independent set that cannot be improved by certain (greedy) local moves, even
though it may not be globally optimal. It is trivial to construct an
independent set in a graph. It is easy to (greedily) construct a maximal
independent set. However, it is NP-hard to construct a globally-optimal
(maximum) independent set. In general, constructing a locally-optimal structure
is somewhat more difficult than constructing an arbitrary structure, and
constructing a globally-optimal structure is more difficult than constructing a
locally-optimal structure. The same situation arises with listing. The
differences between the problems become obscured when we move from listing to
counting because nearly everything is #P-complete. However, we highlight an
interesting phenomenon that arises in approximate counting, where the situation
is apparently reversed. Specifically, we show that counting maximal independent
sets is complete for #P with respect to approximation-preserving reductions,
whereas counting all independent sets, or counting maximum independent sets is
complete for an apparently smaller class, $\mathrm{\#RH}\Pi_1$ which has a
prominent role in the complexity of approximate counting. Motivated by the
difficulty of approximately counting maximal independent sets in bipartite
graphs, we also study the problem of approximately counting other
locally-optimal structures that arise in algorithmic applications, particularly
problems involving minimal separators and minimal edge separators. Minimal
separators have applications via fixed-parameter-tractable algorithms for
constructing triangulations and phylogenetic trees. Although exact
(exponential-time) algorithms exist for listing these structures, we show that
the counting problems are #P-complete with respect to both exact and
approximation-preserving reductions.

at November 26, 2014 01:40 AM UTC

**Authors: **Ágnes Cseh, Brian C. Dean **Download:** PDF**Abstract: **The stable allocation problem is a many-to-many generalization of the
well-known stable marriage problem, where we seek a bipartite assignment
between, say, jobs (of varying sizes) and machines (of varying capacities) that
is "stable" based on a set of underlying preference lists submitted by the jobs
and machines. We study a natural "unsplittable" variant of this problem, where
each assigned job must be fully assigned to a single machine. Such unsplittable
bipartite assignment problems generally tend to be NP-hard, including
previously-proposed variants of the unsplittable stable allocation problem. Our
main result is to show that under an alternative model of stability, the
unsplittable stable allocation problem becomes solvable in polynomial time;
although this model is less likely to admit feasible solutions than the model
proposed iby McDermid and Manlove, we show that in the event there is no
feasible solution, our approach computes a solution of minimal total congestion
(overfilling of all machines collectively beyond their capacities). We also
describe a technique for rounding the solution of a stable allocation problem
to produce "relaxed" unsplit solutions that are only mildly infeasible, where
each machine is overcongested by at most a single job.

at November 26, 2014 01:40 AM UTC

**Authors: **Dae-Sung Jang, Han-Lim Choi **Download:** PDF**Abstract: **We consider discretization of the 'geometric cover problem' in the plane:
Given a set $P$ of $n$ points in the plane and a compact planar object $T_0$,
find a minimum cardinality collection of planar translates of $T_0$ such that
the union of the translates in the collection contains all the points in $P$.
We show that the geometric cover problem can be converted to a form of the
geometric set cover, which has a given finite-size collection of translates
rather than the infinite continuous solution space of the former. We propose a
reduced finite solution space that consists of distinct canonical translates
and present polynomial algorithms to find the reduce solution space for disks,
convex/non-convex polygons (including holes), and planar objects consisting of
finite Jordan curves.

at November 26, 2014 01:42 AM UTC

**Authors: **Katharina Huber, Leo van Iersel, Vincent Moulton, Celine Scornavacca, Taoyang Wu **Download:** PDF**Abstract: **Binets and trinets are phylogenetic networks with two and three leaves,
respectively. Here we consider the problem of deciding if there exists a binary
level-1 phylogenetic network displaying a given set $\mathcal{T}$ of binary
binets or trinets over a set $X$ of taxa, and constructing such a network
whenever it exists. We show that this is NP-hard for trinets but
polynomial-time solvable for binets. Moreover, we show that the problem is
still polynomial-time solvable for inputs consisting of binets and trinets as
long as the cycles in the trinets have size three. Finally, we present an
$O(3^{|X|} poly(|X|))$ time algorithm for general sets of binets and trinets.
The latter two algorithms generalise to instances containing level-1 networks
with arbitrarily many leaves, and thus provide some of the first supernetwork
algorithms for computing networks from a set of rooted phylogenetic networks.

at November 26, 2014 01:41 AM UTC

**Authors: **Troy Lee, Zhaohui Wei **Download:** PDF**Abstract: **The square root rank of a nonnegative matrix $A$ is the minimum rank of a
matrix $B$ such that $A=B \circ B$, where $\circ$ denotes entrywise product. We
show that the square root rank of the slack matrix of the correlation polytope
is exponential. Our main technique is a way to lower bound the rank of certain
matrices under arbitrary sign changes of the entries using properties of the
roots of polynomials in number fields. The square root rank is an upper bound
on the positive semidefinite rank of a matrix, and corresponds the special case
where all matrices in the factorization are rank-one.

at November 26, 2014 01:40 AM UTC

**Authors: **Kashyap Dixit, Martin Fürer **Download:** PDF**Abstract: **We study the problem of counting the number of \emph{isomorphic} copies of a
given {\em template} graph, say $H$, in the input {\em base} graph, say $G$. In
general, this is (provably) very hard to solve efficiently. So, a lot of work
has gone into designing efficient {\em approximation schemes}, especially, when
$H$ is a perfect matching.

In this work, we present schemes to count $k$-cliques and $k$-clique covers. Our embedding problems are \emph{almost} always approximable. The decision versions of these problems are fundamental and are well studied. Both of these problems are NP-hard. In particular, the {\em $k$-Clique Cover} problem is NP-hard for every $k\ge 3$.

Here, we present {\em fully polynomial time randomized approximation schemes} (fpras) to count $k$-cliques when $k=O(\sqrt{\log n})$ and $k$-clique covers when $k$ is a constant. Our work partially resolves an open problem in [Frieze and McDiarmid (1997)], where they ask whether there exists a fpras for counting $k$-cliques in random graphs. As an aside, we also obtain an alternate derivation of the closed form expression for the $k$-th moment of a binomial random variable. Here, we use the equalities that we derive from binomial theorem. The previous derivation [Knoblauch (2008)] was based on the moment generating function of a binomial random variable.

at November 26, 2014 01:41 AM UTC

**Authors: **Ho-Lin Chen, David Doty, Ján Maňuch, Arash Rafiey, Ladislav Stacho **Download:** PDF**Abstract: **We show that in the hierarchical tile assembly model, if there is a
producible assembly that overlaps a nontrivial translation of itself
consistently (i.e., the pattern of tile types in the overlap region is
identical in both translations), then arbitrarily large assemblies are
producible. The significance of this result is that tile systems intended to
controllably produce finite structures must avoid pattern repetition in their
producible assemblies that would lead to such overlap. This answers an open
question of Chen and Doty (SODA 2012), who showed that so-called
"partial-order" systems producing a unique finite assembly *and" avoiding such
overlaps must require time linear in the assembly diameter. An application of
our main result is that any system producing a unique finite assembly is
automatically guaranteed to avoid such overlaps, simplifying the hypothesis of
Chen and Doty's main theorem.

at November 26, 2014 01:42 AM UTC

**Authors: **Venkatesan Guruswami, Carol Wang **Download:** PDF**Abstract: **The noise model of deletions poses significant challenges in coding theory,
with basic questions like the capacity of the binary deletion channel still
being open. In this paper, we study the harder model of worst-case deletions,
with a focus on constructing efficiently decodable codes for the two extreme
regimes of high-noise and high-rate. Specifically, we construct polynomial-time
decodable codes with the following trade-offs (for any eps > 0):

(1) Codes that can correct a fraction 1-eps of deletions with rate poly(eps) over an alphabet of size poly(1/eps);

(2) Binary codes of rate 1-O~(sqrt(eps)) that can correct a fraction eps of deletions; and

(3) Binary codes that can be list decoded from a fraction (1/2-eps) of deletions with rate poly(eps)

Our work is the first to achieve the qualitative goals of correcting a deletion fraction approaching 1 over bounded alphabets, and correcting a constant fraction of bit deletions with rate aproaching 1. The above results bring our understanding of deletion code constructions in these regimes to a similar level as worst-case errors.

at November 26, 2014 01:41 AM UTC

This weekend, the Institute for Advanced Study in Princeton hosted a workshop on the “Lens of Computation in the Sciences,” which was organized by Avi Wigderson, and was meant to showcase theoretical computer science’s imperialistic ambitions to transform every other field. I was proud to speak at the workshop, representing CS theory’s designs on physics. But videos of all four of the talks are now available, and all are worth checking out:

- Computational Phenomena in Biology, by Leslie Valiant
- Computational Phenomena in Economics, by Tim Roughgarden
- Computational Phenomena in Social Science, by Jon Kleinberg
- Computational Phenomena in Physics, by me

Unfortunately, the videos were slow to buffer when I last tried it. While you’re waiting, you could also check my PowerPoint slides, though they overlap considerably with my previous talks. (As always, if you can’t read PowerPoint, then go ask another reader of this blog to convert the file into a format you like.)

Thanks so much to Avi, and everyone else at IAS, for organizing an awesome workshop!

by Scott at November 25, 2014 11:02 PM UTC

-- Although the workshop will not have proceedings (so you can as usual submit a talk and still submit it to a conference of your choosing), exceptional submissions will be invited to a special issue of the Journal of Privacy and Confidentiality.

-- The PC is pretty inter-disciplinary. This is certainly not just a Theory-A workshop. Work on privacy in all areas is on topic.

-- You get to hear Jon Ullman give a (presumably excellent) talk.

CALL FOR PAPERS

TPDP 2015

First workshop on the Theory and Practice of Differential Privacy

18th April 2015, London, UK

Affiliated to ETAPS

http://tpdp.computing.dundee.ac.uk

Differential privacy is a promising approach to the privacy-preserving

release of data: it offers a strong guaranteed bound on the increase

in harm that a user incurs as a result of participating in a

differentially private data analysis.

Researchers in differential privacy come from several area of computer

science as algorithms, programming languages, security, databases,

machine learning, as well as from several areas of statistics and data

analysis. The workshop is intended to be an occasion for researchers

from these different research areas to discuss the recent developments

in the theory and practice of differential privacy.

**Submissions**

The overall goal of TPDP is to stimulate the discussion on the

relevance of differentially private data analyses in practice. For

this reason, we seek contributions from different research areas of

computer science and statistics.

Authors are invited to submit a short abstract (4-5 pages maximum) of

their work by January 23, 2015. Abstracts must be written in English

and be submitted as a single PDF file at the EasyChair page for TPDP:

https://easychair.org/conferences/?conf=3Dtpdp2015

Submissions will be judged on originality, relevance, interest and

clarity. Submission should describe novel works or works that have

already appeared elsewhere but that can stimulate the discussion

between the different communities. Accepted abstracts will

be presented at the workshop.

The workshop will not have formal proceedings, but we plan to have a

special issue of the Journal of Privacy and Confidentiality devoted to

TPDP. Authors presenting valuable contributions at the workshop will

be invited to submit a journal version of their work right after the

workshop.

**Important Dates**

-January 23, 2015 - Abstract Submission

-February 10, 2015 - Notification

-February 14, 2015 - Deadline early registration ETAPS

-April 18, 2015 - Workshop

-May 15, 2015 Deadline for journal special issue

**Topics**

Specific topics of interest for the workshop include (but are not limited t=

o):

theory of differential privacy,

verification techniques for differential privacy,

programming languages for differential privacy,

models for differential privacy,

trade-offs between privacy protection and analytic utility,

differential privacy and surveys,

relaxations of the differential privacy definition,

differential privacy vs other privacy notions and methods,

differential privacy and accuracy,

practical differential privacy,

implementations for differential privacy,

differential privacy and security,

applications of differential privacy.

**Invited Speakers**

Jonathan Ullman - Simons Fellow at Columbia University,

Another invited speaker joint with HotSpot'15 to be confirmed.

**Program Committee**

Gilles Barthe - IMDEA Software

Konstantinos Chatzikokolakis - CNRS and LIX, Ecole Polytechnique

Kamalika Chaudhuri - UC San Diego

Graham Cormode - University of Warwick

George Danezis - University College London

Marco Gaboardi - University of Dundee

Matteo Maffei - CISPA, Saarland University

Catuscia Palamidessi - INRIA and LIX, Ecole Polytechnique

Benjamin C. Pierce - University of Pennsylvania

Aaron Roth - University of Pennsylvania

David Sands - Chalmers University of Technology

Chris Skinner - London School of Economics

Adam Smith - Pennsylvania State University

Carmela Troncoso - Gradiant

Salil Vadhan - Harvard University

by Aaron Roth (noreply@blogger.com) at November 25, 2014 06:49 PM UTC

- The LIPIcs format automatically includes several standard LaTeX packages including
`babel`,`amsmath`,`amsthm`,`amssymb`, and`hyperref`. So there's no point in including them yourself and (if you specify incompatible options) it may cause an error to include them yourself. I haven't needed to change the`hyperref`options, but if you do, see here. - You may like to use the
`lineno`package so that, when reviewers give you comments on your submission, they can tell you more accurately which line they're referring to. If you try this with the LIPIcs format, you will notice that you don't get line numbers in the last paragraph of a proof, nor in a paragraph that contains a displayed equation (even if you correctly delimit the equation with`\[...\]`instead of using the obsolete`$$...$$`, which can also cause problems with`lineno`). The solution to the proof problem is to change the proof termination symbol (a triangle instead of the usual Halmos box) to use an explicit`$...$`instead of`\ensuremath`):`\renewcommand\qedsymbol{\textcolor{darkgray}{$\blacktriangleleft$}}`

The solution to the displayed equation problem is more complicated, but is given in this blog post from 2007 (the update near the start of that post). Why this incompatibility hasn't been fixed in the last seven years is a different question. - If you use the
`numberwithinsect`document class option (pronounced "number with insect"), then the LIPIcs format numbers theorems, lemmas, etc by what section they are in: Lemma 2.1 for the first lemma in Section 2, etc. But if you also run past the page limit and use appendices, you may notice that the lemmas are being given numbers that re-use previously used numbers, because although the appendices have letters rather than numbers the lemmas use numbers: the first lemma in Appendix B is also called Lemma 2.1. The problem is that the LIPIcs style expands the`\thesection`macro (the one that gives the number or letter of the current section) at the time it defines`\thetheorem`(the one that gives the name of the current theorem or lemma). So when you use`\appendix`(or`\begin{appendix}`if you like to pretend that non-environment commands are really environments),`\thesection`gets changed but it's too late to make a difference to`\thetheorem`. The fix is to add the following lines after`\appendix`:`\makeatletter`

\edef\thetheorem{\expandafter\noexpand\thesection\@thmcountersep\@thmcounter{theorem}}

\makeatother - I've already written about the problems with using the
`\autoref`command of the`hyperref`package: because LIPIcs wants to use a shared numeric sequence for theorems, lemmas, etc.,`\autoref`thinks they are all theorems. Someone else also recently asked about this problem. This is a more general incompatibilty between`amsthm`and`hyperref`, but LIPIcs also includes some of its own code for theorem formatting, which seems to be causing the fixes one can find for`amsthm`not to work. The solution is to fall back to the non-`hyperref`way of doing things:`Lemma~\ref{lem:my-lemma-name}`etc. - Speaking of theorems: if you use
`\newtheorem`, you probably want to have a previous line`\theoremstyle{definition}`so that whatever you're defining looks like the other theorems and lemmas. - On the first page of a LIPIcs paper, the last line of text may be uncomfortably close to the Creative Commons licencing icon. I haven't found a direct workaround for this (although probably it's possible) but you can obtain better spacing by having a footnote (for instance one listing your grant acknowledgements) or a bottom figure on that page.
- If you're used to trying to fit things into a page limit with LNCS format, you may have learned to use
`\paragraph`as a trick to save space over subsections. That doesn't work very well in LIPIcs, for two reasons. First, because it will give you an ugly paragraph number like 6.0.0.1 (the first numbered paragraph in an un-numbered subsubsection of an un-numbered subsection of section 6). You can work around this by using`\paragraph*`. But second, because unlike in LNCS the paragraph heading won't be folded into the paragraph that follows it, so you save a lot less space. I don't want to try to work around this one. And fortunately I haven't yet seen my coauthors adding code like`\noindent{\bfseries Paragraph heading.} Paragraph text...`(or worse`\bf ...`). Solution: find different tricks for your space-saving efforts. Like maybe write more tersely.

Anyone else have any timely tips?

at November 25, 2014 08:12 AM UTC

The basic goal of this is to try to understand how to measure the thickness of a piece of paper that has been folded into a shape that lies flat in the plane. For instance, in designing origami pieces, it's undesirable to have too much thickness, both because it wastes paper causing your piece to be smaller than it needs to and because it may be an obstacle to forming features of your piece that are supposed to be thin.

The obvious thing to do is to just count the number of layers of paper that cover any point of the plane, but can be problematic. For instance, if you have two offset accordion folds (drawn sideways below)

/\/\/\/\/\ \/\/\/\/\/then it's not really accurate to say that the thickness is the same as if you just had one of the two sets of folds: one of the two folds is raised up by the thickness of the other one so the whole folded piece of paper is more like the sum of the thicknesses of its two halves.

In the preprint, we model the thickness by assuming that the flat parts of the paper are completely horizontal, at integer heights, that two overlapping parts of paper have to be at different heights, and that a fold can connect parts of paper that are at any two different heights. But then, it turns out that finding an assignment of heights to the parts of paper that minimizes the maximum height is hard, even for one-dimensional problems where we are given a crease pattern of mountain and valley folds as input, without being told exactly how to arrange those folds. The reason is that there can be ambiguities about how the folded shape can fit into pockets formed by other parts of the fold, and choosing the right pockets is difficult.

at November 25, 2014 06:00 AM UTC

**Authors: **Pawel Gawrychowski, Patrick K. Nicholson **Download:** PDF**Abstract: **In this paper we consider various encoding problems for range queries on
arrays. In these problems, the goal is that the encoding occupies the
information theoretic minimum space required to answer a particular set of
range queries. Given an array $A[1..n]$ a range top-$k$ query on an arbitrary
range $[i,j] \subseteq [1,n]$ asks us to return the ordered set of indices
$\{l_1 ,...,l_k \}$ such that $A[l_m]$ is the $m$-th largest element in
$A[i..j]$. We present optimal encodings for range top-$k$ queries, as well as
for a new problem which we call range min-max, in which the goal is to return
the indices of both the minimum and maximum element in a range.

at November 25, 2014 01:41 AM UTC

**Authors: **Bernhard Bliem, Stefan Woltran **Download:** PDF**Abstract: **A secure set $S$ in a graph is defined as a set of vertices such that for any
$X \subseteq S$ the majority of vertices in the neighborhood of $X$ belongs to
$S$. It is known that deciding whether a set $S$ is secure in a graph is
co-NP-complete. However, it is still open how this result contributes to the
actual complexity of deciding whether for a given graph $G$ and integer $k$, a
non-empty secure set for $G$ of size at most $k$ exists. While membership in
the class $\Sigma^P_2$ is rather easy to see for this existence problem,
showing $\Sigma^P_2$-hardness is quite involved. In this paper, we provide such
a hardness result, hence classifying the secure set existence problem as
$\Sigma^P_2$-complete. We do so by first showing hardness for a variant of the
problem, which we then reduce step-by-step to secure set existence. In total,
we obtain eight new completeness results for different variants of the secure
set existence problem.

at November 25, 2014 01:41 AM UTC

**Authors: **Nathan Adelgren, Pietro Belotti, Akshay Gupte **Download:** PDF**Abstract: **Biobjective mixed integer linear programs (BOMILP) are optimization problems
where two linear objectives are optimized over a polyhedron while restricting
some of the variables to be integer. Since many of the techniques for solving
BOMILP (or approximating its solution set) are iterative processes which
utilize data discovered during early iterations to aid in the discovery of
improved data during later iterations, it is highly desirable to efficiently
store the nondominated subset of a given set of data. This problem has not
received considerable attention in the context of BOMILP; only naive methods
have been implemented. We seek to bridge this gap by presenting a new data
structure in the form of a modified binary tree that stores, updates, searches
and returns nondominated solutions. This structure takes points and line
segments in $\mathbb{R}^2$ as input and stores the nondominated subset of this
input. We note that when used alongside an exact solution procedure, such as
branch-and-bound (BB), at termination the data stored by this structure is
precisely the set of Pareto optimal solutions. We perform two experiments. The
first is designed to compare the utility of our structure for storing
nondominated data to that of a dynamic list which updates via pairwise
comparison. In the second we use our data structure alongside the biobjective
BB techniques available in the literature and solve specific instances of
BOMILP. The results of our first experiment suggest that the data structure
performs reasonably well in handling input of up to $10^7$ points or segments
and does so much more efficiently than a dynamic list. The results of the
second experiment show that when our structure is utilized alongside BB
fathoming is enhanced and running times improve slightly.

at November 25, 2014 01:42 AM UTC

**Authors: **Michael Codish, Luís Cruz-Filipe, Peter Schneider-Kamp **Download:** PDF**Abstract: **This paper studies properties of the back end of a sorting network and
illustrates the utility of these in the search for networks of optimal size or
depth. All previous works focus on properties of the front end of networks and
on how to apply these to break symmetries in the search. The new properties
help shed understanding on how sorting networks sort and speed-up solvers for
both optimal size and depth by an order of magnitude.

at November 25, 2014 01:42 AM UTC