# Theory of Computing Blog Aggregator

### Voronoi diagram of orthogonal polyhedra in two and three dimensions

Authors: Ioannis Z. Emiris, Christina Katsamaki
Abstract: Voronoi diagrams are a fundamental geometric data structure for obtaining proximity relations. We consider collections of axis-aligned orthogonal polyhedra in two and three-dimensional space under the max-norm, which is a particularly useful scenario in certain application domains. We construct the exact Voronoi diagram inside an orthogonal polyhedron with holes defined by such polyhedra. Our approach avoids creating full-dimensional elements on the Voronoi diagram and yields a skeletal representation of the input object. We introduce a complete algorithm in 2D and 3D that follows the subdivision paradigm relying on a bounding-volume hierarchy; this is an original approach to the problem. The complexity is adaptive and comparable to that of previous methods, namely linear in the number of sites, namely edges or facets resp. We also provide a numerically stable, open-source implementation in Julia, illustrating the practical nature of our algorithm.

### An Optimal Monotone Contention Resolution Scheme for Bipartite Matchings via a Polyhedral Viewpoint

Authors: Simon Bruggmann, Rico Zenklusen
Abstract: Relaxation and rounding approaches became a standard and extremely versatile tool for constrained submodular function maximization. One of the most common rounding techniques in this context are contention resolution schemes. Such schemes round a fractional point by first rounding each coordinate independently, and then dropping some elements to reach a feasible set. Also the second step, where elements are dropped, is typically randomized. This leads to an additional source of randomization within the procedure, which can complicate the analysis. We suggest a different, polyhedral viewpoint to design contention resolution schemes, which avoids to deal explicitly with the randomization in the second step. This is achieved by focusing on the marginals of a dropping procedure. Apart from avoiding one source of randomization, our viewpoint allows for employing polyhedral techniques. Both can significantly simplify the construction and analysis of contention resolution schemes. We show how, through our framework, one can obtain an optimal monotone contention resolution scheme for bipartite matchings. So far, only very few results are known about optimality of monotone contention resolution schemes. Our contention resolution scheme for the bipartite case also improves the lower bound on the correlation gap for bipartite matchings. Furthermore, we derive a monotone contention resolution scheme for matchings that significantly improves over the previously best one. At the same time, our scheme implies that the currently best lower bound on the correlation gap for matchings is not tight. Our results lead to improved approximation factors for various constrained submodular function maximization problems over a combination of matching constraints with further constraints.

### Fast Computing the Algebraic Degree of Boolean Functions

Authors: Valentin Bakoev
Abstract: Here we consider an approach for fast computing the algebraic degree of Boolean functions. It combines fast computing the ANF (known as ANF transform) and thereafter the algebraic degree by using the weight-lexicographic order (WLO) of the vectors of the $n$-dimensional Boolean cube. Byte-wise and bitwise versions of a search based on the WLO and their implementations are discussed. They are compared with the usual exhaustive search applied in computing the algebraic degree. For Boolean functions of $n$ variables, the bitwise implementation of the search by WLO has total time complexity $O(n.2^n)$. When such a function is given by its truth table vector and its algebraic degree is computed by the bitwise versions of the algorithms discussed, the total time complexity is $\Theta((9n-2).2^{n-7})=\Theta(n.2^n)$. All algorithms discussed have time complexities of the same type, but with big differences in the constants hidden in the $\Theta$-notation. The experimental results after numerous tests confirm the theoretical results - the running times of the bitwise implementation are dozens of times better than the running times of the byte-wise algorithms.

### Shortest-Path-Preserving Rounding

Authors: Herman Haverkort, David Kübel, Elmar Langetepe
Abstract: Various applications of graphs, in particular applications related to finding shortest paths, naturally get inputs with real weights on the edges. However, for algorithmic or visualization reasons, inputs with integer weights would often be preferable or even required. This raises the following question: given an undirected graph with non-negative real weights on the edges and an error threshold $\varepsilon$, how efficiently can we decide whether we can round all weights such that shortest paths are maintained, and the change of weight of each shortest path is less than $\varepsilon$? So far, only for path-shaped graphs a polynomial-time algorithm was known. In this paper we prove, by reduction from 3-SAT, that, in general, the problem is NP-hard. However, if the graph is a tree with $n$ vertices, the problem can be solved in $O(n^2)$ time.

### Approximation results for makespan minimization with budgeted uncertainty

Authors: Marin Bougeret, Klaus Jansen, Michael Poss, Lars Rohwedder
Abstract: We study approximation algorithms for the problem of minimizing the makespan on a set of machines with uncertainty on the processing times of jobs. In the model we consider, which goes back to~\cite{BertsimasS03}, once the schedule is defined an adversary can pick a scenario where deviation is added to some of the jobs' processing times. Given only the maximal cardinality of these jobs, and the magnitude of potential deviation for each job, the goal is to optimize the worst-case scenario. We consider both the cases of identical and unrelated machines. Our main result is an EPTAS for the case of identical machines. We also provide a $3$-approximation algorithm and an inapproximability ratio of $2-\epsilon$ for the case of unrelated machines

### Silent MST approximation for tiny memory

Authors: Lélia Blin, Swan Dubois, Laurent Feuilloley
Abstract: In network distributed computing, minimum spanning tree (MST) is one of the key problems, and silent self-stabilization one of the most demanding fault-tolerance properties. For this problem and this model, a polynomial-time algorithm with $O(\log^2\!n)$ memory is known for the state model. This is memory optimal for weights in the classic $[1,\text{poly}(n)]$ range (where $n$ is the size of the network). In this paper, we go below this $O(\log^2\!n)$ memory, using approximation and parametrized complexity.

More specifically, our contributions are two-fold. We introduce a second parameter~$s$, which is the space needed to encode a weight, and we design a silent polynomial-time self-stabilizing algorithm, with space $O(\log n \cdot s)$. In turn, this allows us to get an approximation algorithm for the problem, with a trade-off between the approximation ratio of the solution and the space used. For polynomial weights, this trade-off goes smoothly from memory $O(\log n)$ for an $n$-approximation, to memory $O(\log^2\!n)$ for exact solutions, with for example memory $O(\log n\log\log n)$ for a 2-approximation.

### Memory Lower Bounds for Self-Stabilization

Authors: Lélia Blin, Laurent Feuilloley, Gabriel Le Bouder
Abstract: In the context of self-stabilization, a \emph{silent} algorithm guarantees that the register of every node does not change once the algorithm has stabilized. At the end of the 90's, Dolev et al. [Acta Inf. '99] showed that, for finding the centers of a graph, for electing a leader, or for constructing a spanning tree, every silent algorithm must use a memory of $\Omega(\log n)$ bits per register in $n$-node networks. Similarly, Korman et al. [Dist. Comp. '07] proved, using the notion of proof-labeling-scheme, that, for constructing a minimum-weight spanning trees (MST), every silent algorithm must use a memory of $\Omega(\log^2n)$ bits per register. It follows that requiring the algorithm to be silent has a cost in terms of memory space, while, in the context of self-stabilization, where every node constantly checks the states of its neighbors, the silence property can be of limited practical interest. In fact, it is known that relaxing this requirement results in algorithms with smaller space-complexity.

In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary self-stabilizing algorithms, not necessarily silent. To our knowledge, the only known lower bound on the memory requirement for general algorithms, also established at the end of the 90's, is due to Beauquier et al.~[PODC '99] who proved that registers of constant size are not sufficient for leader election algorithms. We improve this result by establishing a tight lower bound of $\Theta(\log \Delta+\log \log n)$ bits per register for self-stabilizing algorithms solving $(\Delta+1)$-coloring or constructing a spanning tree in networks of maximum degree~$\Delta$. The lower bound $\Omega(\log \log n)$ bits per register also holds for leader election.

### Efficient Profile Maximum Likelihood for Universal Symmetric Property Estimation

Authors: Moses Charikar, Kirankumar Shiragur, Aaron Sidford
Abstract: Estimating symmetric properties of a distribution, e.g. support size, coverage, entropy, distance to uniformity, are among the most fundamental problems in algorithmic statistics. While each of these properties have been studied extensively and separate optimal estimators are known for each, in striking recent work, Acharya et al. 2016 showed that there is a single estimator that is competitive for all symmetric properties. This work proved that computing the distribution that approximately maximizes \emph{profile likelihood (PML)}, i.e. the probability of observed frequency of frequencies, and returning the value of the property on this distribution is sample competitive with respect to a broad class of estimators of symmetric properties. Further, they showed that even computing an approximation of the PML suffices to achieve such a universal plug-in estimator. Unfortunately, prior to this work there was no known polynomial time algorithm to compute an approximate PML and it was open to obtain a polynomial time universal plug-in estimator through the use of approximate PML. In this paper we provide a algorithm (in number of samples) that, given $n$ samples from a distribution, computes an approximate PML distribution up to a multiplicative error of $\exp(n^{2/3} \mathrm{poly} \log(n))$ in time nearly linear in $n$. Generalizing work of Acharya et al. 2016 on the utility of approximate PML we show that our algorithm provides a nearly linear time universal plug-in estimator for all symmetric functions up to accuracy $\epsilon = \Omega(n^{-0.166})$. Further, we show how to extend our work to provide efficient polynomial-time algorithms for computing a $d$-dimensional generalization of PML (for constant $d$) that allows for universal plug-in estimation of symmetric relationships between distributions.

### Inference under Information Constraints II: Communication Constraints and Shared Randomness

Authors: Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi
Abstract: A central server needs to perform statistical inference based on samples that are distributed over multiple users who can each send a message of limited length to the center. We study problems of distribution learning and identity testing in this distributed inference setting and examine the role of shared randomness as a resource. We propose a general-purpose simulate-and-infer strategy that uses only private-coin communication protocols and is sample-optimal for distribution learning. This general strategy turns out to be sample-optimal even for distribution testing among private-coin protocols. Interestingly, we propose a public-coin protocol that outperforms simulate-and-infer for distribution testing and is, in fact, sample-optimal. Underlying our public-coin protocol is a random hash that when applied to the samples minimally contracts the chi-squared distance of their distribution to the uniform distribution.

### Congratulations, Dr. Tillman!

from David Eppstein

Today I participated in the successful dissertation defense of Bálint Tillman, a student of Athina Markopoulou in the UCI Graduate Program in Networked Systems.

Bálint has been investigating problems connected with the Erdős–Gallai theorem, which states that it is possible to test whether a sequence of numbers is the degree distribution of a graph (the sequence of numbers of vertices of each possible degree) and if so, find a graph with that degree distribution, in polynomial time. The degree distribution can be extended to a matrix called the joint degree distribution, which specifies the number of pairs of adjacent vertices with each combination of degrees, and to higher-order tensors specifying the degrees of subgraphs with more than two vertices.

In his INFOCOM 2015 paper “Construction of simple graphs with a target joint degree matrix and beyond”, Bálint showed that one can recognize the joint degree distributions of simple graphs, and reconstruct a graph with that distribution, in polynomial time. The algorithm works equally well when the vertices are distinguished in other ways than by degree and the input matrix specifies the target number of edges with each pair of degrees between each class of vertices. Later, in KDD 2017, he extended these results to directed graphs and at NetSci 2018 he showed how to find a realization with as few connected components as possible.

On the other hand, if one adds only a little bit of extra information to the joint degree distribution, such as the total number of triangles in the graph, it becomes NP-complete to recognize whether the input describes a valid graph and NP-hard to reconstruct a graph that realizes a given description. This comes from a poster by Bálint with Will Devanny and me at NetSci 2016, where we found the reduction from graph 3-coloring depicted below.

To perform an NP-hardness reduction, one should start with a graph for which it’s hard to test 3-colorability, and translate it into an instance of whatever other problem you want to prove hard. But instead let’s pretend for now that we start with a little more information: a graph that’s known to be 3-colorable, and a specific 3-coloring of it. To turn this into a hard problem for realizability of joint distribution plus number of triangles, we add a triangle to the graph, representing the three colors, and connect each original graph vertex to the new triangle vertex for its color. Then we add enough hair (in the form of degree-one vertices) to the augmented graph to make all vertices have distinct degrees, except within the triangle of new vertices where all three degrees should be the same. Now take as the result of the reduction the pair of the joint degree distribution and number of triangles in the augmented graph.

But now the trick is that can be computed directly from your starting graph, without knowing its coloring or even whether it is colorable. Because the degrees are distinct, and tells you the number of edges for each combination of degrees, any realization of must contain a copy of your starting graph augmented by a triangle. The graph and the triangle might be connected to each other differently than they were before, but their connection pattern must still correspond to a different valid 3-coloring, because otherwise you would form some extra triangles in the graph (one for each invalidly-colored edge) and not correctly match the value of . So is realizable if and only if your starting graph has a 3-coloring. This reduction proves that testing realizability of pairs is NP-complete.

There’s even more material along these lines in Bálint’s dissertation, but some of it is not yet published. I think the plan is to get all of that submitted over the summer before Bálint starts a new position at Google. Congratulations, Bálint!

by David Eppstein at May 21, 2019 06:20 PM UTC

### Making Up Tests

from Richard Lipton

It’s harder to make up tests than to take them

 [ Recent photo ]

Ken Regan has been busy these last few days working on making a final exam, giving the exam, and now grading the exam.

Today Ken and I want to talk about tests.

I also have a test for you. You can jump right to our test of knowledge. Do not, please, use any search tools, especially Google.

## Test Theory

Ken recently made up a final exam. We both have had to make countless tests over the years. I was never trained in how to make a good test. Nor how to make a test at all. I am still puzzled about how to do it.

Avi Wigderson once told me that Michael Rabin only asked questions on his exams that he had stated already in lectures. Is there a theory of what makes a proper test? I do not know any.

Suppose that before the exam we lectured and the students learned ${T}$ and ${F}$: Here ${T}$ are true statements and ${F}$ are false statements. A rote type question might be:

Is the statement ${S}$ true or false?

Here ${S}$ would be in either ${T}$ or ${F}$. This type of question is purely a memory problem.

A more difficult test would have questions like:

Is ${S}$ true or false

Here ${S}$ would be equivalent to some ${S'}$ that is in ${T}$ or in ${F}$. The equivalence between ${S}$ and ${S'}$ would require only the application of a few simple logical rules. This is much harder for students. In the limit we could have ${S}$ and ${S'}$ far apart, even could have it an open problem if ${S}$ and ${S'}$ are equivalent.

## Our Test

Question 1: We all know that Dick Karp created the P=NP question. What is Dick’s middle name?

1. Mark

2. Manning

3. Mathew

4. Richard

Question 2: This year is the fifty-first anniversary of STOC. Where was the first one held?

1. Marina del Rey, CA

2. Massapequa, NY

3. Boston, MA

4. Chicago, IL

Question 3: Which of these did not happen in 1969?

1. The first automatic teller machine in the United States is installed.