Theory of Computing Blog Aggregator

A short summary: The beautiful decade-old conjectures on random sorting networks by  Omer Angel, Alexander Holroyd, Dan Romik, and Bálint Virág, have now been settled by Duncan Dauvergne and Bálint Virág in two papers: Circular support in random sorting networks, by Dauvergne and Virág, and The Archimedean limit of random sorting networks by Duncan Dauvergne.


Dan Romik, see also Romik’s mathematical gallery and Romik’s moving sofa page

Sorting networks

Sorting is one of the most important algorithmic tasks and it is closely related to much beautiful mathematics. In this post, a sorting network is a shortest path from 12…n to n…21 in the Cayley graph of S_n generated by nearest-neighbour swaps. In other words, a sorting networks is a sequence of {{n} \choose {2}} transpositions of the form (i,i+1) whose product is the permutation (n,n-1,\dots,1).

Sorting networks, as we just defined,  appear in other contexts and under other names. Also  the term “sorting networks” is sometimes used in a different way, and in particular, allows swaps that are not nearest neighbors. (See the slides for Uri Zwick’s lecture on sorting networks.)

Richard Stanley proved a remarkable formula

{{n}\choose{2}}!/1^n3^{n-1}5^{n-2}\cdots (2n-3)^1,

for the number of sorting networks or reduced decomposition of the permutation n…21.  (We mentioned it in this post. )

We can also think about sorting networks as  maximal chains in the weak Bruhat order of the symmetric group.  Another related notion in combinatorial geometry is that of  “(simple) allowable sequence of permutations”. an allowable sequence of permutation is a sequence of permutations \pi_1,\pi_2,\pi_t starting with  12…n and ending with n…21 such that each permotation in the sequence is obtained by the previous one by reverseing one set or several disjoint sets of consecutive elements. See, e.g., this paper of Hagit last on two proofs of the Sylvester-Gallai theorem via allowable sequence of permutations.

Random Sorting networks

Alexander Holroyd’s videotaped lecture on random sorting networks. Holroyd’s random sorting gallery (pictures below are taken from there), and his six other amazing mathematical gallerys

Random sorting networks were considered a decade ago in a beautiful paper by Angel, Holroyd, Romik, and Virág . In this paper some brave conjectures were made

Conjecture 1: the trajectories of individual particles converge to random sine curves,

Conjecture 2:  the permutation matrix at half-time converges to the projected surface measure of the 2-sphere.

There are more conjectures! I will just show you one additional picture

The rhombic tiling corresponding to a uniform random sorting network:

The works by Dauvergne and Virág

In two recent breakthrough papers all those conjectures were proved. The papers are

  1. Circular support in random sorting networks, by Dauvergne and Virag

…in which they show the tight support bound for the circle seen in the halfway permutation, as well as the tight Lipschitz bound for trajectories.

2. The Archimedean limit of random sorting networks, by Dauvergne.

…in which all the 2007 conjectures are proved. Here is the abstract:

A sorting network (also known as a reduced decomposition of the reverse permutation), is a shortest path from 12⋯n to n⋯21 in the Cayley graph of the symmetric group Sn generated by adjacent transpositions. We prove that in a uniform random n-element sorting network \sigma^n, that all particle trajectories are close to sine curves with high probability. We also find the weak limit of the time-t permutation matrix measures of \sigma^n. As a corollary of these results, we show that if S_n is embedded into \mathbb R^n via the map τ↦(τ(1),τ(2),…τ(n)), then with high probability, the path σn is close to a great circle on a particular (n−2)-dimensional sphere in \mathbb R^n. These results prove conjectures of Angel, Holroyd, Romik, and Virag.

These papers build on previous results, including some in the 2007 paper, recent results by Gorin and Rahman from Random sorting networks: local statistics via random matrix laws, as well as those of Angel, Dauvergne, Holroyd and Virág from their paper on the local limit of random sorting networks.

The halving (pseudo)lines problem

Let me mention an important conjecture on sorting networks,

Conjecture: For every k, and \epsilon >0 the number of appearances of the transposition (k,k+1) in every sorting network is O(n^{1+\epsilon}).

This is closely related to the halving line problem. The best lower bound (Klawe, Paterson, and Pippenger) behaves like n \exp (\sqrt {\log n}). A geometric construction giving this bound  is a famous theorem by Geza Toth.   The best known upper bound by Tamal Dey is n^{4/3}.

I am amazed that I did not blog about the halving lines problem and about allowable sequences of permutations in the past. (I only briefly mentioned the problem and allowable sequences of permutations in one earlier post on a certain beautiful geometric discrepancy problem.)

The permutahedron makes an appearance


The permutahedron is the Cayley graph of the symmetric group Sn generated by the nearest-neighbour swaps (12)(23)(34) and (n-1n). (Here n=5.) Are there analogous phenomena for the associahedron? one can ask.

by Gil Kalai at May 20, 2018 05:33 PM UTC

Should we expect simplicity in a theory named for complexity?

Amer. Phy. Soc. interview source

Sabine Hossenfelder is a physicist at the Frankfurt Institute for Advanced Studies who works on quantum gravity. She is also noted for her BackRe(Action) blog. She has a forthcoming book Lost in Math: How Beauty Leads Physics Astray. Its thesis is that the quest for beauty and simplicity in physics has led to untestable theories and diverted attention from concrete engagements with reality.

Today we wonder whether her ideas can be tested, at least by analogy, in computational complexity.

Her book is slated to appear on June 12. We have not seen an advance copy but the book grew from her past commentaries including this from 2016, this in Nature in 2017, and this last week. The criticism of string theory goes back even before the book and blog Not Even Wrong by Peter Woit of Columbia and the book The Trouble With Physics by Lee Smolin emerged in 2006. We are not trying to join that debate but rather to engage with the general thesis she stated here:

Do we actually have evidence that elegance is a good guide to the laws of nature?

She continues: “The brief answer is no, we have no evidence. … Beautiful ideas sometimes work, sometimes they don’t. It’s just that many physicists prefer to recall the beautiful ideas which did work.” For an example, supersymmetry is beautiful but has gone far toward a definite “doesn’t work” verdict.

In theoretical computing and mathematics we both remember and preserve beautiful ideas that work. But as bloggers looking to the future as she does, we address ideas that have not yet emerged from shells, to help judge which ones to try hatching. Algorithms and complexity have feet planted not just in Platonic reality but in the empirical fact of programs giving correct answers within the time and other constraints we say they will. Hence we have a testbed for how often a-priori beautiful ideas have proved effective and vice-versa.

Physics and Complexity

Certainly the burst of particle physics in the early-mid 20th Century came with unanticipated complexity. We mention one well-known anecdote that, to judge from her index, is not among those in her book: Isidor Rabi won the 1944 Nobel Prize for his discovery of nuclear magnetic resonance, which he used not to treat sports injuries but to discern the magnetic moment and nuclear spin of atoms. When the muon was discovered but appeared to play no role in nuclear interactions, he famously reacted by exclaiming,

Who ordered that?

Muons are ingrained in the physics Standard Model which has much beauty but also has “bolted-on” aspects that those seeking greater beauty seek to supersede. The model is incomplete with regard to gravity and neutrino masses and leaves issues about dark energy and the matter/antimatter imbalance unaddressed.

William of Ockham’s “Razor” is most often quoted as “Entities should not be multiplied beyond what is necessary” in Latin words by John Punch from the early 1600s. Estimating where the bar of “necessary” is set is still an issue. Anselm Blumer, Andrzej Ehrenfeucht, David Haussler, and Manfred Warmuth in 1987 connected Ockham’s Razor to the complexity of learning, and this was further sharpened by Ming Li, Paul Vitanyi, and John Tromp. Further connections via Kolmogorov complexity and algorithmic probability lead to arguments summarized in a nice survey by Li and Vitanyi with Walter Kirchherr. They quote John von Neumann,

The justification (of a model) is solely and precisely that it is expected to work. … Furthermore, it must satisfy certain aesthetic criteria—that is, in relation to how much it describes, it must be simple.

and continue in their own words:

Of course there are problems with this. Why should a scientist be governed by ‘aesthetic’ criteria? What is meant by ‘simple’? Isn’t such a concept hopelessly subjective?

The answer they seek is that simpler theories have higher probability of having been actuated. This may apply well in large-scale environments such as machine learning and “fieldwork” in biological sciences, in testable ways. Whether it applies on the one scale of one theory for one universe is another matter.

At least we can say that complexity theory proposes grounds for judgment in the physics debate. Hossenfelder seems aware of this, to go by a snippet on page 90 that was highlighted by an early reviewer of her book:

Computational complexity is in principle quantifiable for any theory which can be converted into computer code. We are not computers, however, and therefore computational complexity is not a measure we actually use. The human idea of simplicity is very much based on ease of applicability, which is closely tied to our ability to grasp an idea, hold it in mind, and push it around until a paper falls out.

It hence strikes us as all the more important to reflect on what complexity is like as a theory.

Complexity and the Three Families

We have three main natural families of complexity classes: {\mathsf{DTIME}[t(n)]} and {\mathsf{NTIME}[t(n)]} and {\mathsf{DSPACE}[s(n)]}. Up to polynomial equivalence these stand apart and form a short ladder with rungs {s(n) = O(1)}, then {s(n) = O(\log n)} and {t(n) = 2^{O(s(n))} = n^{O(1)}}, then {s(n) = n^{O(1)}} and {t(n) = \exp(n^{O(1)})}, and finally {s(n) = \exp(n^{O(1)})} which is exemplified among natural computational problems by the computation of Gröbner bases and the equivalence of regular expressions with squaring.

Complexity theory’s first remarkable discovery is that almost all of the many thousands of much-studied computational problems are quantized into the completeness levels of these classes. The reductions involved are often much finer than their defining criterion of being poly-time or log-space computable. Without question the reductions and quantization into three families are beautiful. Requoting Rabi now:

Who ordered them?

The families intertwine:

\displaystyle {\mathsf{DSPACE}[O(\log n)] \subseteq \mathsf{P} \subseteq \mathsf{NP} \subseteq \mathsf{PSPACE} \subseteq \mathsf{EXP} \subseteq \mathsf{NEXP} \subseteq \mathsf{EXPSPACE}.}

The problems they quantize are similarly ordered by reductions. Thus we can extend Rabi with a pun:

Who totally ordered them?

Yet whether these classes are all distinct has escaped proof. The belief they are distinct is founded not on elegance but on myriad person-years of trying to solve these problems.

Stronger separation conjectures such as Unique Games and (S)ETH, however, seem to be hailed as much for explanatory power as for solid evidence. As a cautionary coda to how we have blogged about both, we note that the former’s bounds were shaved in exactly the range of exponential time bounds that the latter hypotheses rely on for their force.

What is also like the situation in physics is a disconnect between (i) how complexity theory is usually defined via asymptotic time and space measures and (ii) concrete real-world feasibility of algorithms, aspects of which we have flagged. This also infects the reliance on unproven assumptions in crypto, which has been remarked by many and may be unavoidable. In crypto, at least, there is vast experience with attempts to break the conditionally-secure systems, a check we don’t see how to have with published algorithms.

Bolder Conjectures

Rather than shrink from the physics analogy, we want to test it by going even further with conjectures and comparing their ramifications for theory-building. Here is the first:

Every “reasonable” complexity class is equal to a member of one of the three main families.

Note that some of the big surprises in complexity theory went in the direction of this conjecture. The result that {\mathsf{IP}=\mathsf{PSPACE}} is a perfect example. Also the closure under complement of space shows we only need {\mathsf{DSPACE}[s(n)]} and do not need its nondeterministic counterpart. Short of specifying exactly which of the several hundred classes in the complexity “Zoo” are “reasonable,” we note that many of its classes {\mathcal{C}} are reasonable and such that the equality of {\mathcal{C}} to one of the basic time or space classes would be a huge result. For {\mathcal{C}} like linear time or space or like {2^{O(n)}} exponential time that are not polynomially closed we still get equality to a basic time {t(n)} or space {s(n)} class.

Our second conjecture might be called “superreducibility”:

For every two “natural” computational problems {A} and {B}, either {A \leq_T^p B} or {B \leq_T^p A}.

This is roughly entailed by the first conjecture since the three families are totally ordered. It may be viable for finer reductions that collapse complements such as polynomial-time one-query reducibility. It is however false without the “natural” qualifier: whenever {A \leq_T^p B} but {B} does not reduce back to {A}, there are infinitely many pairwise-incomparable languages between {A} and {B}. We wonder whether one can formulate an opposite of the “gappiness” property used to prove this theorem in order to make the second conjecture more formal.

Combined time-space classes {\mathsf{TISP}[t(n),s(n)]} for different {t(n),s(n)} pairs may furnish exceptions to both conjectures, but how natural? Eric Allender noted to us that {\mathsf{TimeAlternations(exp,poly)}} has the first-order theory of the reals with addition as a natural complete problem, as shown by Leonard Berman. It fits between {\mathsf{NEXP}} and {\mathsf{EXPSPACE}} but equality to either would surprise. It preserves the total order conjecture, however. Closer to home are “intermediate” problems within {\mathsf{NP}} or in the realm of {\mathsf{BQP}} or {\mathsf{SZK}} or others. We surveyed work by Eric and others that gives some of these problems greater relatability under randomized Turing reductions but less likelihood of hardness. Notwithstanding these issues, we feel it will take a stronger principle to deflate the guidance value of these conjectures.

If we had a choice in building complexity theory, would we build it like this? Should we invest effort to simplify the theory? Is there a model that improves on the Turing machine? Are there theories within computational complexity for which lack of beauty inhibits their development? For one example, Dick and I started a theory of “progressivealgorithms but ran into uglefactions.

Kolmogorov Complexity as an Example

The clearest example for our thoughts about theory-building may be Kolmogorov complexity (KC) itself. It is the most direct effort to quantify information. If there is any place where we should expect a simple theory with unique concrete answers and radiant beauty, this is it.

Much as we love and apply the subject, we do not get that tingling feeling. First, the metric by which it is quantified—a universal Turing machine (UTM)—is an arbitrary choice. Any UTM {U} has equal footing in the theory as it stands. The difference made by choice of {U} is just an additive shift related to the size of {U} and the theory is invariant under such shifts. But if you want to know about concrete KC there are strenuous efforts to make.

Second, there are multiple basic definitions, starting with whether the set of code strings needs to be prefix-free. No clear winner has emerged from the original competing proposals.

Third, the metric is uncomputable. Proposals for approximating it by feasible KC notions have only multiplied the entities further. One can base them on automata that have computable decision properties but then there are as many notions as automata models. I (Ken) mentioned here a conversation last year among several principals in this line of work that did not radiate satisfaction about concreteness.

Fourth, these issues complicate the notation. Is it {K(x)} or {C(x)} or {KC(x)}—or {Kt(x)} or {K^t(x)} or {KT(x)}—conditioned by default or not on {n = |x|} and the like, and are we dropping or keeping additive constants and (log-)logs?

We note a new paper on making the KC theory more “empirical” that may help clean things up. But in the meantime, we cannot deny its importance and success. Our point is that the above marks of ugliness are a brute fact of reality, and any attempt at a more beautiful theory of strings would fly in the face of them.

Open Problems

In what ways might the quest for beauty and simplicity in complexity theory be necessarily compromised? What do you think of our conjectures: like them? refute them?

by RJLipton+KWRegan at May 20, 2018 02:34 AM UTC

I’ve put up a new paper.  Unusually for me these days, it’s a very short and simple one (8 pages)—I should do more like this!  Here’s the abstract:

    We show that combining two different hypothetical enhancements to quantum computation—namely, quantum advice and non-collapsing measurements—would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.

I welcome discussion in the comments.  The real purpose of this post is simply to fulfill a request by James Gallagher, in the comments of my Robin Hanson post:

The probably last chance for humanity involves science progressing, can you apply your efforts to quantum computers, which is your expertise, and stop wasting many hours of you [sic] time with this [expletive deleted]

Indeed, I just returned to Tel Aviv, for the very tail end of my sabbatical, from a weeklong visit to Google’s quantum computing group in LA.  While we mourned tragedies—multiple members of the quantum computing community lost loved ones in recent weeks—it was great to be among so many friends, and great to talk and think for once about actual progress that’s happening in the world, as opposed to people saying mean things on Twitter.  Skipping over its plans to build a 49-qubit chip, Google is now going straight for 72 qubits.  And we now have some viable things that one can do, or try to do, with such a chip, beyond simply proving quantum supremacy—I’ll say more about that in subsequent posts.

Anyway, besides discussing this progress, the other highlight of my trip was going from LA to Santa Barbara on the back of Google physicist Sergio Boixo’s motorcycle—weaving in and out of rush-hour traffic, the tightness of my grip the only thing preventing me from flying out onto the freeway.  I’m glad to have tried it once, and probably won’t be repeating it.

by Scott at May 19, 2018 12:45 PM UTC

We show that a very simple pseudorandom generator fools intersections of $k$ linear threshold functions (LTFs) and arbitrary functions of $k$ LTFs over $n$-dimensional Gaussian space. The two analyses of our PRG (for intersections versus arbitrary functions of LTFs) are quite different from each other and from previous analyses of PRGs for functions of halfspaces. Our analysis for arbitrary functions of LTFs establishes bounds on the Wasserstein distance between Gaussian random vectors with similar covariance matrices, and combines these bounds with a conversion from Wasserstein distance to "union-of-orthants'' distance from [CST14]. Our analysis for intersections of LTFs uses extensions of the classical Sudakov-Fernique type inequalities, which give bounds on the difference between the expectations of the maxima of two Gaussian random vectors with similar covariance matrices. For all values of $k$, our generator has seed length $O(\log n) + poly(k)$ for arbitrary functions of $k$ LTFs and $O(\log n) + poly(\log k)$ for intersections of $k$ LTFs. The best previous result, due to [GOWZ10], only gave such PRGs for arbitrary functions of $k$ LTFs when $k=O(\log \log n)$ and for intersections of $k$ LTFs when $k=O({\frac {\log n}{\log \log n}})$. Thus our PRG achieves an $O(\log n)$ seed length for values of $k$ that are exponentially larger than previous work could achieve. By combining our PRG over Gaussian space with an invariance principle for arbitrary functions of LTFs and with a regularity lemma, we obtain a deterministic algorithm that approximately counts satisfying assignments of arbitrary functions of $k$ general LTFs over $\{0,1\}^n$ in time $poly(n) \cdot 2^{poly(k,1/\eps)}$ for all values of $k$. This algorithm has a $poly(n)$ runtime for $k =(\log n)^c$ for some absolute constant $c>0$, while the previous best $poly(n)$-time algorithms could only handle $k = O(\log \log n)$.

at May 19, 2018 12:17 PM UTC

We show that combining two different hypothetical enhancements to quantum computation---namely, quantum advice and non-collapsing measurements---would let a quantum computer solve any decision problem whatsoever in polynomial time, even though neither enhancement yields extravagant power by itself. This complements a related result due to Raz. The proof uses locally decodable codes.

at May 19, 2018 01:08 AM UTC

All the legal maneuvers, the decades of recriminations, came down in the end to two ambiguous syllables.  No one knew why old man Memeson had named his two kids “Laurel” and “Yanny,” or why his late wife had gone along with it.  Not Laura, not Lauren, but Laurel—like, the leaves that the complacent rest on?  Poor girl.  And yet she lucked out compared to her younger brother. “Yanny”? Rhymes with fanny, seriously?  If you got picked on in school half as much as Yanny did, you too might grow up angry enough to spend half your life locked in an inheritance fight.

But people mostly tolerated the old man’s eccentricities, because he clearly knew something. All through the 1930s, Memeson Audio was building the highest-end radios and record players that money could buy.  And long after he’d outdone the competition, Memeson continued to outdo himself. At the 1939 New York World’s Fair, he proudly unveiled a prototype of his finest record player yet, the one he’d been tinkering with in his personal workshop for a decade: the Unmistakable.  Interviewed about it later, people who attended the demo swore that you couldn’t mishear a single syllable that came out of the thing if you were 99% deaf. No one had ever heard a machine like it—or would, perhaps, until the advent of digital audio.  On Internet forums, audiophiles still debate how exactly Memeson managed to do it with the technology of the time.  Alas, just like the other Memeson debate—about which more shortly—this one might continue indefinitely, since only one Unmistakable was ever built, and that World’s Fair was the last time anyone heard it.

The day after the triumphant demonstration, a crowd cheered as Memeson boarded a train in Grand Central Station to return to his factory near Chicago, there to supervise the mass production of Unmistakables. Meanwhile Laurel and Yanny, now both in their thirties and helping to run the family firm, stood on the platform and beamed. It hadn’t been easy to grow up with such a singleminded father, one who seemed to love his radios a million times more than them, but at a moment like this, it almost felt worth it.  When Laurel and Yanny returned to the Fair to continue overseeing the Memeson Audio exhibition, they’d be the highest-ranking representatives of the company, and would bask in their old man’s reflected glory.

In biographies, Memeson is described as a pathological recluse, who’d hole himself up in his workshop for days at a time, with strict orders not to be disturbed by anyone.  But on this one occasion—as it turned out, the last time he’d ever be seen in public—Memeson was as hammy as could be.  As the train pulled out of Grand Central, he leaned out of an open window in his private car and grinned for the cameras, waving with one arm and holding up the Unmistakable with the other.

Every schoolchild knows what happened next: the train derailed an hour later.  Along with twenty other passengers, Memeson was killed, while all that remained of his Unmistakable was a mess of wires and splintered wood.

Famously, there was one last exchange. As the train began moving, a journalist waved his hat at Memeson and called out “safe travels, sir!”

Memeson smiled and tipped his hat.

Then, noticing Laurel and Yanny on the platform, the journalist yelled to Memeson, in jest (or so he thought): “if something happens, which of these two is next in line to run the business?”

The old man had never been known for his sense of humor, and seemed from his facial expression (or so witnesses would later say) to treat the question with utmost seriousness. As the train receded into the distance, he shouted—well, everyone agrees that it was two syllables. But which? With no written will to consult—one of Memeson’s many idiosyncrasies was his defiance of legal advice—it all came down to what people heard, or believed, or believed they heard.

On the one hand, it would of course be extremely unusual back then for a woman to lead a major technology firm. And Memeson had never shown the slightest interest in social causes: not women’s suffrage, not the New Deal, nothing. In court, Yanny’s lawyers would press these points, arguing that the old man couldn’t possibly have intended to pass on his empire to a daughter.

On the other hand, Laurel was his first-born child.  And some people said that, if Memeson had ever had a human connection with anyone, it was with her.  There were even employees who swore that, once in a while, Laurel was seen entering and leaving her dad’s workshop—a privilege the old man never extended to Yanny or anyone else. Years later, Laurel would go so far as to claim that, during these visits, she’d contributed crucial ideas to the design of the Unmistakable. Most commentators dismiss this claim as bluster: why would she wait to drop such a bombshell until she and Yanny had severed their last ties, until both siblings’ only passion in life was to destroy the other, to make the world unable to hear the other’s name?

At any rate, neither Laurel nor anyone else was ever able to build another Unmistakable, or to give a comprehensible account of how it worked.  But Laurel certainly has die-hard defenders to this day—and while I’ve tried to be evenhanded in this account, I confess to being one of them.

In the end, who people believed about this affair seemed to come down to where they stood—literally. Among the passengers in the train cars adjoining Memeson’s, the ones who heard him are generally adamant that they heard “Laurel”; while most who stood on the platform are equally insistent about “Yanny.”  Today, some Memeson scholars theorize that this discrepancy is due to a Doppler effect.  People on the platform would’ve heard a lower pitch than people comoving with Memeson, and modern reconstructions raise the possibility, however farfetched, that this alone could “morph” one name to the other.  If we accept this, then it suggests that Memeson himself would have intended “Laurel”—but pitch changing a word?  Really?

Today, Laurel and Yanny are both gone, like their father and his company, but their dispute is carried on by their children and grandchildren, with several claims still winding their way through the courts.

Are there any recordings from the platform?  There is one, which was lost for generations before it unexpectedly turned up again. Alas, any hopes that this recording would definitively resolve the matter were … well, just listen to the thing.  Maybe the audio quality isn’t good enough.  Maybe an Unmistakable recording, had it existed, would’ve revealed the observer-independent truth, given us a unique map from the sensory world to the world of meaning.

by Scott at May 18, 2018 12:47 PM UTC

Authors: Bernhard Haeupler, Nicolas Resch
Download: PDF
Abstract: Classically, coding theory has been concerned with the problem of transmitting a single message in a format which is robust to noise. Recently, researchers have turned their attention to designing coding schemes to make two-way conversations robust to noise. That is, given an interactive communication protocol $\Pi$, an \emph{interactive coding scheme} converts $\Pi$ into another communication protocol $\Pi'$ such that, even if errors are introduced during the execution of $\Pi'$, the parties are able to determine what the outcome of running $\Pi$ would be in a noise-free setting.

We consider the problem of designing interactive coding schemes which allow the parties to simulate the original protocol using little memory. Specifically, given any communication protocol $\Pi$ we construct robust simulating protocols which tolerate a constant noise rate and require the parties to use only $O(\log d \log s)$ memory, where $d$ is the depth of $\Pi$ and $s$ is a measure of the size of $\Pi$. Prior to this work, all known coding schemes required the parties to use at least $\Omega(d)$ memory, as the parties were required to remember the transcript of the conversation thus far. Moreover, our coding scheme achieves a communication rate of $1-O(\sqrt{\varepsilon})$ over oblivious channels and $1-O(\sqrt{\varepsilon\log\log\tfrac{1}{\varepsilon}})$ over adaptive adversarial channels, matching the conjecturally optimal rates. Lastly, we point to connections between fault-tolerant circuits and coding for interactive communication with small memory.

at May 18, 2018 12:42 AM UTC

Authors: Benjamin Paaßen
Download: PDF
Abstract: Almost 30 years ago, Zhang and Shasha published a seminal paper describing an efficient dynamic programming algorithm computing the tree edit distance, that is, the minimum number of node deletions, insertions, and replacements that are necessary to transform one tree into another. Since then, the tree edit distance has had widespread applications, for example in bioinformatics and intelligent tutoring systems. However, the original paper of Zhang and Shasha can be challenging to read for newcomers and it does not describe how to efficiently infer the optimal edit script.

In this contribution, we provide a comprehensive tutorial to the tree edit distance algorithm of Zhang and Shasha. We further prove metric properties of the tree edit distance, and describe efficient algorithms to infer the cheapest edit script, as well as a summary of all cheapest edit scripts between two trees.

at May 18, 2018 12:42 AM UTC

Authors: Jessica Enright, Kitty Meeks, George B. Mertzios, Viktor Zamaraev
Download: PDF
Abstract: A variety of potentially disease-spreading contact networks can be naturally modeled with graphs whose structure is subject to discrete changes over time, i.e. with temporal graphs. In such a temporal graph, vertices represent meaningful entities (such as animals or farms) and edges represent potentially infectious contacts between those entities. Furthermore the `availability' of an edge $e$ at time $t$ means that, at time $t$, the entities at the endpoints of $e$ are in contact. In this paper, motivated by network epidemiology applications in the dynamics of disease spreading on a data-derived network, we study the problem of deleting edges and/or edge availabilities from a given temporal graph in order to reduce its (temporal) connectivity. In particular, our aim is to find a temporal subgraph, in which the potential disease of any vertex $u$ can be transferred to only a limited number of other vertices $v$ using a temporal path (i.e. a path from $u$ to $v$, along which the times of the edge availabilities increase). We introduce two natural deletion problems for temporal graphs (for deletion of edges and of edge availabilities, respectively) and we provide positive and negative results on their computational complexity, both in the traditional and the parameterized sense, subject to various natural parameters.

at May 18, 2018 12:00 AM UTC

Authors: Lavinia Egidi, Felipe A. Louza, Giovanni Manzini, Guilherme P. Telles
Download: PDF
Abstract: We propose an external memory algorithm for the computation of the BWT and LCP array for a collection of sequences. Our algorithm takes the amount of available memory as an input parameter, and tries to make the best use of it by splitting the input collection into subcollections sufficiently small that it can compute their BWT in RAM using an optimal linear time algorithm. Next, it merges the partial BWTs in external memory and in the process it also computes the LCP values. We prove that our algorithm performs O(n AveLcp) sequential I/Os, where n is the total length of the collection, and AveLcp is the average Longest Common Prefix of the collection. This bound is an improvement over the known algorithms for the same task. The experimental results show that our algorithm outperforms the current best algorithm for collections of sequences with different lengths and for collections with relatively small average Longest Common Prefix.

In the second part of the paper, we show that our algorithm can be modified to output two additional arrays that, used with the BWT and LCP arrays, provide simple, scan based, external memory algorithms for three well known problems in bioinformatics: the computation of maximal repeats, the all pairs suffix-prefix overlaps, and the construction of succinct de Bruijn graphs. To our knowledge, there are no other known external memory algorithms for these problems.

at May 18, 2018 12:44 AM UTC

Authors: Petra Mutzel, Lutz Oettershagen
Download: PDF
Abstract: The Harary-Hill Conjecture states that for $n\geq 3$ every drawing of $K_n$ has at least \begin{align*} H(n) := \frac{1}{4}\Big\lfloor\frac{n}{2}\Big\rfloor\Big\lfloor\frac{n-1}{2}\Big\rfloor\Big\lfloor\frac{n-2}{2}\Big\rfloor\Big\lfloor\frac{n-3}{2}\Big\rfloor \end{align*} crossings. In general the problem remains unsolved, however there has been some success in proving the conjecture for restricted classes of drawings. The most recent and most general of these classes is seq-shellability. In this work, we improve these results and introduce the new class of single-pair-seq-shellable drawings. We prove the Harary-Hill Conjecture for this new class using novel results on triple cumulated $k$-edges. So far, all approaches for proving the Harary-Hill Conjecture for specific classes rely on a globally fixed reference face. We successfully apply new techniques in order to loosen this restriction, which enables us to select different reference faces when considering subdrawings. Furthermore, we introduce the notion of $k$-deviations as the difference between an optimal and the actual number of $k$-edges. Using $k$-deviations, we gain interesting insights into the essence of $k$-edges, and we further relax the necessity of a fixed reference face.

at May 18, 2018 12:46 AM UTC

Authors: Júlio Araújo, Victor A. Campos, Carlos Vinícius G. C. Lima, Vinícius Fernandes dos Santos, Ignasi Sau, Ana Silva
Download: PDF
Abstract: Given a graph $G$, a proper $k$-coloring of $G$ is a partition $c = (S_i)_{i\in [1,k]}$ of $V(G)$ into $k$ stable sets $S_1,\ldots, S_{k}$. Given a weight function $w: V(G) \to \mathbb{R}^+$, the weight of a color $S_i$ is defined as $w(i) = \max_{v \in S_i} w(v)$ and the weight of a coloring $c$ as $w(c) = \sum_{i=1}^{k}w(i)$. Guan and Zhu [Inf. Process. Lett., 1997] defined the weighted chromatic number of a pair $(G,w)$, denoted by $\sigma(G,w)$, as the minimum weight of a proper coloring of $G$. The problem of determining $\sigma(G,w)$ has received considerable attention during the last years, and has been proved to be notoriously hard: for instance, it is NP-hard on split graphs, unsolvable on $n$-vertex trees in time $n^{o(\log n)}$ unless the ETH fails, and W[1]-hard on forests parameterized by the size of a largest tree. In this article we provide some positive results for the problem, by considering its so-called dual parameterization: given a vertex-weighted graph $(G,w)$ and an integer $k$, the question is whether $\sigma(G,w) \leq \sum_{v \in V(G)} w(v) - k$. We prove that this problem is FPT by providing an algorithm running in time $9^k \cdot n^{O(1)}$, and it is easy to see that no algorithm in time $2^{o(k)} \cdot n^{O(1)}$ exists under the ETH. On the other hand, we present a kernel with at most $(2^{k-1}+1) (k-1)$ vertices, and we rule out the existence of polynomial kernels unless ${\sf NP} \subseteq {\sf coNP} / {\sf poly}$, even on split graphs with only two different weights. Finally, we identify some classes of graphs on which the problem admits a polynomial kernel, in particular interval graphs and subclasses of split graphs, and in the latter case we present lower bounds on the degrees of the polynomials.

at May 18, 2018 12:00 AM UTC

Authors: V. Arvind, Partha Mukhopadhyay, Abhranil Chatterjee, Rajit Datta
Download: PDF
Abstract: Let $C$ be a depth-3 arithmetic circuit of size at most $s$, computing a polynomial $ f \in \mathbb{F}[x_1,\ldots, x_n] $ (where $\mathbb{F}$ = $\mathbb{Q}$ or $\mathbb{C}$) and the fan-in of the product gates of $C$ is bounded by $d$. We give a deterministic polynomial identity testing algorithm to check whether $f\equiv 0$ or not in time $ 2^d \text{ poly}(n,s) $.

at May 18, 2018 12:41 AM UTC

As I mentioned before, I am teaching CS 121  at Harvard, and have written my own text, with the (not very original) title “Introduction to Theoretical Computer Science” . I am hoping for this text to turn into a published textbook in the next year or two. Toward this end, I would be grateful for any comments or suggestions on the text, as I will be working on it over the summer.

You can use the issues page on the GitHub repository to make any suggestions, corrections,  reports on bugs and typos, and so on.

I also hope that others instructors would consider using this text in their courses, and would welcome suggestions as to what I can do to help in that. In particular, over the summer I plan to add more exercises (including some solved ones) and more examples, as well as more explanations and “proof ideas” for many of the theorems.

The main differences between this text and “classical approaches” to intro theory courses such as Sipser’s are the following:

Circuits / straightline programs  as the basic model instead of automata

I do not start with finite automata as the basic computational model, but rather with straight-line programs (or, equivalently Boolean circuits) in an extremely simple programming language which I call the “NAND programming language” since its only operation is assigning to one variable the NAND of two others.

Automata are discussed later in the course, after Turing machines and undecidability, as an example for a restricted computational model where problems such as halting are effectively solvable. This actually corresponds to the historical ordering: Boolean algebra goes back to Boole’s work in the 1850’s, Turing machines and undecidability were of course discovered in the 1930’s, while finite automata were introduced in the 1943 work of McCulloch and Pitts but only really understood in the seminal 1959 work of Rabin and Scott. More importantly, the main current practical motivations for restricted models such as regular and context free languages (whether it is for parsing, for analyzing liveness and safety, or even for routing on software defined networks) are precisely because these are tractable models in which semantic questions can be effectively answered. This motivation can be better appreciated after students see the undecidability of semantic properties of general computing models.

Moreover, the Boolean circuit / straightline programs model is extremely simple to both describe and analyze, and some of the main lessons of the theory of computation, including the notions of the duality between code and data, and the idea of universality, can already be seen in this context. Nonuniform computation also gives essential background for some exciting topics I like to cover later in the course. For example, cryptography (making sense of notions such as “256 bits of security” or difficulty of bitcoin mining), pseudorandom generators and the conjecture that BPP=P, and quantum computing. Circuits of course also yield the simplest proof of the Cook Levin theorem.

A programming language instead of Turing machines for modeling uniform computation

Instead of Turing Machines,  I introduce uniform computation using an equivalent model obtained by extending the straightline NAND programming language mentioned above to include loops and arrays (I call the resulting programming language “NAND++”). I do define Turing machines and show the equivalence to NAND++ program, so the students can connect this both to the historical context as well to other literature they may encounter.

I believe that the programming language formalism makes this model more concrete and familiar to the students than Turing machines. For examples, a result such as the equivalence of Turing machines with two dimensional tapes and one dimensional tapes is now described as showing that a language with two dimensional arrays can be “transpiled” into a language with one dimensional arrays only (i.e., two dimensional arrays can be implemented via “syntactic sugar”).

Moreover, because the NAND++ programming language is extremely simple and fully specified,  it is easy to show its formal equivalence with TM’s. In fact,  since NAND++ is essentially obtained by adding a “feedback loop” to Boolean circuits, this makes the Cook Levin theorem easier to prove. I even implemented the Cook Levin reduction in a Python notebook, and so students can see how one can transform a NAND++ program  P into a graph G and a number k such that G has a cut of size k if and only if the program had an input that makes it output 1. Alas, these graphs tend to be quite large:




I also introduce yet another extension of NAND++ that allows indirect access to arrays, and hence is essentially equivalent to the standard RAM machine model used (implicitly) in algorithms courses. (I call this language NAND<<.) Using a RAM based model makes the distinction between notions such as O(n) and O(n^2) time more meaningful, and makes the time complexity classes correspond to the informal definitions of linear and quadratic time that students encountered in their algorithms lectures (or their whiteboard coding interviews..).

More advanced topics

Reducing the time dedicated to automata (and eliminating context free languages, though I do touch on them in the text in an optional section) allows to spend more time on topics  such randomness and computation, the interactions between proofs and programs (including Gödel’s incompleteness, interactive proof systems, and even a bit on the \lambda-calculus and the Curry-Howard correspondence), cryptography, and quantum computing.

The book is still work in progress, but I think is already quite usable as a textbook. Indeed, much of the feedback I got on the course was that people were happy with the text (though perhaps they merely preferred it to the lectures due to my teaching abilities 🙂 ). One student even got me this coffee mug:



In any case, I hope to get more comments as I work on it over the summer. Regardless of whether or not it’s eventually published as a book, I intend to keep a version of it freely available online.


by Boaz Barak at May 17, 2018 06:55 PM UTC

Focusing on property testing tasks that have query complexity that is independent of the size of the tested object (i.e., depends on the proximity parameter only), we prove the existence of a rich hierarchy of the corresponding complexity classes. That is, for essentially any function $q:(0,1]\to\N$, we prove the existence of properties for which $\epsilon$-testing has query complexity $\Theta(q(\Theta(\epsilon)))$. Such results are proved in three standard domains that are often considered in property testing: generic functions, adjacency predicates describing (dense) graphs, and incidence functions describing bounded-degree graphs. These results complement hierarchy theorems of Goldreich, Krivelevich, Newman, and Rozenberg (Computational Complexity, 2012), which refer to the dependence of the query complexity on the size of the tested object, and focus on the case that the proximity parameter is set to some small positive constant. We actually combine both flavors and get tight results on the query complexity of testing when allowing the query complexity to depend on both the size of the object and the proximity parameter.

at May 17, 2018 08:22 AM UTC

The next TCS+ talk will take place this coming Wednesday, May 23rd at 1:00 PM Eastern Time (10:00 AM Pacific Time, 19:00 Central European Time, 18:00 UTC). Leonard Schulman from Caltech will speak about “Explicit Binary Tree Codes with Polylogarithmic Size Alphabet” (abstract below).

Please make sure you reserve a spot for your group to join us live by signing up on the online form. As usual, for more information about the TCS+ online seminar series and the upcoming talks, or to suggest a possible topic or speaker, please see the website.

Abstract: Tree codes are “real time” or “causal” error-correcting codes. They are known to exist but explicit construction has been a longstanding open problem. We report on progress on this problem.

For every constant delta we give an explicit binary tree code with distance delta and alphabet size poly(log n), where n is the depth of the tree. This is the first improvement over a two-decade-old construction that has an exponentially larger alphabet of size poly(n).

As part of the analysis, we prove a bound on the number of positive integer roots a real polynomial can have in terms of its sparsity with respect to the Newton basis–a result of independent interest.

Joint work with Gil Cohen (Princeton) and Bernhard Haeupler (CMU)

by plustcs at May 16, 2018 03:17 PM UTC

PUBLIC SERVICE ANNOUNCEMENT: Early registration for the EC 2018 conference ends on May 17, two days from now. After that, the cost of registration increases by $100 for the conference (or $50 if you’re a student), $25 for the workshops, $25 for the tutorials.

If you’re planning to attend EC but you haven’t registered yet, take a moment to visit the registration site now. It’s quick and easy to register!

by robertkleinberg at May 15, 2018 08:40 PM UTC

We consider the $(\ell_p,\ell_r)$-Grothendieck problem, which seeks to maximize the bilinear form $y^T A x$ for an input matrix $A \in {\mathbb R}^{m \times n}$ over vectors $x,y$ with $\|x\|_p=\|y\|_r=1$. The problem is equivalent to computing the $p \to r^\ast$ operator norm of $A$, where $\ell_{r^*}$ is the dual norm to $\ell_r$. The case $p=r=\infty$ corresponds to the classical Grothendieck problem. Our main result is an algorithm for arbitrary $p,r \ge 2$ with approximation ratio $(1+\epsilon_0)/(\sinh^{-1}(1)\cdot \gamma_{p^\ast} \,\gamma_{r^\ast})$ for some fixed $\epsilon_0 \le 0.00863$. Here $\gamma_t$ denotes the $t$'th norm of the standard Gaussian. Comparing this with Krivine's approximation ratio $(\pi/2)/\sinh^{-1}(1)$ for the original Grothendieck problem, our guarantee is off from the best known hardness factor of $(\gamma_{p^\ast} \gamma_{r^\ast})^{-1}$ for the problem by a factor similar to Krivine's defect (up to the constant $(1+\epsilon_0)$). Our approximation follows by bounding the value of the natural vector relaxation for the problem which is convex when $p,r \ge 2$. We give a generalization of random hyperplane rounding using H\"{o}lder-duals of Gaussian projections rather than taking the sign. We relate the performance of this rounding to certain hypergeometric functions, which prescribe necessary transformations to the vector solution before the rounding is applied. Unlike Krivine's Rounding where the relevant hypergeometric function was $\arcsin$, we have to study a family of hypergeometric functions. The bulk of our technical work then involves methods from complex analysis to gain detailed information about the Taylor series coefficients of the inverses of these hypergeometric functions, which then dictate our approximation factor. Our result also implies improved bounds for ``factorization through $\ell_{2}^{n}$'' of operators from $\ell_{p}^{n}$ to $\ell_{q}^{m}$ (when $p\geq 2 \geq q$) --- such bounds are of significant interest in functional analysis and our work provides modest supplementary evidence for an intriguing parallel between factorizability, and constant-factor approximability.

at May 15, 2018 06:29 PM UTC

Authors: Wei Chen, Shang-Hua Teng, Hanrui Zhang
Download: PDF
Abstract: We introduce two new "degree of complementarity" measures, which we refer to, respectively, as supermodular width and superadditive width. Both are formulated based on natural witnesses of complementarity. We show that both measures are robust by proving that they, respectively, characterize the gap of monotone set functions from being submodular and subadditive. Thus, they define two new hierarchies over monotone set functions, which we will refer to as Supermodular Width (SMW) hierarchy and Superadditive Width (SAW) hierarchy, with level 0 of the hierarchies resting exactly on submodular and subadditive functions, respectively.

We present a comprehensive comparative analysis of the SMW hierarchy and the Supermodular Degree (SD) hierarchy, defined by Feige and Izsak. We prove that the SMW hierarchy is strictly more expressive than the SD hierarchy. We show that previous results regarding approximation guarantees for welfare and constrained maximization as well as regarding the Price of Anarchy (PoA) of simple auctions can be extended without any loss from the SD hierarchy to the SMW hierarchy. We also establish almost matching information-theoretical lower bounds. The combination of these approximation and hardness results illustrate that the SMW hierarchy provides an accurate characterization of "near submodularity" needed for maximization approximation. While SD and SMW hierarchies support nontrivial bounds on the PoA of simple auctions, we show that our SAW hierarchy seems to capture more intrinsic properties needed to realize the efficiency of simple auctions. So far, the SAW hierarchy provides the best dependency for the PoA of Single-bid Auction, and is nearly as competitive as the Maximum over Positive Hypergraphs (MPH) hierarchy for Simultaneous Item First Price Auction (SIA). We provide almost tight lower bounds for the PoA of both auctions with respect to the SAW hierarchy.

at May 14, 2018 06:21 AM UTC

Authors: Mohamed Allaoui, Aurélien Goudjo
Download: PDF
Abstract: A new class of rational parametrization has been developed and it was used to generate a new family of rational functions B-splines $\displaystyle{{\left({}^{\alpha}{\mathbf B}_{i}^{k} \right)}_{i=0}^{k}}$ which depends on an index $\alpha \in (-\infty,0)\cup (1,+\infty)$. This family of functions verifies, among other things, the properties of positivity, of partition of the unit and, for a given degree k, constitutes a true basis approximation of continuous functions. We loose, however, the regularity classical optimal linked to the multiplicity of nodes, which we recover in the asymptotic case, when $\alpha \longrightarrow \infty$. The associated \mbox{B-splines} curves verify the traditional properties particularly that of a convex hull and we see a certain "conjugated symmetry" related to $\alpha$. The case of open knot vectors without an inner node leads to a new family of rational Bezier curves that will be separately, object of in-depth analysis.

at May 14, 2018 12:00 AM UTC

Authors: Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos
Download: PDF
Abstract: We consider the problems of deciding whether an input graph can be modified by removing/adding at most $k$ vertices/edges such that the result of the modification satisfies some property definable in first-order logic. We establish a number of sufficient and necessary conditions on the quantification pattern of the first-order formula $\phi$ for the problem to be fixed-parameter tractable or to admit a polynomial kernel.

at May 14, 2018 12:00 AM UTC

Authors: Hanqing Zhao, Yuehan Luo
Download: PDF
Abstract: We propose an $O(N)$ sorting algorithm based on Machine Learning method, which shows a huge potential for sorting big data. This sorting algorithm can be applied to parallel sorting and is suitable for GPU or TPU acceleration. Furthermore, we apply this algorithm to sparse hash table.

at May 14, 2018 12:00 AM UTC

Authors: Jérémy Barbay, Pablo Pérez-Lantero, Javiel Rojas-Ledesma
Download: PDF
Abstract: We consider the Minimum Coverage Kernel problem: given a set B of $d$-dimensional boxes, find a subset of B of minimum size covering the same region as B. This problem is $\mathsf{NP}$-hard, but as for many $\mathsf{NP}$-hard problems on graphs, the problem becomes solvable in polynomial time under restrictions on the graph induced by $B$. We consider various classes of graphs, show that Minimum Coverage Kernel remains $\mathsf{NP}$-hard even for severely restricted instances, and provide two polynomial time approximation algorithms for this problem.

at May 14, 2018 12:00 AM UTC

Authors: Kelsey Horan, Delaram Kahrobaei
Download: PDF
Abstract: In this paper we discuss the Hidden Subgroup Problem (HSP) in relation to post-quantum group-based cryptography. We review the relationship between HSP and other computational problems discuss an optimal solution method, and review the known results about the quantum complexity of HSP. We also overview some platforms for group-based cryptosystems. Notably, efficient algorithms for solving HSP in such infinite group platforms are not yet known.

at May 14, 2018 12:40 AM UTC

Authors: Keren Censor-Hillel, Bernhard Haeupler, D. Ellis Hershkowitz, Goran Zuzic
Download: PDF
Abstract: The radio network model is a well-studied abstraction for modeling wireless multi-hop networks. However, radio networks make the strong assumption that messages are delivered deterministically. The recently introduced noisy radio network model relaxes this assumption by dropping messages independently at random.

In this work we quantify the relative computational power of noisy radio networks and classic radio networks. In particular, given a protocol for a fixed radio network we show how to reliably simulate this protocol if noise is introduced with a multiplicative cost of $\mathrm{poly}(\log \Delta, \log \log n)$ rounds. For this result we make the simplifying assumption that the simulated protocol is $\textit{static}$. Moreover, we demonstrate that, even if the simulated protocol is not static, it can be simulated with a multiplicative $O(\Delta \log \Delta)$ cost in the number of rounds. Hence, our results show that protocols on constant-degree networks can be made robust to random noise with constant multiplicative overhead. Lastly, we argue that simulations with a multiplicative overhead of $o(\log \Delta)$ are unlikely to exist by proving that an $\Omega(\log \Delta)$ multiplicative round overhead is necessary under certain natural assumptions.

at May 14, 2018 12:00 AM UTC

Authors: J. Ian Munro, Sebastian Wild
Download: PDF
Abstract: We present two stable mergesort variants, "peeksort" and "powersort", that exploit existing runs and find nearly-optimal merging orders with practically negligible overhead. Previous methods either require substantial effort for determining the merging order (Takaoka 2009; Barbay & Navarro 2013) or do not have a constant-factor optimal worst-case guarantee (Peters 2001; Auger, Nicaud & Pivoteau 2015; Buss & Knop 2018). We demonstrate that our methods are competitive in terms of running time with state-of-the-art implementations of stable sorting methods.

at May 14, 2018 12:00 AM UTC

Authors: Venkatesan Guruswami, Andrii Riazanov
Download: PDF
Abstract: We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is a classical problem. It arises in two equivalent contexts: (i) the smallest size possible for a perfect hash family that maps a universe of $N$ elements into $\{1,2,\dots,k\}$, and (ii) the zero-error capacity for decoding with lists of size less than $k$ for a certain combinatorial channel.

A general upper bound of $k!/k^{k-1}$ on the rate of a $k$-hash code (in the limit of large $n$) was obtained by Fredman and Koml\'{o}s in 1984 for any $k \geq 4$. While better bounds have been obtained for $k=4$, their original bound has remained the best known for each $k \ge 5$. In this work, we obtain the first improvement to the Fredman-Koml\'{o}s bound for every $k \ge 5$. While we get explicit (numerical) bounds for $k=5,6$, for larger $k$ we only show that the FK bound can be improved by a positive, but unspecified, amount. Under a conjecture on the optimum value of a certain polynomial optimization problem over the simplex, our methods allow an effective bound to be computed for every $k$.

at May 14, 2018 12:00 AM UTC

Authors: Rico Zenklusen
Download: PDF
Abstract: We present a $1.5$-approximation for the Metric Path Traveling Salesman Problem (path TSP). All recent improvements on the path TSP crucially exploit a structural property shown by An, Kleinberg, and Shmoys [Journal of the ACM, 2015], namely that narrow cuts with respect to a Held-Karp solution form a chain. We significantly deviate from these approaches by showing the benefit to deal with larger $s$-$t$ cuts, even though they are much less structured. More precisely, we show that a variation of the dynamic programming idea recently introduced by Traub and Vygen [SODA, 2018] is versatile enough to deal with larger size cuts, by exploiting a seminal result of Karger on the number of near-minimum cuts. This avoids a recursive application of dynamic programming as used by Traub and Vygen, and leads to a considerable simpler algorithm avoiding an additional error term in the approximation guarantee. Because we match the still unbeaten $1.5$-approximation guarantee of Christofides' algorithm for TSP, any further progress on the approximability of the path TSP will also lead to an improvement for TSP.

at May 14, 2018 12:00 AM UTC

We say a subset $C \subseteq \{1,2,\dots,k\}^n$ is a $k$-hash code (also called $k$-separated) if for every subset of $k$ codewords from $C$, there exists a coordinate where all these codewords have distinct values. Understanding the largest possible rate (in bits), defined as $(\log_2 |C|)/n$, of a $k$-hash code is a classical problem. It arises in two equivalent contexts: (i) the smallest size possible for a perfect hash family that maps a universe of $N$ elements into $\{1,2,\dots,k\}$, and (ii) the zero-error capacity for decoding with lists of size less than $k$ for a certain combinatorial channel. A general upper bound of $k!/k^{k-1}$ on the rate of a $k$-hash code (in the limit of large $n$) was obtained by Fredman and Komlós in 1984 for any $k \geq 4$. While better bounds have been obtained for $k=4$, their original bound has remained the best known for each $k \ge 5$. In this work, we obtain the first improvement to the Fredman-Komlós bound for every $k \ge 5$. While we get explicit (numerical) bounds for $k=5,6$, for larger $k$ we only show that the FK bound can be improved by a positive, but unspecified, amount. Under a conjecture on the optimum value of a certain polynomial optimization problem over the simplex, our methods allow an effective bound to be computed for every $k$.

at May 12, 2018 09:39 PM UTC

We show that proving mildly super-linear lower bounds on non-commutative arithmetic circuits implies exponential lower bounds on non-commutative circuits. That is, non-commutative circuit complexity is a threshold phenomenon: an apparently weak lower bound actually suffices to show the strongest lower bounds we could desire. This is part of a recent line of inquiry into why arithmetic circuit complexity, despite being a heavily restricted version of Boolean complexity, still cannot prove super-linear lower bounds on general devices. One can view our work as positive news (it suffices to prove weak lower bounds to get strong ones) or negative news (it is as hard to prove weak lower bounds as it is to prove strong ones). We leave it to the reader to determine their own level of optimism.

at May 11, 2018 06:20 PM UTC

We introduce a new model for testing graph properties which we call the \emph{rejection sampling model}. We show that testing bipartiteness of $n$-nodes graphs using rejection sampling queries requires complexity $\widetilde{\Omega}(n^2)$. Via reductions from the rejection sampling model, we give three new lower bounds for tolerant testing of Boolean functions of the form $f\colon\{0,1\}^n\to \{0,1\}$: \begin{itemize} \item Tolerant $k$-junta testing with \emph{non-adaptive} queries requires $\widetilde{\Omega}(k^2)$ queries. \item Tolerant unateness testing requires $\widetilde{\Omega}(n)$ queries. \item Tolerant unateness testing with \emph{non-adaptive} queries requires $\widetilde{\Omega}(n^{3/2})$ queries. \end{itemize} Given the $\widetilde{O}(k^{3/2})$-query non-adaptive junta tester of Blais \cite{B08}, we conclude that non-adaptive tolerant junta testing requires more queries than non-tolerant junta testing. In addition, given the $\widetilde{O}(n^{3/4})$-query unateness tester of Chen, Waingarten, and Xie \cite{CWX17b} and the $\widetilde{O}(n)$-query non-adaptive unateness tester of Baleshzar, Chakrabarty, Pallavoor, Raskhodnikova, and Seshadhri \cite{BCPRS17}, we conclude that tolerant unateness testing requires more queries than non-tolerant unateness testing, in both adaptive and non-adaptive settings. These lower bounds provide the first separation between tolerant and non-tolerant testing for a natural property of Boolean functions.

at May 11, 2018 04:58 PM UTC

This 'sweet and sour' news is already some time overdue. You might already know how a typical geographical distribution of ERC grants looks like. The next figure shows to which countries Consolidator grants went in 2017.

This distribution is usually typical for Poland, i.e., apx. 1 grant is given. This in general is rather 'sour' news. Still a 'sweet' information is that this was yet another grant in algorithms that went to our group in Warsaw. Hence, we currently have 3 ERC grants running:
- Marcin Pilipczuk got ERC Starting Grant CUTACOMBS - Cuts and decompositions: algorithms and combinatorial properties,
- Marek Cygan got ERC Starting Grant TOTAL - Technology transfer between modern algorithmic paradigms,
- I, myself, got ERC Consolidator Grant TUGboAT - Towards Unification of Algorithmic Tools.

In other words, there are some interesting project happening right in Warsaw, and if you would like to visit us, just let us know.

by sank at May 11, 2018 01:00 PM UTC

Authors: Yi-Jun Chang
Download: PDF
Abstract: Energy efficiency is a critical issue for wireless devices operated under stringent power constraint. Following prior works, we measure the energy cost of a device by its transceiver usage, and the energy complexity of an algorithm is defined as the maximum number of time slots a device transmits or listens, over all devices. In a recent paper of Chang et al. (PODC 2018), it was shown that broadcasting in a multi-hop network of unknown topology can be done in $\text{poly} \log n$ energy. In this paper, we continue this line of research, and investigate the energy complexity of other fundamental graph problems in multi-hop networks. Our results are summarized as follows.

1. To avoid spending $\Omega(D)$ energy, the broadcasting protocols of Chang et al. (PODC 2018) do not send the message along a BFS tree, and it is open whether BFS could be computed in $o(D)$ energy, for sufficiently large $D$. In this paper we devise an algorithm that attains $\tilde{O}(\sqrt{n})$ energy cost.

2. We show that the framework of the ${\Omega}(n /\log^2 n)$ round lower bound proof for computing diameter in CONGEST of Abboud et al.~(DISC 2017) can be adapted to give an $\tilde{\Omega}(n / \log^3 n)$ energy lower bound in the wireless network model (with no message size constraint), and this lower bound applies to $O(\log n)$-arboricity graphs. From the upper bound side, we show that the energy complexity of $\tilde{O}(\sqrt{n})$ can be attained for bounded-genus graphs (which includes planar graphs).

3. Our upper bounds for computing diameter can be extended to other graph problems. We show that exact global minimum cut or approximate $s$--$t$ minimum cut can be computed in $\tilde{O}(\sqrt{n})$ energy for bounded-genus graphs.

at May 11, 2018 12:00 AM UTC

Authors: Jean Cardinal, Erik D. Demaine, David Eppstein, Robert A. Hearn, Andrew Winslow
Download: PDF
Abstract: We consider the computational complexity of reconfiguration problems, in which one is given two combinatorial configurations satisfying some constraints, and is asked to transform one into the other using elementary transformations, while satisfying the constraints at all times. Such problems appear naturally in many contexts, such as model checking, motion planning, enumeration and sampling, and recreational mathematics. We provide hardness results for problems in this family, in which the constraints and operations are particularly simple. More precisely, we prove the PSPACE-completeness of the following decision problems:

$\bullet$ Given two satisfying assignments to a planar monotone instance of Not-All-Equal 3-SAT, can one assignment be transformed into the other by single variable `flips' (assignment changes), preserving satisfiability at every step?

$\bullet$ Given two subsets of a set S of integers with the same sum, can one subset be transformed into the other by adding or removing at most three elements of S at a time, such that the intermediate subsets also have the same sum?

$\bullet$ Given two points in $\{0,1\}^n$ contained in a polytope P specified by a constant number of linear inequalities, is there a path in the n-hypercube connecting the two points and contained in P?

These problems can be interpreted as reconfiguration analogues of standard problems in NP. Interestingly, the instances of the NP problems that appear as input to the reconfiguration problems in our reductions can be shown to lie in P. In particular, the elements of S and the coefficients of the inequalities defining P can be restricted to have logarithmic bit-length.

at May 11, 2018 01:23 AM UTC

Authors: Julien Destombes, Andrei Romashchenko
Download: PDF
Abstract: We propose necessary conditions of soficness of multidimensional shifts formulated in terms of resource-bounded Kolmogorov complexity. Using this technique we provide examples of effective and non-sofic shifts on $\mathbb{Z}^2$ with very low block complexity: the number of admissible patterns of size $n\times n$ grows only as a polynomial in $n$.

at May 11, 2018 12:00 AM UTC

Authors: Irit Dinur, Pasin Manurangsi
Download: PDF
Abstract: We study the 2-ary constraint satisfaction problems (2-CSPs), which can be stated as follows: given a constraint graph $G=(V,E)$, an alphabet set $\Sigma$ and, for each $\{u, v\}\in E$, a constraint $C_{uv} \subseteq \Sigma\times\Sigma$, the goal is to find an assignment $\sigma: V \to \Sigma$ that satisfies as many constraints as possible, where a constraint $C_{uv}$ is satisfied if $(\sigma(u),\sigma(v))\in C_{uv}$.

While the approximability of 2-CSPs is quite well understood when $|\Sigma|$ is constant, many problems are still open when $|\Sigma|$ becomes super constant. One such problem is whether it is hard to approximate 2-CSPs to within a polynomial factor of $|\Sigma| |V|$. Bellare et al. (1993) suggested that the answer to this question might be positive. Alas, despite efforts to resolve this conjecture, it remains open to this day.

In this work, we separate $|V|$ and $|\Sigma|$ and ask a related but weaker question: is it hard to approximate 2-CSPs to within a polynomial factor of $|V|$ (while $|\Sigma|$ may be super-polynomial in $|V|$)? Assuming the exponential time hypothesis (ETH), we answer this question positively by showing that no polynomial time algorithm can approximate 2-CSPs to within a factor of $|V|^{1 - o(1)}$. Note that our ratio is almost linear, which is almost optimal as a trivial algorithm gives a $|V|$-approximation for 2-CSPs.

Thanks to a known reduction, our result implies an ETH-hardness of approximating Directed Steiner Network with ratio $k^{1/4 - o(1)}$ where $k$ is the number of demand pairs. The ratio is roughly the square root of the best known ratio achieved by polynomial time algorithms (Chekuri et al., 2011; Feldman et al., 2012).

Additionally, under Gap-ETH, our reduction for 2-CSPs not only rules out polynomial time algorithms, but also FPT algorithms parameterized by $|V|$. Similar statement applies for DSN parameterized by $k$.

at May 11, 2018 12:00 AM UTC

Authors: Jouni Sirén, Erik Garrison, Adam M. Novak, Benedict Paten, Richard Durbin
Download: PDF
Abstract: The variation graph toolkit (VG) represents genetic variation as a graph. Each path in the graph is a potential haplotype, though most paths are unlikely recombinations of true haplotypes. We augment the VG model with haplotype information to identify which paths are more likely to be correct. For this purpose, we develop a scalable implementation of the graph extension of the positional Burrows-Wheeler transform. We demonstrate the scalability of the new implementation by indexing the 1000 Genomes Project haplotypes. We also develop an algorithm for simplifying variation graphs for k-mer indexing without losing any k-mers in the haplotypes.

at May 11, 2018 12:00 AM UTC

Authors: Vladimir Braverman, Petros Drineas, Jalaj Upadhyay, Samson Zhou
Download: PDF
Abstract: We initiate the study of numerical linear algebra in the sliding window model, where only the most recent $W$ updates in the data stream form the underlying set. Much of the previous work in the sliding window model uses one of two frameworks: either the exponential histogram (Datar et al., SICOMP'02) or the smooth histogram (Braverman and Ostrovsky, FOCS'07). We show that some elementary linear algebraic problems, such as the estimation of matrix $\ell_p$ norms, can be addressed in the sliding window model using these frameworks. Specifically, we show that approximating matrix entrywise norms for all $p < \infty$ and Schatten $p$-norms for $p=0,1$, and $2$ (which include the matrix rank, the trace or nuclear norm, and the Frobenius norm) are suitable for the smooth histogram framework.

However, most "interesting" problems are not smooth and specifically, we show that the spectral norm, vector induced matrix norms, generalized regression, low-rank approximation, and leverage scores are not amenable for the smooth histogram framework. To overcome this challenge, we generalize the smooth histogram framework from real-valued functions to matrix-valued functions. We believe that this framework is a natural way to study numerical linear algebra problems in the sliding window model and perhaps beyond.

We then apply our framework to derive approximations for the following linear algebraic functions in the sliding window model: Spectral sparsification, Low-rank approximation, Generalized regression, Graph sparsification (and applications), Matrix multiplication, Row-subset selection. In addition to the results presented in this paper, we hope that our new framework will be useful in developing future randomized numerical linear algebra algorithms.

at May 11, 2018 12:00 AM UTC

Authors: Lin Chen, Lei Xu, Weidong Shi
Download: PDF
Abstract: We consider the 4-block $n$-fold integer programming (IP), in which the constraint matrix consists of $n$ copies of small matrices $A$, $B$, $D$ and one copy of $C$ in a specific block structure. We prove that, the $\ell_{\infty}$-norm of the Graver basis elements of 4-block $n$-fold IP is upper bounded by $O_{FPT}(n^{s_c})$ where $s_c$ is the number of rows of matrix $C$ and $O_{FPT}$ hides a multiplicative factor that is only dependent on the parameters of the small matrices $A,B,C,D$ (i.e., the number of rows and columns, and the largest absolute value among the entries). This improves upon the existing upper bound of $O_{FPT}(n^{2^{s_c}})$. We provide a matching lower bounded of $\Omega(n^{s_c})$, which even holds for an arbitrary non-zero integral element in the kernel space. We then consider a special case of 4-block $n$-fold in which $C$ is a zero matrix (called 3-block $n$-fold IP). We show that, surprisingly, 3-block $n$-fold IP admits a Hilbert basis whose $\ell_{\infty}$-norm is bounded by $O_{FPT}(1)$, despite the fact that the $\ell_{\infty}$-norm of its Graver basis elements is still $\Omega(n)$. Finally, we provide upper bounds on the $\ell_{\infty}$-norm of Graver basis elements for 3-block $n$-fold IP. Based on these upper bounds, we establish algorithms for 3-block $n$-fold IP and provide improved algorithms for 4-block $n$-fold IP.

at May 11, 2018 12:00 AM UTC

Authors: Danny Nguyen, Igor Pak
Download: PDF
Abstract: We prove that the problem of minimizing the number of integer points inparallel translations of a rational convex polytope in $\mathbb{R}^6$ is NP-hard. We apply this result to show that given a rational convex polytope $P \subset \mathbb{R}^6$, finding the largest integer $t$ s.t. the expansion $tP$ contains fewer than $k$ integer points is also NP-hard. We conclude that the Ehrhart quasi-polynomials of rational polytopes can have arbitrary fluctuations.

at May 11, 2018 12:00 AM UTC