Authors: Ioannis Z. Emiris, Christina Katsamaki
Download: PDF
Abstract: Voronoi diagrams are a fundamental geometric data structure for obtaining
proximity relations. We consider collections of axisaligned orthogonal
polyhedra in two and threedimensional space under the maxnorm, 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 fulldimensional 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 boundingvolume 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, opensource implementation in Julia,
illustrating the practical nature of our algorithm.
Theory of Computing Blog Aggregator
Authors: Simon Bruggmann, Rico Zenklusen
Download: PDF
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.
Authors: Valentin Bakoev
Download: PDF
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 weightlexicographic order
(WLO) of the vectors of the $n$dimensional Boolean cube. Bytewise 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((9n2).2^{n7})=\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
bytewise algorithms.
Authors: Herman Haverkort, David Kübel, Elmar Langetepe
Download: PDF
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 nonnegative 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 pathshaped
graphs a polynomialtime algorithm was known. In this paper we prove, by
reduction from 3SAT, that, in general, the problem is NPhard. However, if the
graph is a tree with $n$ vertices, the problem can be solved in $O(n^2)$ time.
Authors: Marin Bougeret, Klaus Jansen, Michael Poss, Lars Rohwedder
Download: PDF
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 worstcase 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
Authors: Lélia Blin, Swan Dubois, Laurent Feuilloley
Download: PDF
Abstract: In network distributed computing, minimum spanning tree (MST) is one of the
key problems, and silent selfstabilization one of the most demanding
faulttolerance properties. For this problem and this model, a polynomialtime
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 twofold. We introduce a second parameter~$s$, which is the space needed to encode a weight, and we design a silent polynomialtime selfstabilizing algorithm, with space $O(\log n \cdot s)$. In turn, this allows us to get an approximation algorithm for the problem, with a tradeoff between the approximation ratio of the solution and the space used. For polynomial weights, this tradeoff 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 2approximation.
Authors: Lélia Blin, Laurent Feuilloley, Gabriel Le Bouder
Download: PDF
Abstract: In the context of selfstabilization, 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 prooflabelingscheme, that, for constructing
a minimumweight 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
selfstabilization, 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
spacecomplexity.
In this paper, we are aiming at measuring how much gain in terms of memory can be expected by using arbitrary selfstabilizing 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 selfstabilizing 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.
Authors: Moses Charikar, Kirankumar Shiragur, Aaron Sidford
Download: PDF
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 plugin 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 plugin
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 plugin
estimator for all symmetric functions up to accuracy $\epsilon =
\Omega(n^{0.166})$. Further, we show how to extend our work to provide
efficient polynomialtime algorithms for computing a $d$dimensional
generalization of PML (for constant $d$) that allows for universal plugin
estimation of symmetric relationships between distributions.
Authors: Jayadev Acharya, Clément L. Canonne, Himanshu Tyagi
Download: PDF
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 generalpurpose simulateandinfer
strategy that uses only privatecoin communication protocols and is
sampleoptimal for distribution learning. This general strategy turns out to be
sampleoptimal even for distribution testing among privatecoin protocols.
Interestingly, we propose a publiccoin protocol that outperforms
simulateandinfer for distribution testing and is, in fact, sampleoptimal.
Underlying our publiccoin protocol is a random hash that when applied to the
samples minimally contracts the chisquared distance of their distribution to
the uniform distribution.
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 higherorder 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 NPcomplete to recognize whether the input describes a valid graph and NPhard 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 3coloring depicted below.
To perform an NPhardness reduction, one should start with a graph for which it’s hard to test 3colorability, 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 3colorable, and a specific 3coloring 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 degreeone 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 3coloring, because otherwise you would form some extra triangles in the graph (one for each invalidlycolored edge) and not correctly match the value of . So is realizable if and only if your starting graph has a 3coloring. This reduction proves that testing realizability of pairs is NPcomplete.
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
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 and : Here are true statements and are false statements. A rote type question might be:
Is the statement true or false?
Here would be in either or . This type of question is purely a memory problem.
A more difficult test would have questions like:
Is true or false
Here would be equivalent to some that is in or in . The equivalence between and would require only the application of a few simple logical rules. This is much harder for students. In the limit we could have and far apart, even could have it an open problem if and are equivalent.
Our Test
No looking at Google please.
Question 1: We all know that Dick Karp created the P=NP question. What is Dick’s middle name?
 Mark
 Manning
 Mathew
 Richard
Question 2: This year is the fiftyfirst anniversary of STOC. Where was the first one held?
 Marina del Rey, CA
 Massapequa, NY
 Boston, MA
 Chicago, IL
Question 3: Which of these did not happen in 1969?
 The first automatic teller machine in the United States is installed.
 The $500 bills are officially removed from circulation.
 The first The Limited store opens, in San Francisco.
 The New York Mets win the World Series.
Question 4: The first STOC conference program committee included:
 No women.
 A person named Mike.
 A person named Pat.
 All the above.
Question 5: How do you tell if you are a “theoretical computer scientist”?
 You wear flipflops in the winter.
 You regularly attend STOC.
 You wear glasses.
 You cannot program a computer.
Question 6: “Cooking” a chess problem means:
 Showing it is in a family of NPcomplete problems on boards.
 Showing it has two or more solutions (or no solutions).
 Showing it cannot be solved by Steve Cook.
 Showing that it cannot be solved by the bestmove strategy.
Question 7: The other theory conference is called FOCS. Which of these is true about this conference:
 The name was selected by a person named Edward.
 It has never had parallel sessions.
 It was originally called Symposium on Switching Circuit Theory and Logical Design.
 The artwork for the proceedings cover is by an artist named Smith, who never published in the conference.
Question 8: What do the STOC conferences have in common with last night’s final episode of Game of Thrones?
 Both had flying horses and whistling pigs.
 No dragons were harmed during either.
 Both have left many big questions unanswered.
 Both are explained by the “Prisoner’s Dilemma” game solution.
Question 9: STOC has been held on each of these islands except:
 Long Island, NY.
 Puerto Rico.
 Crete.
 Vancouver Island.
Question 10: What term appears in the titles of three awardwinning STOC/FOCS papers since 2016?
 Quantum.
 Quadratic/subquadratic.
 Quadtree.
 Quasi/quasipolynomial.
Open Problems
Answers: Note 1a means question 1 and answer 1 and so on. This is a wordpress issue.
by rjlipton at May 21, 2019 12:48 PM UTC
In this post we return to the generic form of the FTRL online optimization algorithm. If the cost functions are linear, as they will be in all the applications that I plan to talk about, the algorithm is:
where is the convex set of feasible solutions that the algorithm is allowed to produce, is the linear loss function at time , and is the strictly convex regularizer.
If we have an unconstrained problem, that is, if , then the optimization problem (1) has a unique solution: the such that
and we can usually both compute efficiently in an algorithm and reason about effectively in an analysis.
Unfortunately, we are almost always interested in constrained settings, and then it becomes difficult both to compute and to reason about it.
A very nice special case happens when the regularizer acts as a barrier function for , that is, the (norm of the) gradient of goes to infinity when one approaches the boundary of . In such a case, it is impossible for the minimum of (1) to occur at the boundary and the solution will be again the unique in such that
We swept this point under the rug when we studied FTRL with negativeentropy regularizer in the settings of experts, in which is the set of probability distributions. When we proceeded to solve (1) using Lagrange multipliers, we ignored the nonnegativity constraints. The reason why it was ok to do so was that the negativeentropy is a barrier function for the nonnegative orthant .
Another important special case occurs when the regularizer is a multiple of lengthsquared. In this case, we saw that we could “decouple” the optimization problem by first solving the unconstrained optimization problem, and then projecting the solution of the unconstrained problem to :
Then we have the closedform solution and, depending on the set , the projection might also have a nice closedform, as in the case that comes up in results related to regularity lemmas.
As we will see today, this approach of solving the unconstrained problem and then projecting on works for every regularizer, for an appropriate notion of projection called the Bregman projection (the projection will depend on the regularizer).
To define the Bregman projection, we will first define the Bregman divergence with respect to the regularizer , which is a nonnegative “distance” defined on (or possibly a subset of for which the regularizer is a barrier function). Then, the Bregman projection of on is defined as .
Unfortunately, it is not so easy to reason about Bregman projections either, but the notion of Bregman divergence offers a way to reinterpret the FTRL algorithm from another point of view, called mirror descent. Via this reinterpretation, we will prove the regret bound
which carries the intuition that the regret comes from a combination of the “distance” of our initial solution from the offline optimum and of the “stability” of the algorithm, that is, the “distance” between consecutive soltuions. Nicely, the above bound measures both quantities using the same “distance” function.
1. Bregman Divergence and Bregman Projection
For a strictly convex function , we define the Bregman divergence associated to as
that is, the difference between the value of at and the value of the linear approximation of at (centered at ). By the strict convexity of we have and iff . These properties suggest that we may think of as a kind of “distance” between and , which is a useful intuition although it is important to keep in mind that the divergence need not be symmetric and need not satisfy the triangle inequality.
Now we show that, assuming that is well defined and strictly convex on all , and that the losses are linear, the constrained optimization problem (1) can be solved by first solving the unconstrained problem and then “projecting” the solution on by finding the point in of smallest Bregman divergence from the unconstrained optimum:
The proof is very simple. The optimum of the unconstrained optimization problem is the unique such that
that is, the unique such that
On the other hand, is defined as
that is,
where the second equality above follows from the fact that two functions that differ by a constant have the same optimal solutions.
Indeed we see that the above “decoupled” characterization of the FTRL algorithm would have worked for any definition of a function of the form
and that our particular choice of what “stuff dependent only on ” to add makes which is reasonable for something that we want to think of as a “distance function.”
Note that, in all of the above, we can replace with a convex set provided that is a barrier function for . In that case
is the unique such that
and everything else follows analogously.
2. Examples
2.1. Bregman Divergence of LengthSquared
If , then
so Bregman divergence is distancesquared, and Bregman projection is just (Euclidean) projection.
2.2. Bregman Divergence of Negative Entropy
If, for , we define
then the associated Bregman divergence is the generalized KL divergence.
where so that
Note that, if and are probability distributions, then the final two terms above cancel out, leaving just the KL divergence .
3. Mirror Descent
We now introduce a new perspective on FTRL.
In the unconstrained setting, if is a strictly convex function and is the associated Bregman divergence, the mirror descent algorithm for online optimization has the update rule
The idea is that we want to find a solution that is good for the past loss functions, but that does not “overfit” too much. If, in past steps, had been chosen to be such a solution for the loss functions , then, in choosing , we want to balance staying close to but also doing well with respect to , hence the above definition.
Theorem 1 Initialized with , the unconstrained mirror descent algorithm is identical to FTRL with regularizer .
Proof: We will proceed by induction on . At , the definition of is the same. For larger , we know that FTRL will choose the unique such that , so we will assume that this is true for the mirror descent algorithm for and prove it for .
First, we note that the function is strictly convex, because it equals
and so it is a sum of a strictly convex function , linear functions in , and constants independent of . This means that is the unique point at which the gradient of the above function is zero, that is,
and so
and, using the inductive hypothesis, we have
as desired.
In the constrained case, there are two variants of mirror descent. Using the terminology from Elad Hazan’s survey, agile mirror descent is the natural generalization of the unconstrained algorithm:
Following the same steps as the proof in the previous section, it is possible to show that agile mirror descent is equivalent to solving, at each iteration, the “decoupled” optimization problems
That is, we can first solve the unconstrained problem and then project on . (Again, we can always replace by a set for which is a barrier function and such that .)
The lazy mirror descent algorithm has the update rule
The initialization is
Fact 2 Lazy mirror descent is equivalent to FTRL.
Proof: The solutions are the unconstrained optimum of FTRL, and is the Bregman projection of on . We proved in the previous section that this characterizes constrained FTRL.
What about agile mirror descent? In certain special cases it is equivalent to lazy mirror descent, and hence to FTRL, but it usually leads to a different set of solutions.
We will provide an analysis of lazy mirror descent, but first we will give an analysis of the regret of unconstrained FTRL in terms of Bregman divergence, which will be the model on which we will build the proof for the constrained case.
4. A Regret Bound for FTRL in Terms of Bregman Divergence
In this section we prove the following regret bound.
Theorem 3 Unconstrained FTRL with regularizer satisfies the regret bound
where is the Bregman divergence associated with .
We will take the mirror descent view of unconstrained FTRL, so that
We proved that
This means that we can rewrite the regret suffered at step with respect to as
and the theorem follows by adding up the above expression for and recalling that .
Unfortunately I have no geometric intuition about the above identity, although, as you can check yourself, the algebra works neatly.
5. A Regret Bound for Agile Mirror Descent
In this section we prove the following generalization of the regret bound from the previous section.
Theorem 4 Agile mirror descent satisfies the regret bound
The first part of the update rule of agile mirror descent is
and, following steps that we have already carried out before, satisfies
This means that we can rewrite the regret suffered at step with respect to as
where the same mystery cancellations as before make the above identity true.
Now I will wield another piece of magic, and I will state without proof the following fact about Bregman projections
Lemma 5 If and is the Bregman projection on of a point , then
That is, if we think of as a “distance,” the distance from to its closest point in plus the distance from to is at most the distance from to . Note that this goes in the opposite direction as the triangle inequality (which ok, because typically does not satisfy the triangle inequality).
In particular, the above lemma gives us
and so
Now summing over and recalling that we have our theorem.
by luca at May 21, 2019 01:42 AM UTC
Authors: Mahdi Boroujeni, Sina Dehghani, Soheil Ehsani, MohammadTaghi HajiAghayi, Saeed Seddighin
Download: PDF
Abstract: Despite persistent efforts, there is no known technique for obtaining
unconditional superlinear lower bounds for the computational complexity of the
problems in P. Vassilevska Williams and Williams introduce a fruitful approach
to advance a better understanding of the computational complexity of the
problems in P. In particular, they consider All Pairs Shortest Paths (APSP) and
other fundamental problems such as checking whether a matrix defines a metric,
verifying the correctness of a matrix product, and detecting a negative
triangle in a graph. Abboud, Grandoni, and Vassilevska Williams study
wellknown graph centrality problems such as Radius, Median, etc., and make a
connection between their computational complexity to that of two fundamental
problems, namely APSP and Diameter. They show any algorithm with subcubic
running time for these centrality problems, implies a subcubic algorithm for
either APSP or Diameter. In this paper, we define vertex versions for these
centrality problems and based on that we introduce new complementary problems.
The main open problem of Abboud et al. is whether or not APSP and Diameter are
equivalent under subcubic reduction. One of the results of this paper is APSP
and CoDiameter, which is the complementary version of Diameter, are equivalent.
Moreover, for some of the problems in this set, we show that they are
equivalent to their complementary versions. Considering the slight difference
between a problem and its complementary version, these equivalences give us the
impression that every problem has such a property, and thus APSP and Diameter
are equivalent. This paper is a step forward in showing a subcubic equivalence
between APSP and Diameter, and we hope that the approach introduced in our
paper can be helpful to make this breakthrough happen.
Authors: Roman Galay
Download: PDF
Abstract: As it follows from G\"odel's incompleteness theorems, any consistent formal
system of axioms and rules of inference should imply a true unprovable
statement. Actually this fundamental principle can be efficiently applicable in
Computational Mathematics and Complexity Theory concerning the computational
complexity of problems from the class NP, particularly and especially the
NPcomplete ones. While there is a wide set of algorithms for these problems
that we call heuristic, the correctness or/and complexity of each concrete
algorithm (or the probability of its correct and polynomialtime work) on a
class of instances is often too difficult to determine, although we may also
assume the existence of a variety of algorithms for NPcomplete problems that
are both correct and polynomialtime on all the instances from a given class
(where the given problem remains NPcomplete), but whose correctness or/and
polynomialtime complexity on the class is impossible to prove as an example
for G\"odel's theorems. However, supposedly such algorithms should possess a
certain complicatedness of processing the input data and treat it in a certain
algebraically "entangled" manner. The same algorithmic analysis in fact
concerns all the other significant problems and subclasses of NP, such as the
graph isomorphism problem and its associated complexity class GI.
The following short article offers a couple of algebraically entangled polynomialtime algorithms for the graph isomorphism and clique problems whose correctness is yet to be determined either empirically or through attempting to find proofs.
Authors: Sebastian Berndt, Valentin Dreismann, Kilian Grage, Klaus Jansen, Ingmar Knof
Download: PDF
Abstract: Online algorithms that allow a small amount of migration or recourse have
been intensively studied in the last years. They are essential in the design of
competitive algorithms for dynamic problems, where objects can also depart from
the instance. In this work, we give a general framework to obtain so called
robust online algorithms for these dynamic problems: these online algorithm
achieve an asymptotic competitive ratio of $\gamma+\epsilon$ with migration
$O(1/\epsilon)$, where $\gamma$ is the best known offline asymptotic
approximation ratio. In order to use our framework, one only needs to construct
a suitable online algorithm for the static online case, where items never
depart. To show the usefulness of our approach, we improve upon the best known
robust algorithms for the dynamic versions of generalizations of Strip Packing
and Bin Packing, including the first robust algorithm for general
$d$dimensional Bin Packing and Vector Packing.
Authors: Lijie Chen, Ofer Grossman
Download: PDF
Abstract: We develop techniques to prove lower bounds for the BCAST(log n) Broadcast
Congested Clique model (a distributed message passing model where in each
round, each processor can broadcast an O(log n)sized message to all other
processors). Our techniques are built to prove bounds for natural input
distributions. So far, all lower bounds for problems in the model relied on
constructing specifically tailored graph families for the specific problem at
hand, resulting in lower bounds for artificially constructed inputs, instead of
natural input distributions.
One of our results is a lower bound for the directed planted clique problem. In this problem, an input graph is either a random directed graph (each directed edge is included with probability 1/2), or a random graph with a planted clique of size k. That is, k randomly chosen vertices have all of the edges between them included, and all other edges in the graph appear with probability 1/2. The goal is to determine whether a clique exists. We show that when k = n^(1/4  eps), this problem requires a number of rounds polynomial in n.
Additionally, we construct a pseudorandom generator which fools the Broadcast Congested Clique. This allows us to show that every k round randomized algorithm in which each processor uses up to n random bits can be efficiently transformed into an O(k)round randomized algorithm in which each processor uses only up to O(k log n) random bits, while maintaining a high success probability. The pseudorandom generator is simple to describe, computationally very cheap, and its seed size is optimal up to constant factors. However, the analysis is quite involved, and is based on the new technique for proving lower bounds in the model.
The technique also allows us to prove the first average case lower bound for the Broadcast Congested Clique, as well as an averagecase time hierarchy.
Authors: Yair Bartal, Nova Fandina, Ofer Neiman
Download: PDF
Abstract: A {\em tree cover} of a metric space $(X,d)$ is a collection of trees, so
that every pair $x,y\in X$ has a low distortion path in one of the trees. If it
has the stronger property that every point $x\in X$ has a single tree with low
distortion paths to all other points, we call this a {\em Ramsey} tree cover.
Tree covers and Ramsey tree covers have been studied by
\cite{BLMN03,GKR04,CGMZ05,GHR06,MN07}, and have found several important
algorithmic applications, e.g. routing and distance oracles. The union of trees
in a tree cover also serves as a special type of spanner, that can be
decomposed into a few trees with low distortion paths contained in a single
tree; Such spanners for Euclidean pointsets were presented by \cite{ADMSS95}.
In this paper we devise efficient algorithms to construct tree covers and Ramsey tree covers for general, planar and doubling metrics. We pay particular attention to the desirable case of distortion close to 1, and study what can be achieved when the number of trees is small. In particular, our work shows a large separation between what can be achieved by tree covers vs. Ramsey tree covers.
Authors: Soheil Behnezhad, Laxman Dhulipala, Hossein Esfandiari, Jakub Łącki, Warren Schudy, Vahab Mirrokni
Download: PDF
Abstract: We introduce the Adaptive Massively Parallel Computation (AMPC) model, which
is an extension of the Massively Parallel Computation (MPC) model. At a high
level, the AMPC model strengthens the MPC model by storing all messages sent
within a round in a distributed data store. In the following round, all
machines are provided with random read access to the data store, subject to the
same constraints on the total amount of communication as in the MPC model. Our
model is inspired by the previous empirical studies of distributed graph
algorithms using MapReduce and a distributed hash table service.
This extension allows us to give new graph algorithms with much lower round complexities compared to the best known solutions in the MPC model. In particular, in the AMPC model we show how to solve maximal independent set in $O(1)$ rounds and connectivity/minimum spanning tree in $O(\log\log_{m/n} n)$ rounds both using $O(n^\delta)$ space per machine for constant $\delta < 1$. In the same memory regime for MPC, the best known algorithms for these problems require polylog $n$ rounds. Our results imply that the 2Cycle conjecture, which is widely believed to hold in the MPC model, does not hold in the AMPC model.
Authors: Noga Alon, Shiri Chechik, Sarel Cohen
Download: PDF
Abstract: In this work we derandomize two central results in graph algorithms,
replacement paths and distance sensitivity oracles (DSOs) matching in both
cases the running time of the randomized algorithms.
For the replacement paths problem, let G = (V,E) be a directed unweighted graph with n vertices and m edges and let P be a shortest path from s to t in G. The {\sl replacement paths} problem is to find for every edge e \in P the shortest path from s to t avoiding e. Roditty and Zwick [ICALP 2005] obtained a randomized algorithm with running time of ~O(m \sqrt{n}). Here we provide the first deterministic algorithm for this problem, with the same ~O(m \sqrt{n}) time.
For the problem of distance sensitivity oracles, let G = (V,E) be a directed graph with realedge weights. An fSensitivity Distance Oracle (fDSO) gets as input the graph G=(V,E) and a parameter f, preprocesses it into a datastructure, such that given a query (s,t,F) with s,t \in V and F \subseteq E \cup V, F \le f being a set of at most f edges or vertices (failures), the query algorithm efficiently computes the distance from s to t in the graph G \setminus F ({\sl i.e.}, the distance from s to t in the graph G after removing from it the failing edges and vertices F). For weighted graphs with real edge weights, Weimann and Yuster [FOCS 2010] presented a combinatorial randomized fDSO with ~O(mn^{4\alpha}) preprocessing time and subquadratic ~O(n^{22(1\alpha)/f}) query time for every value of 0 < \alpha < 1. We derandomize this result and present a combinatorial deterministic fDSO with the same asymptotic preprocessing and query time.
Authors: Michael Dinitz, Yasamin Nazari, Zeyu Zhang
Download: PDF
Abstract: There has been significant recent progress on algorithms for approximating
graph spanners, i.e., algorithms which approximate the best spanner for a given
input graph. Essentially all of these algorithms use the same basic LP
relaxation, so a variety of papers have studied the limitations of this
approach and proved integrality gaps for this LP in a variety of settings. We
extend these results by showing that even the strongest liftandproject
methods cannot help significantly, by proving polynomial integrality gaps even
for $n^{\Omega(\epsilon)}$ levels of the Lasserre hierarchy, for both the
directed and undirected spanner problems. We also extend these integrality gaps
to related problems, notably Directed Steiner Network and ShallowLight Steiner
Network.
Authors: Ahmed Shokry
Download: PDF
Abstract: Utilizing graph algorithms is a common activity in computer science.
Algorithms that perform computations on large graphs are not always efficient.
This work investigates the SingleSource Shortest Path (SSSP) problem, which is
considered to be one of the most important and most studied graph problems.
This thesis contains a review of the SSSP problem in both theory and practice.
In addition, it discusses a new singlesource shortestpath algorithm that
achieves the same $O(n \cdot m)$ time bound as the traditional
BellmanFordMoore algorithm but outperforms it and other stateoftheart
algorithms in practice.
The work is comprised of three parts. The first discusses some basic shortestpath and negativecycledetection algorithms in literature from the theoretical and practical point of view. The second contains a discussion of a new algorithm for the singlesource shortestpath problem that outperforms most stateoftheart algorithms for several wellknown families of graphs. The main idea behind the proposed algorithm is to select the fewest mosteffective vertices to scan. We also propose a discussion of correctness, termination, and the proof of the worstcase time bound of the proposed algorithm. This section also suggests two different implementations for the proposed algorithm, the first runs faster while the second performs a fewer number of operations. Finally, an extensive computational study of the different shortest paths algorithms is conducted. The results are proposed using a new evaluation metric for shortestpath algorithms. A discussion of outcomes, strengths, and weaknesses of the various shortest path algorithms are also included in this work.
Authors: Osman Asif Malik, Stephen Becker
Download: PDF
Abstract: We present a method for randomizing a formula for bilinear computation of
matrix products. We consider the implications of such randomization when the
formula itself is approximate, and when the formula is exact but its
computation is plagued by numerical error due to finite precision arithmetic.
Our theoretical results and numerical experiments indicate that our method can
improve performance in both settings for a negligible increase in computational
complexity.
The Department of Computer Science at Royal Holloway, University of London, invites applications for a Lecturer position (a fulltime and permanent (tenured) post). We are recruiting for an academic member of staff who can strengthen our research, which falls broadly within Algorithms and Complexity, Artificial Intelligence, Distributed and Global Computing, and Software Language Engineering.
Website: https://jobs.royalholloway.ac.uk/vacancy.aspx?ref=0519179
Email: Jose.Fiadeiro@rhul.ac.uk
by shacharlovett at May 20, 2019 06:34 PM UTC
Guest Column: The Third P =?NP Poll (see here)
that appeared in Lane Hemaspaandra's SIGACT News Complexity Column.
I kept track of the following:
1) Number of corrections. Anything that I changed. Could be style, a new thought, need not be (though could be) an error.
2) Errors. These are things that really need to be corrected, like having `think' instead of `thing' .
Corrections vs Errors, an Example:
If I refer to Lane Hemaspaandra as Notorious L.A.N that is a correction and an error, as he is Notorous L.A.H.
If I refer to Lane Hemaspaandra as Notorious L.A.H and decide to change it to LAH that is a correction that is not an error.
I didn't keep track of serious errors vs typos, but after the first 3 proofreads there were no more serious errors sort of you'll see. Most serious was a fontsgonewild thing where half the paper was in boldface.
Here is a history of the number of corrections
1) Lane proofread the first draft. κ corrections where κ is some cardinal between the cardinality of N and the cardinality of 2^{N} . Its value depends on which model of set theory you are in. (My spellchecker thinks that cardinality is not a word. I checked and I am spelling it correctly but perhaps it's one of those things where I stare at it too much and keep misreading it.)
Henceforth I omit the word proofread as it is understood
2) Bill G: 81 corrections, 29 of which were errors.
3) Clyde: 64 corrections, of which 17 were errors.
4) Bill G: 40 corrections, of which 21 were errors (I had added a new section causing more errors)
5) Clyde: 30 corrections of which 10 were errors.
6) Bill G: 24 corrections of which 6 were errors.
7) Clyde: 18 corrections of which 8 were errors.
8) David Sekora (A CS grad student at Maryland who at one time wanted to be an English Major): f15 corrections of which 15 were errors. Really! Typos dagnabbit! (Spell check thinks that dagnabbit is spelled wrong. Umin that case what is the correct spelling?)
9) Nathan Grammel (A CS grad student at Maryland) :6 corrections of which 3 were errors.
10) Bill G, proofreading backwards, a paragraph at a time: 29 corrections of which 5 were errors.
11) Justin Hontz, an ugrad who TAs for me: 10 corrections of which 7 were errors.
12) Karthik Abinav, a grad student in theory at Maryland: 2 corrections both of which were errors. Was this the end or are there still issues?
13) Josh Twitty, an ugrad who TAs for me: 0 corrections. YEAH!
14) Dan Smolyak, an ugrad CS and Eco major:4 corrections, all 4 errors. Error sounds too strong. For example, one of them was to replace ?. with ? Yes, its an error, but not that important. It DOES point to his carefulness as a proofreader.
15) Clyde Kruskal :20 corrections, 10 of which were errors. To call them errors seems wrong when he corrects Group theory' to Group Theory. None of these corrections were caused by prior comments. I think all of the errors were in the paper early on, undetected until now!
16) Backwards Bill G again: 28 corrections, 14 of which were errors. Again, the errors were minor. Most of the errors were relatively recent. As an example, if I list out topics in math like:
a) Group Theory, Set Theory, and Ramsey Theory
then I am supposed to use capital letters, but if I say in prose
Lance Fortnow thinks that the techniques used will be group theory, set theory, and Ramsey theory
then only the R in Ramsey Theory is in caps. Makes me glad I'm in math.
17) Lane got penultimate proofread. Lane found 75 (yes 75 WOW) of which 66 (yes 66 WOW) were errors. Many of these were spacing and latex things that I would never have noticed (indeed I didn't notice) and most readers would not have noticed (hmmm how do I know that?) but only an editor could catch (hmmm when I've edited the book review column and now the open problems column and I never found more than 10 errors). So when all is said and done: KUDOS to Lane! And My point was that you can never get all the errors out. On that I am correct. I wonder if there are still errors? Yeah, but at most 10. However, I said that BEFORE giving it to Lane.
18) Stephen Fenner, the editor of SIGACT news got FINAL proofread. He found that I spelled his name wrong . How many errors are left? I would bet at most 10. I would bet that I would lose that bet.

Why after multiple proofreadings are there still errors? (My spell check thinks proofreadings is not a word. Maybe my spell check is worried that if people get documents proofread a lot then they won't be needed anymore. This blog post refutes that thought.)
1) An error can occur from a correction. This caused a massive problem with another paper. Lane's next column will be by me and coauthors on The Muffin Problem. We had all kinds of problems with the colors and sizes Massive Magenta Muffins or Miniature Magenta Muffins? Sizes gone wild! Again Kudos to my proofreaders and to Lane for catching this rather important error.
2) If some passage is added late in the process it will surely have errors.
3) An error correction may clear away the brush so you can see other errors.
4) With LaTeX (or Word for some) we have the ability to get things perfect. So there is no cost to keeping on perfecting things. This lead so many corrections that are not errors.
5) I know of an adviser who would first say change A to B, and later change B back to A. (None of that happened with the paper discussed above).
Are errors inevitable? Clyde Kruskal tells me that his father Martin Kruskal, as a teenager, read Courant and Robbins book What is Mathematics and found some errors in it. Martin's mother didn't believe him and marched him over to Courant's house:
MARTIN MOTHER: Martin claims to have found errors in your book.
COURANT: (laughs) There are errors in every book.
Courant was so impressed that ten (or so) years later Courant became Martin's PhD adviser.
by GASARCH (noreply@blogger.com) at May 20, 2019 02:14 PM UTC
I would like to congratulate my Taiwanese readers for being in the first Asian country to introduce samesex marriage.
by luca at May 18, 2019 08:41 PM UTC
That is “app” as in an online application
[ Leo Stein ] 
Leo Stein is an assistant professor in the department of Physics and Astronomy at the University of Mississippi. His research interests include general relativity from an astrophysical standpoint.
Today I want to share an unusual proof of his.
Mathematics and complexity theory are all about proving theorems. Most of the time, so far, we prove the old way: we write out a humanly readable proof. At least we hope the proof is readable. Some of the time, we use a computer to check or even create the proof. Sometimes we do extensive numerical computations, but these are not proofs.
Solving Quadratic Equations
I have known, as I am sure you do, forever that a quadratic equation can be solved in closed form. That is
has the two solutions
I have discussed this before here and its relationship to the World’s Fair in Flushing Meadows.
A natural question is: Are square roots needed in any formula for quadratic equations? The answer is “Yes”.
Theorem 1 There does not exist any continuous function from the space of quadratic polynomials to complex numbers which associates to any quadratic polynomial a root of that polynomial.
Corollary 2 There is no quadratic formula built out of a finite combination of field operations and the functions , and the coefficients of the polynomial.
The corollary uses the basic fact that are continuous functions. Note that each has a single branch on complex plane, whereas radicals and the logarithm function do not. So how do we prove the theorem?
An App Based Proof
Here is a novel, I think, proof that uses an app. Stein has written the app and it is here. He explains how to use it. I strongly suggest that you try this yourself.
To get a feel for all this, drag the coefficient to and the coefficient to . You should have two real roots in root space (one at , the other at ). Let’s call the negative root, and the positive root. Now move the coefficient around in a small loop (i.e. move it around a little bit, and then return it to where it started). Note that the roots move continuously, and then return to their original positions. Next, move in a big loop (big enough that it orbits around ). Something funny happens: the roots and switch places.
Leo Goldmakher says here:
Pause and think about this for a second. This is really, really weird.
Here is one immediate consequence of this observation:
Theorem 3 There does not exist any continuous function from the space of quadratic polynomials to complex numbers which associates to any quadratic polynomial a root of that polynomial.
And so the corollary follows.
A Standard Proof
Goldmakher writes out a more conventional proof in his paper titled Arnold’s Elementary Proof Of The Insolvability Of The Quintic. He also shows the following theorem:
Theorem 4 Fix a positive integer . Any quintic formula built out of the field operations, continuous functions, and radicals must have nesting of level more than .
This says that there can be no fixed formula for fifth degree, quintic, polynomials. Of course, this follows from Galois theory, but his proof uses just calculus. The Arnold is Vladimir Arnold.
Open Problems
Do you know other cases of an app with animation conveying the essence of a mathematical proof? This means more than “proofs in pictures” or “proofs without words”—the animation and interactivity are crucial.
by rjlipton at May 18, 2019 08:03 PM UTC
We now discuss how to view proofs of certain regularity lemmas as applications of the FTRL methodology.
The Szemeredi Regularity Lemma states (in modern language) that every dense graph is well approximate by a graph with a very simple structure, made of the (edgedisjoint) union of a constant number of weighted complete bipartite subgraphs. The notion of approximation is a bit complicated to describe, but it enables the proof of counting lemmas, which show that, for example, the number of triangles in the original graph is well approximated by the (appropriately weighted) number of triangles in the approximating graph.
Analogous regularity lemmas, in which an arbitrary object is approximated by a lowcomplexity object, have been proved for hypergraphs, for subsets of abelian groups (for applications to additive combinatorics), in an analytic setting (for applications to graph limits) and so on.
The weak regularity lemma of Frieze and Kannan provides, as the name suggests, a weaker kind of approximation than the one promised by Szemeredi’s lemma, but one that is achievable with a graph that has a much smaller number of pieces. If is the “approximation error” that one is willing to tolerate, Szemeredi’s lemma constructs a graph that is the union of a weighted complete bipartite subgraphs where the height of the tower of exponentials is polynomial in . In the FriezeKannan construction, that number is cut down to a single exponential . This result too can be generalized to graph limits, subsets of groups, and so on.
With Tulsiani and Vadhan, we proved an abstract version of the FriezeKannan lemma (which can be applied to graphs, functions, distributions, etc.) in which the “complexity” of the approximation is . In the graph case, the approximating graph is still the union of complete bipartite subgraphs, but it has a more compact representation. One consequence of this result is that for every highminentropy distribution , there is an efficiently samplable distribution with the same minentropy as , that is indistinguishable from . Such a result could be taken to be a proof that what GANs attempt to achieve is possible in principle, except that our result requires an unrealistically high entropy (and we achieve “efficient samplability” and “indistinguishability” only in a weak sense).
All these results are proved with a similar strategy: one starts from a trivial approximator, for example the empty graph, and then repeats the following iteration: if the current approximator achieves the required approximation, then we are done; otherwise take a counterexample, and modify the approximator using the counterexample. Then one shows that:
 The number of iterations is bounded, by keeping track of an appropriate potential function;
 The “complexity” of the approximator does not increase too much from iteration to iteration.
Typically, the number of iterations is , and the difference between the various results is given by whether at each iteration the “complexity” increases exponentially, or by a multiplicative factor, or by an additive term.
Like in the post on pseudorandom constructions, one can view such constructions as an online game between a “builder” and an “inspector,” except that now the online optimization algorithm will play the role of the builder, and the inspector is the one acting as an adversary. The bound on the number of rounds comes from the fact that the online optimization algorithms that we have seen so far achieve amortized error per round after rounds, so it takes rounds for the error bound to go below .
We will see that the abstract weak regularity lemma of my paper with Tulsiani and Vadhan (and hence the graph weak regularity lemma of Frieze and Kannan) can be immediately deduced from the theory developed in the previous post.
When I was preparing these notes, I was asked by several people if the same can be done for Szemeredi’s lemma. I don’t see a natural way of doing that. For such results, one should maybe use the online optimization techniques as a guide rather than as a black box. In general, iterative arguments (in which one constructs an object through a series of improvements) require the choice of a potential function, and an argument about how much the potential function changes at every step. The power of the FTRL method is that it creates the potential function and a big part of the analysis automatically and, even where it does not work directly, it can serve as an inspiration.
One could imagine a counterfactual history in which people first proved the weak regularity lemma using online optimization out of the box, as we do in this post, and then decided to try and use an L2 potential function and an iterative method to get the Szemeredi lemma, subsequently trying to see what happens if the potential function is entropy, thus discovering Jacob Fox’s major improvement on the “triangle removal lemma,” which involves the construction of an approximator that just approximates the number of triangles.
1. A “vanilla” weak regularity lemma
Frieze and Kannan proved the following basic result about graph approximations, which has a number of algorithmic applications. If is a set of vertices which is understood from the context, and are disjoint subsets of vertices, then let , that is, the boolean matrix such that iff and .
The cut norm of a matrix is
In the following we will identify a graph with its adjacency matrix.
Theorem 1 Let be an graph on vertices and be an approximation parameter.
Then there are sets and scalars , where , such that if we define
we have
We will prove the following more general version.
Theorem 2 Let be a set, be a bounded function, be a family of functions mapping to and be an approximation parameter. Then there are functions in and scalars , with , such that if we define
we have
We could also, with the same proof, argue about a possibly infinite set with a measure such that is finite, and, after defining the inner product
we could prove the same conclusion of the theorem, with instead of as an error bound.
Here is the proof: run the FTRL algorithm with L2squared regularizer in the setup in which the space of solutions is the set of all functions and the loss functions are linear. Every time the algorithm proposes a solution , if there is a function such that either or , the adversary will pick, respectively, or as a loss function . When the adversary has no such choice, we stop and the function is our desired approximation.
First of all, let us analyze the number of rounds. Here the maximum norm of the functions in is , so after rounds we have the regret bound
Now let us consider to be our offline solution: we have
which implies
Finally, recall that
where is the scaling constant in the definition of the regularizer ( is of order of when is order of ), and so our final approximator computed at the last round is a weighted sum of functions from .
2. The weak regularity lemma
Frieze and Kannan’s weak regularity lemma has the following form.
Theorem 3 Let be an graph on vertices and be an approximation parameter.
Then there is a partition of into sets , and there are bounded weights for such that if we defined the weighted graph where the weight of the edge in is , where and , then we have
Notice that if we did not require the weights to be between 0 and 1 then the result of the previous section can also be cast in the above language, because we can take the partition to be the “Sigmaalgebra generated by” the sets .
For a scalar , let be defined as
where stands for truncation. Note that is the L2 projection of on .
Theorem 3 is a special case of the following result, proved in our paper with Tulsiani and Vadhan.
Theorem 4 Let be a set, be a bounded function, be a family of functions mapping to and be an approximation parameter. Then there are functions in and scalars , with , such that if we define
we have
To prove Theorem 4 we play the same online game as in the previous section: the online algorithm proposes a solution ; if then we stop and output , otherwise we let the loss function be a function such that either or is in and
The only difference is that we use the FTRL algorithm with L2 regularizer that has the set feasible solutions defined to be the set of all functions rather than the set of all functions . Then each function is the projection to of , and the projection to is just composition with . The bound on the number of steps is the same as the one in the previous section.
Looking at the case in which is the set of edges of a clique on , is the set of graphs of the form , and considering the Sigmaalgebra generated by gives Theorem 3 from Theorem 4.
3. Sampling HighEntropy Distributions
Finally we discuss the application to sampling highentropy distributions.
Suppose that is a distribution over of minentropy , meaning that for every we have
where we think of the entropy deficiency as being small, such as a constant or
Let be a class of functions that we think of as being “efficient.” For example, could be the set of all functions computable by circuits of size for some size bound , such as, for example . We will assume that is in . Define
to be a bounded function . Fix an approximation parameter .
Then from Theorem 4 we have that there are functions , and scalars , all equal to for a certain parameter , such that if we define
Now define the probability distribution
Applying (1) to the case , we have
and we know that , so
and we can rewrite (2) as
and, finally
that is
which says that and are indistinguishable by functions in . If we chose , for example, to be the class of functions computable by circuits of size , then and are indistinguishable by circuits of size .
But is also samplable in a relatively efficient way using rejection sampling: pick a random , then output with probability and fail with probability . Repeat the above until the procedure does not fail. At each step, the probability of success is , so, assuming (because otherwise all of the above makes no sense) that, say, , the procedure succeeds on average in at most attempts. And if each is computable by a circuit of size , then is computable by a circuit of size .
The undesirable features of this result are that the complexity of sampling and the quality of indistinguishability depend exponentially on the randomness deficiency, and the sampling circuit is a nonuniform circuit that it’s not clear how to construct without advice. Impagliazzo’s recent results address both these issues.
by luca at May 16, 2019 07:37 PM UTC
We all get too many alerts. I just assume many of the emails I send to faculty never get read or remembered. I get many requests to mention conferences, workshop and other theory happenings on this blog because nobody knows how to get the word out through the clutter. If we followed through on all these requests, this blog would become clutter itself.
Back in 2009, Nikhil Devanur and I wrote a paper trying to capture this phenomenon using complexity. Building on Levin's notion of universal search, the unawareness of a string x in an environment E is the amount of time needed to generate x from a context c given an oracle for E. Levin showed that one can have a universal algorithm, only a constant time slower to generate x than any other algorithm. One should think of E as the sum total of all our knowledge including search engines on the Internet. Technically we should have used the term "attention" instead of "awareness".
One example is using a calendar as part of your environment, E, that reminds you of an event, x, on that date, c. We use calendars, contact lists, emails searches and many other ways to keep strings we need to remember. Advertisers try to alter your E to get the unawareness of x down.
One of these papers that didn't go far because we didn't have great applications for the definition. But it follows a good philosophy, when life seems complex, model it.
by Lance Fortnow (noreply@blogger.com) at May 16, 2019 12:46 PM UTC

El poema de los números primos (). Exhibit of the mathematicallyinspired artworks of Esther Ferrer, at Tabakalera in San Sebastián, Spain.

How combinatorics became legitimate (). Igor Pak recommends two interesting video interviews with László Lovász and Endre Szemerédi. The whole interviews are quite long but they’re broken into 10minute clips and Igor has picked out the ones relevant to the title.

Magic angles and superconductivity in twisted graphene (). If you twist two sheets of hexagonally tiled carbon relative to each other you can get a superconductor, but only for certain very specific twist angles.

Matthew Butterick says no to ligatures in programming fonts (, via). I tend to agree. They make some things cuter but more things inconsistent. The lack of a short double back arrow in the Fira example is telling. And anyone who expects to see individual characters has to know what font they’re displayed in and how it mangles them to understand what they’re reading. But if you like these for your own text editing, whatever. Just show me the ASCII when I have to view it in my browser.

Breaking the Bellman–Ford shortestpath bound (). Amr Elmasry claims a time bound of for singlesource shortest paths in graphs that may have cycles and negative edge weights, but no negative cycles. If correct, this would be a big improvement over the time for Bellman–Ford. However, I got stuck somewhere around Lemma 3 when trying to understand it. Anyone else have better progress?

Some actual data on how the subject’s gender influences biography creation and deletion on Wikipedia (). Stillexisting older articles on women are more likely to have gone through a deletion discussion than men, but we don’t know whether more were nominated or equally many nominated but women survived better, and whether the inequality of nominations has lessened recently or the greater nomination rate for women takes longer to kick in and is still prevalent.

The graphs behind Reuleaux polyhedra (), by Luis Montejano, Eric Pauli, Miguel Raggi, and Edgardo RoldánPensado. These shapes are the intersections of equalradius balls centered at their vertices; smoothing some edges gives them constant width. Their vertices are the finite point sets with the most diameters. Their vertexedge graphs are selfdual, unlike other polyhedral graphs. And their vertexdiameter graphs are 4colorable. Examples include pyramids over odd polygons.

It’s not like it’s difficult to make your own out of, you know, paper, but if you want a colorful kit to teach yourself about the Miuraori and three other folds, this one looks pretty if a little overpriced at $20 for eight sheets of paper ().

Tensor products of graphs can require fewer colors than their factors (). This short new preprint by Yaroslav Shitov gives counterexamples to Hedetniemi’s conjecture from 1966. In a new blog post Gil Kalai explains the construction.

Algorithms and natural history (). In a new blog, Laurent Feuilloley writes about some algorithmic problems on polyhedra coming from the measurement of skulls, diamond cutting, and the use of symmetry to undo deformations of fossils.

Did you know that Swiss mathematician Alice Roth invented Swiss cheese? (). A Swiss cheese is a disk with smaller disks removed, leaving no interior. Scientific American alerted me to this amusing terminology but I got a clearer idea what they’re good for from an exercise using them to show complex conjugation to be wellbehaved on a compact domain but hard to approximate by rational functions.

China is now blocking all language editions of Wikipedia (, via), expanding its previous block which applied only to the Mandarin edition.
Of course their internet blockage is hardly the biggest problem with China these days. I was surprised to find that some of my usuallywellinformed friends hadn’t even heard of “the largest mass incarceration of the 21st century” and “precursors to genocide”, China’s concentration camps for up to a million Uighur people. So read and learn.

Hazel Perfect (). A new Wikipedia article on the inventor of gammoids (how I came across her name this time) and Christian LawsonPerfect’s mathematical hero (despite or because of the unexplained similarity of names).

In a recent poll, “56% of Americans said Arabic numerals should not be taught in American schools” ().
by David Eppstein at May 15, 2019 10:00 PM UTC
We invite applications for a postdoc position hosted by HsinHao Su at Boston College. Areas of specific interests include but not limited to distributed graph algorithms, local algorithms, dynamic graph algorithms, gossip algorithms, and massive parallel computation algorithms. The starting date is flexible between Fall 2019 and Spring 2020. The position is for a period of up to two years.
Website: https://sites.google.com/site/distributedhsinhao/postdoc
Email: suhx@bc.edu
by shacharlovett at May 15, 2019 07:23 PM UTC
Ever since I “upgraded” this website to use SSL, it’s become completely inaccessible once every three months, because the SSL certificate expires. Several years in, I’ve been unable to find any way to prevent this from happening, and Bluehost technical support was unable to suggest any solution. The fundamental problem is that, as long as the site remains up, the Bluehost control panel tells me that there’s nothing to do, since there is a current certificate. Meanwhile, though, I start getting menacing emails saying that my SSL certificate is about to expire and “you must take action to secure the site”—never, of course, specifying what action to take. The only thing to do seems to be to wait for the whole site to go down, then frantically take random certificaterelated actions until somehow the site goes back up. Those actions vary each time and are not repeatable.
Does anyone know a simple solution to this ridiculous problem?
(The deeper problem, of course, is that a PhD in theoretical computer science left me utterly unqualified for the job of webmaster. And webmasters, as it turns out, need to do a lot just to prevent anything from changing. And since childhood, I’ve been accustomed to countless tasks that are trivial for most people being difficult for me—if that ever stopped being the case, I’d no longer feel like myself.)
by Scott at May 15, 2019 02:56 AM UTC
An inappropriate comment on the ABC conjecture
Joseph Oesterlé and David Masser are famous for their independent discovery of the ABC conjecture.
Today I want to point out an unfair comment about their discovery.
Anonymity on the Internet was captured by a famous 1993 cartoon in the New Yorker magazine titled, “On the Internet, nobody knows you’re a dog.” Amazing to think that was more than a quartercentury ago and remains true. But people can tell if what you’ve written is something inappropriate.
The Comment
The comment is:
SAYS WHO??? I have some trouble with this item.
Masser is a Fellow of the Royal Society, who was elected in 2005. He is
also responsible, following an earlier insight of Joseph Oesterlé, for formulating the abc conjecture; this is a simple statement about integers which seems to hold the key to much of the future direction of number theory.
See this link for his full citation and the comment. Click on the show more bibliography button there. The comment is apparently anonymous, although the author is probably known to some. I thank Joël Ouaknine for pointing out this strange comment.
Update: Ken speculates that it’s a misplaced comment by an editor of the Royal Society website itself. Perhaps they compose HTML from MS Word or Acrobat or other software that provides comment bubbles—but this one escaped the bubble and wasn’t noticed. Editors of Wikipedia have automatic tools for flagging assertions that are unsupported or at least need citation.
What the comment undoubtedly shows is vigorous debate behind the walls of Britain’s august institution. So let’s say a little more on what the comment is about.
The ABC Conjecture
The biggest mysteries about numbers often concern the interaction between addition and multiplication. For example:
 The twin prime conjecture: There are an infinite number of primes such that is also prime. This is due to Alphonse de Polignac.
 The Goldbach conjecture: Every even number greater than four is the sum of two odd primes. This is due to Christian Goldbach.
 The Brocard conjecture: There are only a finite number of solutions to in natural numbers. This is due to Henri Brocard.
Suppose that where are positive and coprime natural numbers. Let be the product of all the distinct prime divisors of . Then the ABC conjecture says that
Note, this inequality does indeed connect adding with multiplying. The usual conjecture is stronger, see this for details.
The ABC conjecture appears to be open, even though Shinichi Mochizuki has claimed a proof for years. See this for a discussion about the status of the conjecture.
Despite multiple conferences dedicated to explicating Mochizuki’s proof, number theorists have struggled to come to grips with its underlying ideas. His series of papers, which total more than 500 pages, are written in an impenetrable style, and refer back to a further 500 pages or so of previous work by Mochizuki, creating what one mathematician, Brian Conrad of Stanford University, has called “a sense of infinite regress.”
The Comment II
The comment on Masser’s work is wrong, strange, inappropriate. Oesterlé and Masser deserve more credit, not less, for their brilliant discovery of the ABC conjecture. There are now many—perhaps hundreds—of applications of the ABC conjecture. For example consider generalizations of Fermat’s Last Theorem. Suppose that
where are odd primes. And . Provided are positive and coprime, it follows by the ABC conjecture that is bounded by . This is impossible for large enough since . Therefore, (*) can only have a finite number of solutions. Pretty neat.
Open Problems
Do you know of any other inappropriate comments of this kind?
[added remark by Ken, linked rather than embed dog cartoon]
[Added prime r must be 7 or larger. Thanks to comment by MadHatter.]
by rjlipton at May 14, 2019 02:49 PM UTC
a) GN was an upper bound on a problem in Ramsey theory. There are now better upper bounds, see here. These better upper bounds are still large HalesJewittLarge, but that's already much smaller than the original GN.
b) Other proofs now have numbers even larger than GN. For example Harvey Friedman's work on the finite versions of Kruskal's Tree Theorem. (There may be other cases if you know some then let me know in the comments.)
Since my dept recently moved buildings I found old papers that I had not looked at in years. One of them was
Old and New Problems and Results in Combinatorial Number Theory
by Erdos and Graham
(see here)
So I began reading it and came across a result of Graham from 1964 that used large numbers. No where near as large as GN, but I found it interesting that Graham was involved with large numbers way back then.
Here is the problem:
A Lucas Sequence is a sequence that obeys
a(n) = a(n1) + a(n2).
Clearly such a sequence is determined by a(0) and a(1).
QUESTION: Does there exists a(0) and a(1) that are rel prime such that the sequence has only composite numbers?
By ingenuity and some computing power Graham found YES. For how the got the numbers see here. The numbers are of course in the paper, and how they got them is interesting, but I present them anyway. Hope I don't make a typo:
a(0) = 1786772701928802632268715130455793
a(1) = 1059683225053915111058164141686995
The paper Old and New... says its open if there is a smaller pair of numbers, I do not know if it is still open. If you know, let us all know in the comments!
These numbers seem small today since we have modern computers that can store and manipulate them easily. Were the considered large numbers in 1964? They were never called Graham Numbers which is probably just as well since that honor lay ahead.
by GASARCH (noreply@blogger.com) at May 13, 2019 04:39 AM UTC
On Friday, 3 May, ICETCS hosted its 15th annual Theory Day. The event consisted of two 45minute presentations by Ravi Boppana (Department of Mathematics, MIT) and Exequiel Rivas(Inria Paris  Rocquencourt, France), and three tenminute presentations by ICETCS researchers highlighting some of the recent research directions pursued by members of the centre.
Ravi Boppana kicked off the Theory Day with a wonderfully paced talk on his work with Ron Holzman on Tomaszewski’s problem on randomly signed sums. The problem is as follows. Let v1, v2, ..., vn be real numbers whose squares add up to 1. Consider the 2n signed sums of the form S=∑±vi. Can there be more signed sums whose value is greater than 1 then those whose value is at most 1? Holzman and Kleitman (1992) proved that at least 3/8 of these sums satisfy S≤1. In his talk, Ravi showed us the main ideas Holzman and he used to improve the bound to 13/32.
Computational effects model the interaction of computer programs with their environment. In his talk, Exequiel Rivastaught us how monadscan be used to capture computational effects (a research programme that started with Moggi's awardwinning work), and then, discussed some attempts to incorporate merging operations in the monadic picture.
Two of the short talks were given by Henning A. Úlfarsson and Elli Anastasiadi. Henning described the work of his group on a tool, called the CombSpecSearcher, that automates the methods used by combinatorialists to prove some of their theorems, The tool is able to prove results featured in dozens of research papers. Watch this space for updates on its development and for its successes!
Elli Anastasiadi, a PhD student who is already playing an important role for the centre, gave a clear sevenminute introduction to finegrained complexity and to the notion of finegrained reduction.
The 2019 Theory Day was well attended, at least by the standards of a TCS event in Iceland. If all goes well, we'll be back next year.
by Luca Aceto (noreply@blogger.com) at May 12, 2019 10:37 PM UTC