Theory of Computing Blog Aggregator


From “readymade” works to surreal hash table wildness in chess programs fooled by him

Toutfait.com source

Marcel Duchamp was a leading French chess player whose career was sandwiched between two forays into the art world. He played for the French national team in five chess Olympiads from 1924 to 1933. He finished tied for fourth place out of fourteen players in the 1932 French championship.

Today we look afresh at some of his coups in art and chess and find some unexpected depth.

We say “unexpected” because Duchamp was famous for art that consisted of common objects tweaked or thrown together. He called them readymades in English while writing in French. An example is his 1917 Fountain, which Dick and Kathryn saw in Philadelphia last weekend:

SFMOMA replica, Wikimedia Commons source

Duchamp first submitted this anonymously to a New York exhibition he was helping to organize. When it was refused, he resigned in protest. He then ascribed it to a person named Richard Mutt. Richard means “rich person” in French while “R. Mutt” suggests Armut which is German for “poverty.” A magazine defended the work by saying that whether Mr. Mutt made the fountain—which came from the J.L. Mott Iron Works—has no importance:

He CHOSE it… [and thus] created a new thought for that object.

The new thought led in 2004 to a poll of 500 art professionals voting Fountain “the most influential artwork of the 20th century.” This was ahead of Guernica, Les Demoiselles d’Avignon, The Persistence of Memory, The Dance, Spiral Jetty, just to name a few works of greater creation effort. It was ahead of everything by Alexander Calder or Andy Warhol or math favorite Maurits Escher for that matter. For Duchamp that was quite a coup—which is also French for a move at chess. Fountain is also a kind of coupe—French for “cup” and also snippet or section.

Readymade Mathematics

Michelangelo Buonarroti famously declared that “every block of stone has a figure inside it and the sculptor’s task is to discover it.” Dick and I feel most of our peers would disagree with this about sculpture but agree with the same remark applied to mathematics. As Platonists we believe our theorems had proofs in “the book” from the start and that our chipping away at problems is what discovers them.

The paradox is that we nevertheless experience theoretical research as being as creative as Michelangelo’s artwork or Duchamp’s original painting, Nude Descending a Staircase. What accounts for this? We have previously alluded to “builders” versus “solvers” and the imperative of creating good definitions. Builders still need to sense where and when proofs are likely to be available.

Finding a new proof idea is reckoned as the height of creativity despite the idea’s prior existence. This is however rare. Most of us do not invent or re-invent wheels but rather ride wheels we’ve mastered. They may be wheels we learned in school, as pre-fab as Duchamp’s 1913 Bicycle Wheel. The creativity may come from learning to deploy the wheels in a new context:

David Gómez (c) “Duchamp a Hamburger Bahnhof” source, license (photo unchanged)

Replicas and Memes

Neither of the works pictured above is the original version. The originals were lost, as were second versions made by Duchamp. Duchamp’s third Bicycle Wheel belongs to MoMA, which is adjacent to Dick and Kathryn’s apartment in Manhattan. The Philadelphia Art Museum has the earliest surviving replica of Fountain, certified by Duchamp as dating to 1950. Duchamp blessed fourteen other replicas in the 1960s.

For contrast, Duchamp spent nine years making the original artwork shown behind the board in this crop of an iconic photo:

Cropped from Vanity Fair source

The nine-foot high construction between glass panes lives in Philadelphia under its English name The Bride Stripped Bare By Her Bachelors, Even. The “even” translates the French même, which is different from mème meaning “meme.” Richard Dawkins coined the latter term in his 1976 book the Selfish Gene. Modern Internet “memes” diverge from Dawkins’s meaning but amplify his book’s emphasis on replication. Both the isolation of concepts and the replication were anticipated by Duchamp.

A wonderful Matrix Barcelona story has the uncropped photo of Duchamp playing the bared Eve Babitz. It also has a film segment with Duchamp and Man Ray which shows how they viewed the world. Duchamp could paint “retinally” as at left below, but this page explains how his vision of the scene shifted a year later. Then his poster for the 1925 French championship abstracts chess itself:

Composite of sources collected here

Duchamp’s Chess

Duchamp’s high-level chess activity stopped before the Second World War broke, but he kept up his interest during it. In 1944-45 he helped organize an exhibition The Visual Imagery of Chess at the Julien Levy gallery in midtown Manhattan. One evening featured a blindfold simultaneous exhibition by the Belgian-American master George Koltanowski:

Composite of src1, src2

This composite photo with leafy allusions shows left-to-right Levy (standing), artist Frederick Kiesler, Duchamp executing a move called out by Koltanowski (facing away), art historian Alfred Barr, Bauhaus artist Xanti Schawinsky, composer Vittorio Rieti, and the married artists Dorothea Tanning and Max Ernst. Plus someone evidently looking for a new game. My “assisted readymade” skirts the edge of fair use (non-commercial) with modification. The works I combined each have higher creation cost than the objects Duchamp used. Yet there’s no restraint on combining other people’s theorems—of whatever creation cost—with attribution.

Koltanowski kept the seven games entirely in his head, winning six and drawing one, and performed similar feats well into his eighties. Yet Duchamp once beat him in a major tournament—in only 15 moves—when Koltanowski was in his prime and looking at the board.

So how strong was Duchamp? It is hard to tell because Arpad Elo did not create the Elo rating system until the 1950s and because the records of many of Duchamp’s games are lost. Twenty of Duchamp’s tournaments are listed in the omnibus Chessbase compilation but only four have all his games, only four more include as many as five games, and most including the 1923 Belgian Cup lack even the results of his other games. For these eight events, my chess model assesses Duchamp’s “Intrinsic Performance Ratings” (IPRs) as follows:


The error bars are big but the readings are consistent enough to conclude that Duchamp reached the 2000–2100 range but fell short of today’s 2200 Master rank.

My IPRs for historical players have been criticized as too low because today’s players benefit from greater knowledge of the opening, middlegame dynamics, and endgames. My model does not compensate for this—it credits moves that go from brain to board not caring whether preparing with computers at home put them in the brain. However, a comparison with Koltanowski is particularly apt because Elo himself estimated Koltanowski at 2450 based on his play in 1932–1937. My IPR from every available Koltanowski game in those years is 2485 +- 95. When limited to the major—and complete—tournaments that would have most informed Elo’s estimate, it is 2520 +- 100. The latter does much to suggest that Koltanowski might have merited back then the grandmaster title, which he was awarded honoris causa in 1988. Koltanowski had 2380 +- 165 in the year 1929, including his loss to Duchamp.

Still, Duchamp’s multiple IPR readings over 2000 earn him the rank of expert, which few attain. Duchamp gave himself a different title in 1952:

I am still a victim of chess. It has all the beauty of art—and much more.

A Readymade Chess Problem

Duchamp loved the endgame but is only known to have composed one problem. Fitting for Valentine’s Day, he embellished it with a hand-drawn cupid:

Composite of diagrams from Arena and Toutfait.com source

Yet unrequited love may be the theme, for there is no solution. Analysis by human masters has long determined the game to be drawn with the confidence of a human mathematical proof. All the critical action can be conveyed in one sequence of moves: 1. Rg7+ Kf2 2. Ke4 h4 3. Kd5 h3 4. Kc6 h2 5. Rh7 Kg2 6. Kc7 Rg8 (or 6…Rf8 or …Re8 or even …Rxb7+ if followed by 7. Kxb7 f5!) 7. b8Q Rxb8 8. Kxb8 h1Q (or 8…f5 first) 9. Rxh1 Kxh1 10. Kc7 f5 11. b6 f4 12. b7 f3 13. b8Q f2 14. Qb1+ Kg2 15. Qe4+ Kg1 16. Qg4+ Kh2 17. Qf3 Kg1 18. Qg3+ Kh1! when 19. Qxf2 is stalemate and no more progress can be made.

The cupid and signature were on one side of the program sheet for an art exhibition titled “Through the Big End of the Opera Glass.” The other side had the board diagram, caption, and mirror-image words saying, “Look through from other side against light.” The upshot arrow was meant as a hint to shoot White’s pawns forward. But by making a mirror image of the position instead, I have found the second of two surprising effects.

The first surprise is that when it comes to verifying the draw with today’s chess programs—which are far stronger than any human player—Duchamp’s position splits them wildly. This is without equipping the programs with endgame tables—just their basic search algorithms.

The Houdini 6 program, which has just begun defending its TCEC championship against a field led by past champions Komodo and Stockfish, takes only 10 seconds on my office machine to reach a “drawn” verdict that it never revises. Here is a coupe of its analysis approaching depth 40 ply, meaning a nominal basic search 20 moves ahead. That’s enough to see the final stalemate, so Houdini instead tries to box Black in, but by move 4 we can already see Black’s king squirting out. Its latent threat to White’s pawns knocks White’s advantage down to 0.27 of a pawn, which is almost nada:

Komodo stays with the critical line but churns up hours of thinking time while keeping an over-optimistic value for it:

The just-released version 9 of Stockfish, however, gyrates past depth 30, seemingly settles down like Houdini, but then suddenly goes—and stays—bananas:

When Komodo is given only 32MB hash, it gyrates even more wildly until seeming to settle on a +3.25 or +3.26 value at depths 31–34. Then at depth 35 it balloons up to +6.99 and swoons. After 24 hours it is still on depth 35 and has emitted only two checked-down values of +6.12 and +4.00 at about the 8 and 16 hour points.

Now for the second surprise. The mirror-image position at right above changes absolutely none of the chess logic. But when we input it to Stockfish 9, with 32MB hash, it gives a serene computation:

What’s going on? The upshot is that the mirrored position’s different squares use a different set of keys in a tabulation hashing scheme. They give a different pattern of hash collisions and hence a different computation.

There are two more mirror positions with Black and White interchanged. One is serene (from depth 20 on) but the other blows up at depths 36–40. This is for Stockfish 9 with 32MB hash and default settings otherwise. With 512MB hash, both blow up. Since both Stockfish 9 and the Arena chess GUI used to take the data are freely downloadable, anyone can reproduce the above and do more experiments.

There is potential high importance because the large-scale behavior of the hash collisions and search may be sensitive to whether the nearly-50,000 bits making up the hash keys are truly random or pseudorandom. I detailed this and a reproducible “digital butterfly effect” in a post some years ago.

Thus unexpected things happen to computers at high depth in Duchamp’s position. It is not in the Chessbase database, but he may have gotten it “readymade” from playing a game or analyzing one. In all cases we can credit the astuteness of his choosing it.

Open Problems

What will be Duchamp’s legacy in the 21st Century? Chess players will keep it growing. Buenos Aires (where he traveled to study chess in 1919), Rio de Janeiro, and Montevideo have organized tournaments in his honor. It was my pleasure to monitor the 2018 Copa Marcel Duchamp which finished last week in Montevideo. This involved getting files of the games from arbiter Sabrina de San Vicente, analyzing them using spare capacity on UB’s Center for Computational Research, and generating ready-made statistical reports for her and the tournament staff to view.


[a few slight fixes and tweaks]

by KWRegan at February 17, 2018 03:55 AM UTC

The only things that matter in a theoretical study are those that you can prove, but it’s always fun to speculate. After worrying about P vs. NP for half my life, and having carefully reviewed the available “evidence” I have decided I believe that P = NP.

A main justification for my belief is history:

  1. In the 1950’s Kolmogorov conjectured that multiplication of n-bit integers requires time \Omega (n^{2}). That’s the time it takes to multiply using the method that mankind has used for at least six millennia. Presumably, if a better method existed it would have been found already. Kolmogorov subsequently started a seminar where he presented again this conjecture. Within one week of the start of the seminar, Karatsuba discovered his famous algorithm running in time O(n^{\log _{2}3})\approx n^{1.58}. He told Kolmogorov about it, who became agitated and terminated the seminar. Karatsuba’s algorithm unleashed a new age of fast algorithms, including the next one. I recommend Karatsuba’s own account [8] of this compelling story.
  2. In 1968 Strassen started working on proving that the standard O(n^{3}) algorithm for multiplying two n\times n matrices is optimal. Next year his landmark O(n^{\log _{2}7})\approx n^{2.81} algorithm appeared in his paper “Gaussian elimination is not optimal” [10].
  3. In the 1970s Valiant showed that the graphs of circuits computing certain linear transformations must be a super-concentrator, a graph which certain strong connectivity properties. He conjectured that super-concentrators must have a super-linear number of wires, from which super-linear circuit lower bounds follow [11]. However, he later disproved the conjectured [12]: building on a result of Pinsker he constructed super-concentrators using a linear number of edges.
  4. At the same time Valiant also defined rigid matrices and showed that an explicit construction of such matrices yields new circuit lower bounds. A specific matrix that was conjectured to be sufficiently rigid is the Hadamard matrix. Alman and Williams recently showed that, in fact, the Hadamard matrix is not rigid [1].
  5. After finite automata, a natural step in lower bounds was to study sightly more general programs with constant memory. Consider a program that only maintains O(1) bits of memory, and reads the input bits in a fixed order, where bits may be read several times. It seems quite obvious that such a program could not compute the majority function in polynomial time. This was explicitly conjectured by several people, including [5]. Barrington [4] famously disproved the conjecture by showing that in fact those seemingly very restricted constant-memory programs are in fact equivalent to log-depth circuits, which can compute majority (and many other things).

And these are just some of the most famous ones. The list goes on and on. In number-on-forehead communication complexity, the function Majority-of-Majorities was a candidate for being hard for more than logarithmically many parties. This was disproved in [3] and subsequent works, where many other counter-intuitive protocols are presented. In data structures, would you think it possible to switch between binary and ternary representation of a number using constant time per digit and zero space overhead? Turns out it is [97]. Do you believe factoring is hard? Then you also believe there are pseudorandom generators where each output bit depends only on O(1) input bits [2]. Known algorithms for directed connectivity use either super-polynomial time or polynomial memory. But if you are given access to polynomial memory full of junk that you can’t delete, then you can solve directed connectivity using only logarithmic (clean) memory and polynomial time [6]. And I haven’t even touched on the many broken conjectures in cryptography, most recently related to obfuscation.

On the other hand, arguably the main thing that’s surprising in the lower bounds we have is that they can be proved at all. The bounds themselves are hardly surprising. Of course, the issue may be that we can prove so few lower bounds that we shouldn’t expect surprises. Some of the undecidability results I do consider surprising, for example Hilbert’s 10th problem. But what is actually surprising in those results are the algorithms, showing that even very restricted models can simulate more complicated ones (same for the theory of NP completeness). In terms of lower bounds they all build on diagonalization, that is, go through every program and flip the answer, which is boring.

The evidence is clear: we have grossly underestimated the reach of efficient computation, in a variety of contexts. All signs indicate that we will continue to see bigger and bigger surprises in upper bounds, and P=NP. Do I really believe the formal inclusion P=NP? Maybe, let me not pick parameters. What I believe is that the idea that lower bounds are obviously true and we just can’t prove them is not only baseless but even clashes with historical evidence. It’s the upper bounds that are missing.

References

[1]   Josh Alman and R. Ryan Williams. Probabilistic rank and matrix rigidity. In Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, STOC 2017, Montreal, QC, Canada, June 19-23, 2017, pages 641–652, 2017.

[2]   Benny Applebaum, Yuval Ishai, and Eyal Kushilevitz. Cryptography in NC^0. SIAM J. on Computing, 36(4):845–888, 2006.

[3]   László Babai, Anna Gál, Peter G. Kimmel, and Satyanarayana V. Lokam. Communication complexity of simultaneous messages. SIAM J. on Computing, 33(1):137–166, 2003.

[4]   David A. Mix Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC^1. J. of Computer and System Sciences, 38(1):150–164, 1989.

[5]   Allan Borodin, Danny Dolev, Faith E. Fich, and Wolfgang J. Paul. Bounds for width two branching programs. In Proceedings of the 15th Annual ACM Symposium on Theory of Computing, 25-27 April, 1983, Boston, Massachusetts, USA, pages 87–93, 1983.

[6]   Harry Buhrman, Richard Cleve, Michal Koucký, Bruno Loff, and Florian Speelman. Computing with a full memory: catalytic space. In ACM Symp. on the Theory of Computing (STOC), pages 857–866, 2014.

[7]   Yevgeniy Dodis, Mihai Pǎtraşcu, and Mikkel Thorup. Changing base without losing space. In 42nd ACM Symp. on the Theory of Computing (STOC), pages 593–602. ACM, 2010.

[8]   A. A. Karatsuba. The complexity of computations. Trudy Mat. Inst. Steklov., 211(Optim. Upr. i Differ. Uravn.):186–202, 1995.

[9]   Mihai Pǎtraşcu. Succincter. In 49th IEEE Symp. on Foundations of Computer Science (FOCS). IEEE, 2008.

[10]   Volker Strassen. Gaussian elimination is not optimal. Numer. Math., 13:354–356, 1969.

[11]   Valiant. On non-linear lower bounds in computational complexity. In ACM Symp. on the Theory of Computing (STOC), pages 45–53, 1975.

[12]   Leslie G. Valiant. Graph-theoretic arguments in low-level complexity. In 6th Symposium on Mathematical Foundations of Computer Science, volume 53 of Lecture Notes in Computer Science, pages 162–176. Springer, 1977.

 

by Emanuele at February 16, 2018 07:54 PM UTC

Private Simultaneous Message (PSM) protocols were introduced by Feige, Kilian and Naor (STOC '94) as a minimal non-interactive model for information-theoretic three-party secure computation. While it is known that every function $f:\{0,1\}^k\times \{0,1\}^k \rightarrow \{0,1\}$ admits a PSM protocol with exponential communication of $2^{k/2}$ (Beimel et al., TCC '14), the best known (non-explicit) lower-bound is $3k-O(1)$ bits. To prove this lower-bound, FKN identified a set of simple requirements, showed that any function that satisfies these requirements is subject to the $3k-O(1)$ lower-bound, and proved that a random function is likely to satisfy the requirements. We revisit the FKN lower-bound and prove the following results: (Counterexample) We construct a function that satisfies the FKN requirements but has a PSM protocol with communication of $2k+O(1)$ bits, revealing a gap in the FKN proof. (PSM lower-bounds) We show that, by imposing additional requirements, the FKN argument can be fixed leading to a $3k-O(\log k)$ lower-bound for a random function. We also get a similar lower-bound for a function that can be computed by a polynomial-size circuit (or even polynomial-time Turing machine under standard complexity-theoretic assumptions). This yields the first non-trivial lower-bound for an explicit Boolean function partially resolving an open problem of Data, Prabhakaran and Prabhakaran (Crypto '14, IEEE Information Theory '16). We further extend these results to the setting of imperfect PSM protocols which may have small correctness or privacy error. (CDS lower-bounds) We show that the original FKN argument applies (as is) to some weak form of PSM protocols which are strongly related to the setting of Conditional Disclosure of Secrets (CDS). This connection yields a simple combinatorial criterion for establishing linear $\Omega(k)$-bit CDS lower-bounds. As a corollary, we settle the complexity of the Inner Product predicate resolving an open problem of Gay, Kerenidis, and Wee (Crypto '15).

at February 16, 2018 08:23 AM UTC

Authors: Andrew Frohmader
Download: PDF
Abstract: This paper presents a simple extension of the binary heap, the List Heap. We use List Heaps to demonstrate the idea of adaptive heaps: heaps whose performance is a function of both the size of the problem instance and the disorder of the problem instance. We focus on the presortedness of the input sequence as a measure of disorder for the problem instance. A number of practical applications that rely on heaps deal with input that is not random. Even random input contains presorted subsequences. Devising heaps that exploit this structure may provide a means for improving practical performance. We present some basic empirical tests to support this claim. Additionally, adaptive heaps may provide an interesting direction for theoretical investigation.

at February 16, 2018 12:00 AM UTC

Authors: Hao-Ting Wei, Wing-Kai Hon, Paul Horn, Chung-Shou Liao, Kunihiko Sadakane
Download: PDF
Abstract: This study considers the (soft) capacitated vertex cover problem in a dynamic setting. This problem generalizes the dynamic model of the vertex cover problem, which has been intensively studied in recent years. Given a dynamically changing vertex-weighted graph $G=(V,E)$, which allows edge insertions and edge deletions, the goal is to design a data structure that maintains an approximate minimum vertex cover while satisfying the capacity constraint of each vertex. That is, when picking a copy of a vertex $v$ in the cover, the number of $v$'s incident edges covered by the copy is up to a given capacity of $v$. We extend Bhattacharya et al.'s work [SODA'15 and ICALP'15] to obtain a deterministic primal-dual algorithm for maintaining a constant-factor approximate minimum capacitated vertex cover with $O(\log n / \epsilon)$ amortized update time, where $n$ is the number of vertices in the graph. The algorithm can be extended to (1) a more general model in which each edge is associated with a nonuniform and unsplittable demand, and (2) the more general capacitated set cover problem.

at February 16, 2018 12:00 AM UTC

Authors: Pierre Aboulker, Marthe Bonamy, Nicolas Bousquet, Louis Esperet
Download: PDF
Abstract: This paper is concerned with efficiently coloring sparse graphs in the distributed setting with as few colors as possible. According to the celebrated Four Color Theorem, planar graphs can be colored with at most 4 colors, and the proof gives a (sequential) quadratic algorithm finding such a coloring. A natural problem is to improve this complexity in the distributed setting. Using the fact that planar graphs contain linearly many vertices of degree at most 6, Goldberg, Plotkin, and Shannon obtained a deterministic distributed algorithm coloring $n$-vertex planar graphs with 7 colors in $O(\log n)$ rounds. Here, we show how to color planar graphs with 6 colors in $\mbox{polylog}(n)$ rounds. Our algorithm indeed works more generally in the list-coloring setting and for sparse graphs (for such graphs we improve by at least one the number of colors resulting from an efficient algorithm of Barenboim and Elkin, at the expense of a slightly worst complexity). Our bounds on the number of colors turn out to be quite sharp in general. Among other results, we show that no distributed algorithm can color every $n$-vertex planar graph with 4 colors in $o(n)$ rounds.

at February 16, 2018 12:00 AM UTC

Authors: Peter Chini, Roland Meyer, Prakash Saivasan
Download: PDF
Abstract: We study the fine-grained complexity of Leader Contributor Reachability (LCR) and Bounded-Stage Reachability (BSR), two variants of the safety verification problem for shared memory concurrent programs. For both problems, the memory is a single variable over a finite data domain. We contribute new verification algorithms and lower bounds based on the Exponential Time Hypothesis (ETH) and kernels.

LCR is the question whether a designated leader thread can reach an unsafe state when interacting with a certain number of equal contributor threads. We suggest two parameterizations: (1) By the size of the data domain D and the size of the leader L, and (2) by the size of the contributors C. We present two algorithms, running in O*((L(D+1))^(LD)*D^D) and O*(4^C) time, showing that both parameterizations are fixed-parameter tractable. Further, we suggest a modification of the first algorithm, suitable for practical instances. The upper bounds are complemented by (matching) lower bounds based on ETH and kernels.

For BSR, we consider programs involving t different threads. We restrict to computations where the write permission changes s times between the threads. BSR asks whether a given configuration is reachable via such an s-stage computation. When parameterized by P, the maximum size of a thread, and t, the interesting observation is that the problem has a large number of difficult instances. Formally, we show that there is no polynomial kernel, no compression algorithm that reduces D or s to a polynomial dependence on P and t. This indicates that symbolic methods may be harder to find for this problem.

at February 16, 2018 12:00 AM UTC

Authors: Ariusz Dereniowski, Dorota Osula, Paweł Rzążewski
Download: PDF
Abstract: A connected path decomposition of a simple graph $G$ is a path decomposition $(X_1,\ldots,X_l)$ such that the subgraph of $G$ induced by $X_1\cup\cdots\cup X_i$ is connected for each $i\in\{1,\ldots,l\}$. The connected pathwidth of $G$ is then the minimum width over all connected path decompositions of $G$. We prove that for each fixed $k$, the connected pathwidth of any input graph can be computed in polynomial-time. This answers an open question raised by Fedor V. Fomin during the GRASTA 2017 workshop, since connected pathwidth is equivalent to the connected (monotone) node search game.

at February 16, 2018 12:00 AM UTC

Authors: Adrià Gascón, Markus Lohrey, Sebastian Maneth, Carl Philipp Reh, Kurt Sieber
Download: PDF
Abstract: We introduce forest straight-line programs (FSLPs) as a compressed representation of unranked ordered node-labelled trees. FSLPs are based on the operations of forest algebra and generalize tree straight-line programs. We compare the succinctness of FSLPs with two other compression schemes for unranked trees: top dags and tree straight-line programs of first-child/next sibling encodings. Efficient translations between these formalisms are provided. Finally, we show that equality of unranked trees in the setting where certain symbols are associative or commutative can be tested in polynomial time. This generalizes previous results for testing isomorphism of compressed unordered ranked trees.

at February 16, 2018 12:00 AM UTC

Authors: Angelo Raffaele Meo
Download: PDF
Abstract: The analysis discussed in this paper is based on a well-known NP-complete problem which is called satisfiability problem or SAT. From SAT a new NP-complete problem is derived, which is described by a Boolean function called core function. In this paper it is proved that the cost of the minimal implementation of core function increases with n exponentially. Since the synthesis of core function is an NP-complete problem, this result is equivalent to proving that P and NP do not coincide.

at February 16, 2018 12:00 AM UTC

Authors: László Kozma, Thatchaphol Saranurak
Download: PDF
Abstract: We present a new connection between self-adjusting binary search trees (BSTs) and heaps, two fundamental, extensively studied, and practically relevant families of data structures. Roughly speaking, we map an arbitrary heap algorithm within a broad and natural model, to a corresponding BST algorithm with the same cost on a dual sequence of operations (i.e. the same sequence with the roles of time and key-space switched). This is the first general transformation between the two families of data structures.

There is a rich theory of dynamic optimality for BSTs (i.e. the theory of competitiveness between BST algorithms). The lack of an analogous theory for heaps has been noted in the literature. Through our connection, we transfer all instance-specific lower bounds known for BSTs to a general model of heaps, initiating a theory of dynamic optimality for heaps.

On the algorithmic side, we obtain a new, simple and efficient heap algorithm, which we call the smooth heap. We show the smooth heap to be the heap-counterpart of Greedy, the BST algorithm with the strongest proven and conjectured properties from the literature, widely believed to be instance-optimal. Assuming the optimality of Greedy, the smooth heap is also optimal within our model of heap algorithms.

Intriguingly, the smooth heap, although derived from a non-practical BST algorithm, is simple and easy to implement (e.g. it stores no auxiliary data besides the keys and tree pointers). It can be seen as a variation on the popular pairing heap data structure, extending it with a "power-of-two-choices" type of heuristic. For the smooth heap we obtain instance-specific upper bounds, with applications in adaptive sorting, and we see it as a promising candidate for the long-standing question of a simpler alternative to Fibonacci heaps.

at February 16, 2018 12:00 AM UTC

Authors: Thodoris Lykouris, Sergei Vassilvitskii
Download: PDF
Abstract: Traditional online algorithms encapsulate decision making under uncertainty, and give ways to hedge against all possible future events, while guaranteeing a nearly optimal solution as compared to an offline optimum. On the other hand, machine learning algorithms are in the business of extrapolating patterns found in the data to predict the future, and usually come with strong guarantees on the expected generalization error.

In this work we develop a framework for augmenting online algorithms with a machine learned oracle to achieve competitive ratios that provably improve upon unconditional worst case lower bounds when the oracle has low error. Our approach treats the oracle as a complete black box, and is not dependent on its inner workings, or the exact distribution of its errors.

We apply this framework to the traditional caching problem -- creating an eviction strategy for a cache of size $k$. We demonstrate that naively following the oracle's recommendations may lead to very poor performance, even when the average error is quite low. Instead we show how to modify the Marker algorithm to take into account the oracle's predictions, and prove that this combined approach achieves a competitive ratio that both (i) decreases as the oracle's error decreases, and (ii) is always capped by $O(\log k)$, which can be achieved without any oracle input. We complement our results with an empirical evaluation of our algorithm on real world datasets, and show that it performs well empirically even using simple off-the-shelf predictions.

at February 16, 2018 12:00 AM UTC

Authors: Vlad-Andrei Munteanu
Download: PDF
Abstract: A directed graph G (V, E) is strongly connected if and only if, for a pair of vertices X and Y from V, there exists a path from X to Y and a path from Y to X. In Computer Science, the partition of a graph in strongly connected components is represented by the partition of all vertices from the graph, so that for any two vertices, X and Y, from the same partition, there exists a path from X to Y and a path from Y to X and for any two vertices, U and V, from different partition, the property is not met. The algorithm presented below is meant to find the partition of a given graph in strongly connected components in O (numberOfNodes + numberOfEdges * log* (numberOfNodes)), where log* function stands for iterated logarithm.

at February 16, 2018 12:00 AM UTC

Authors: Chuan Zhang, Ziyuan Shen, Wei Wei, Jing Zhao, Zaichen Zhang, Xiaohu You Lab of Efficient Architectures for Digital-communication and Signal-processing, Quantum Information Center of Southeast University, National Mobile Communications Research Laboratory, Southeast University, China, State Key Laboratory of Coordination Chemistry, School of Chemistry and Chemical Engineering, Nanjing University, China, State Key Laboratory of Pharmaceutical Biotechnology, School of Life Sciences, Nanjing)
Download: PDF
Abstract: In this paper, it is presented a methodology for implementing arbitrarily constructed time-homogenous Markov chains with biochemical systems. Not only discrete but also continuous-time Markov chains are allowed to be computed. By employing chemical reaction networks (CRNs) as a programmable language, molecular concentrations serve to denote both input and output values. One reaction network is elaborately designed for each chain. The evolution of species' concentrations over time well matches the transient solutions of the target continuous-time Markov chain, while equilibrium concentrations can indicate the steady state probabilities. Additionally, second-order Markov chains are considered for implementation, with bimolecular reactions rather that unary ones. An original scheme is put forward to compile unimolecular systems to DNA strand displacement reactions for the sake of future physical implementations. Deterministic, stochastic and DNA simulations are provided to enhance correctness, validity and feasibility.

at February 16, 2018 02:01 AM UTC

This paper makes progress on the problem of explicitly constructing a binary tree code with constant distance and constant alphabet size. For every constant $\delta < 1$ we give an explicit binary tree code with distance $\delta$ and alphabet size $(\log{n})^{O(1)}$, 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 $n^{O(1)}$. 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.

at February 15, 2018 09:24 PM UTC

Key-agreement protocols whose security is proven in the random oracle model are an important alternative to the more common public-key based key-agreement protocols. In the random oracle model, the parties and the eavesdropper have access to a shared random function (an "oracle"), but they are limited in the number of queries they can make to it. Unfortunately, as shown by Impagliazzo and Rudich [STOC '89] and Barak and Mahmoody [Crypto '09], such protocols can only guarantee limited secrecy: the key of any $\ell$-query protocol can be revealed by an $O(\ell^2)$-query adversary. This quadratic gap between the query complexity of the honest parties and the eavesdropper matches the gap obtained by the Merkle's Puzzles protocol [CACM '78]. In this work we tackle a new aspect of key-agreement protocols in the random oracle model: their communication complexity. In Merkle's Puzzles, to obtain secrecy against an eavesdropper that makes roughly $\ell^2$ queries, the honest parties need to exchange $\Omega(\ell)$ bits. We show that for protocols with certain natural properties, ones that Merkle's Puzzle has, such high communication is unavoidable. Specifically, this is the case if the honest parties' queries are uniformly random, or alternatively if the protocol uses non-adaptive queries and has only two rounds. Our proof for the first setting uses a novel reduction from random-oracle protocols to the set-disjointness problem in two-party communication complexity, which is known to have high communication cost. For the second setting we prove the lower bound directly, using information-theoretic arguments. Understanding the communication complexity of protocols whose security is proven in the random-oracle model is an important question in the study of practical protocols. Our results and proof techniques are a first step in this direction.

at February 15, 2018 05:14 PM UTC

If you haven’t read the important and heart wrenching post by a brave female theoretician about sexual harassment and rape as part of her academic life in our community, please do it now. The word “brave” here is an understatement. Hard for me to imagine the strength that facing these memories again and taking the risk of exposure must have required. I also don’t use “important” lightly as it doesn’t only make the pain that comes with sexual harassment so vivid but also because it demonstrates the cost to our community. We have lost so much of the voice and perspective and creativity of our dear colleague and I know that not only hers. There may be very little that I can say or do about the rape that you experienced. I wish I could hold your hands and cry with you. But I could have done much more to make our community more supportive to all and hostile to none. I therefore not only thank you for the post but also apologize for any inaction, let alone, for any insensitive action I might have been guilty of.

Empowered by the #metoo movement, a group of us (Edith Cohen, Vitaly Feldman, Ronitt Rubinfeld, myself and others) have been discussing in the last few weeks what we can do moving forward. I want to share some of our thoughts (and one additional comment). We would love to hear your thoughts.

  1. In a different context I wrote: “Our collaborators, our audience, our points of reference, are not only the colleagues next door but probably more so our colleagues across the globe.“ In this sense, our community is also our work place and it is very appropriate to view sexual harassment in conferences as creating a hostile work environment. But usually, in our “official” work places we have HR or other representatives that we can contact for support. Who do we contact about sexual harassment in a conference or a visit?
  2. A partial answer is: the chair of the conference or the representative of the academic society that runs the conference or the work place of the offender etc. Indeed, most of these institutions will be obliged to act. See for example ACM’s Code of Ethics and Professional Conduct.
  3. For a victim to act at the face of sexual harassment and against colleagues with influence on the victim’s career is hard enough in regular circumstances. Sending a victim to complain to any of the institutions above seems unrealistic.
  4. We (the aforementioned group) believe that TOC needs its own, widely accepted, code of conduct. This will at the minimum let all of us acknowledge our joint responsibilities (in addition to any relevant legal, ethical or contractual obligations we already have).
  5. We also need a committee of senior individual that can be contacted by victims. Such a committee may not have any legal power but it will have a moral authority to act. In particular, to inform all the relevant entities and to mitigate any threat of retaliation.
  6. Finally, I want to point out a rather old post that seems very relevant to our discussion (even after we take away rape and harassment): on intellectual passion and its unfortunate confusion with sexual passion (and how it may relate to issues of gender).

by Omer Reingold at February 15, 2018 02:18 PM UTC

First of all read the #metoo testimonial going around the TCS blogosphere. Our field is not immune.

Last Sunday Frank Bruni wrote an op-ed column Corporations will Inherit the Earth, an article on how corporations have taken on what governments used to do. Quite a bit is focused on education.
The nimbleness of corporations gives them an edge over hoary, complacent institutions, including those in higher education...In an effort to make sure that employees have up-to-the-minute technical skills--or are simply adept at critical thinking and creative problem solving -- more companies have developed academies of their own. That's likely to accelerate. "I think enterprises like Amazon and Google are going to build universities that teach coding and things the nation needs" said Margaret Spellings, former education secretary and current president of the University of North Carolina system.
Already in the universities we've seen a move towards more majors and minors in STEM and computer science in particular. The changing corporate workplace has already changed academia, putting more an emphasis on technical areas and less on the liberal arts. Will companies though take the next step, running their own schools that focus on the needs of industry? If we see continued decreased government funding for universities and academic research, we may end up with a handful of rich universities and the rest of the population getting education on the job, a future that would be a loss for us all.


by Lance Fortnow (noreply@blogger.com) at February 15, 2018 01:09 PM UTC

In an earlier post I asked if we have TCS “Harvey Weinsteins”. Unfortunately academia is hardly immune from sexual harassment and now a  TCS researcher posted about her experiences with sexual harassment and assault in our community. While this is not pleasant reading, it is important, and I urge you to read the full post (see also here).

It takes courage to talk about such painful experiences, even anonymously, in a community as small as ours. But this researcher deserves our thanks for bringing up this topic, and hopefully starting a conversation that would make theoretical computer science more welcoming and inclusive. I do not know who this person is, but I urge people not try to guess her identity, but rather focus on asking what we can do, both men and women, to make things better.

The blog post already contains some good suggestions. As the overwhelming majority in our field, we men enjoy many structural advantages, and it is especially up to us to step up to this challenge. Research is not a 9 to 5 job: conferences, workshops, and informal interactions are extremely important. But we should remember that we are there for the sake of scientific collaboration. A woman shouldn’t have to worry about the motivations behind every invitation for a discussion or meeting.

Given our skewed gender ratio, it is enough for a small minority of the men to behave badly to essentially guarantee that almost all women will encounter such behavior at some point. That is unless other men step up and call out unprofessional (or worse) behavior when we observe or are made aware of it. I know this is not easy – we are not selected for our ability to handle awkward social situations, and I can’t say I myself have  stepped up or been very aware of such issues in the past. But I will try to do better, and hope others do too.

by Boaz Barak at February 15, 2018 02:10 AM UTC

Authors: Phillip G. Bradford
Download: PDF
Abstract: The exact path length problem is to determine if there is a path of a given fixed cost between two vertices. This paper focuses on the exact path problem for costs $-1,0$ or $+1$ between all pairs of vertices in an edge-weighted digraph. The edge weights are from $\{ -1, +1 \}$. In this case, this paper gives an $\widetilde{O}(n^{\omega})$ exact path solution. Here $\omega$ is the best exponent for matrix multiplication and $\widetilde{O}$ is the asymptotic upper-bound mod polylog factors.

Variations of this algorithm determine which pairs of digraph nodes have Dyck or semi-Dyck labeled paths between them, assuming two parenthesis. Therefore, determining digraph reachability for Dyck or semi-Dyck labeled paths costs $\widetilde{O}(n^{\omega})$. A path label is made by concatenating all symbols along the path's edges.

The exact path length problem has many applications. These applications include the labeled path problems given here, which in turn, also have numerous applications.

at February 15, 2018 12:00 AM UTC

Authors: Kamil Khadiev, Mansur Ziatdinov, Ilnaz Mannapov, Aliya Khadieva, Ramis Yamilov
Download: PDF
Abstract: Online algorithms are known model that is investigated with respect to a competitive ratio typically. In this paper, we investigate streaming algorithms as a model for online algorithms. We focus on quantum and classical online algorithms with advice. Special problem $P_k$ was considered. This problem is obtained using "Black Hats Method". There is an optimal quantum online algorithm with single advice bit and single qubit of memory for the problem. At the same time, there is no optimal deterministic or randomized online algorithm with sublogarithmic memory for the same problem even the algorithm gets $o(\log n)$ advice bits. Additionally, we show that quantum online algorithm with a constant number of qubits can be better than deterministic online algorithm even if deterministic one has a constant number of advice bits and unlimited computational power.

at February 15, 2018 12:00 AM UTC

Authors: Yunfeng Hu, Matthew Hudelson, Bala Krishnamoorthy, Altansuren Tumurbaatar, Kevin R. Vixie
Download: PDF
Abstract: We introduce and begin to explore the mean and median of finite sets of shapes represented as integral currents. The median can be computed efficiently in practice, and we focus most of our theoretical and computational attention on medians. We consider questions on the existence and regularity of medians. While the median might not exist in all cases, we show that a mass-regularized median is guaranteed to exist. When the input shapes are modeled by integral currents with shared boundaries in codimension $1$, we show that the median is guaranteed to exist, and is contained in the \emph{envelope} of the input currents. On the other hand, we show that medians can be \emph{wild} in this setting, and smooth inputs can generate non-smooth medians.

For higher codimensions, we show that \emph{books} are minimizing for a finite set of $1$-currents in $\Bbb{R}^3$ with shared boundaries. As part of this proof, we present a new result in graph theory---that \emph{cozy} graphs are \emph{comfortable}---which should be of independent interest. Further, we show that regular points on the median have book-like tangent cones in this case.

From the point of view of computation, we study the median shape in the settings of a finite simplicial complex. When the input shapes are represented by chains of the simplicial complex, we show that the problem of finding the median shape can be formulated as an integer linear program. This optimization problem can be solved as a linear program in practice, thus allowing one to compute median shapes efficiently.

We provide open source code implementing our methods, which could also be used by anyone to experiment with ideas of their own. The software could be accessed at \href{https://github.com/tbtraltaa/medianshape}{https://github.com/tbtraltaa/medianshape}.

at February 15, 2018 12:00 AM UTC

Authors: Yifeng Gao, Jessica Lin
Download: PDF
Abstract: Detecting repeated variable-length patterns, also called variable-length motifs, has received a great amount of attention in recent years. Current state-of-the-art algorithm utilizes fixed-length motif discovery algorithm as a subroutine to enumerate variable-length motifs. As a result, it may take hours or days to execute when enumeration range is large. In this work, we introduce an approximate algorithm called HierarchIcal based Motif Enumeration (HIME) to detect variable-length motifs with a large enumeration range in million-scale time series. We show in the experiments that the scalability of the proposed algorithm is significantly better than that of the state-of-the-art algorithm. Moreover, the motif length range detected by HIME is considerably larger than previous sequence-matching based approximate variable-length motif discovery approach. We demonstrate that HIME can efficiently detect meaningful variable-length motifs in long, real world time series.

at February 15, 2018 12:00 AM UTC

Authors: Xi Chen, Zhengyang Liu, Rocco A. Servedio, Ying Sheng, Jinyu Xie
Download: PDF
Abstract: We study the problem of testing whether an unknown $n$-variable Boolean function is a $k$-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over $\{0,1\}^n$. Our first main result is that distribution-free $k$-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses $\tilde{O}(k^2)/\epsilon$ queries (independent of $n$). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free $k$-junta testing algorithm must make $\Omega(2^{k/3})$ queries even to test to accuracy $\epsilon=1/3$. These bounds establish that while the optimal query complexity of non-adaptive $k$-junta testing is $2^{\Theta(k)}$, for adaptive testing it is $\text{poly}(k)$, and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

at February 15, 2018 02:41 AM UTC

The following guest post comes from a colleague in the theoretical computer science community who wishes to remain anonymous.  Please read it.  You may see this story on more than one theory blog; that's not an accident.


Every #MeToo story over the last several months has made me pause.  My heart races and my concentration fails.  The fact that the stories have largely focused on the workplace adds to my difficulty.

Do I speak out too?

I have shared a few stories with colleagues about things that have happened to me in school and at work.  But these stories have been somewhat lighthearted events that have been easy to share without outing the perpetrators.

For example, I have told a story about a university employee telling me, in so many words, that I should be barefoot and pregnant and not in the office.  What I didn't share is that the same employee, later that year -- despite the fact that our common boss knew about this story because I did indeed report it -- was awarded a best employee award.  How do you think that made me feel?  Like my experience didn't matter and that such comments are condoned by our department.  Why didn't I share that information widely?  Because I was worried that folks would then be able to figure out who the culprit was.  And isn't that even worse?  Shouldn't it be the sexist who is worried and not the woman who, yet again, is made to feel like she doesn't belong?


Let me tangent a bit.  For years I have not flown.  Ostensibly I stopped flying because of the contribution to the climate crisis.  When I travel, I go by train.  It takes longer, but has been surprisingly pleasant.  And when travel takes 3-4 times as long, you don't do it as often, further reducing your carbon footprint.  Of course, that means that I don't go to conferences unless they are nearby.

But when I really think about it, is this really the reason I stopped going to conferences?  A conference I would normally go to was held nearby a few years ago and I didn't go.  Sure, I suffered a grievous injury two weeks before, but I hadn't even registered.  I had planned to not go long before that injury.

So, really, why do I no longer attend conferences?  Partly I don't feel that I need to anymore, now that I have tenure.  When I stopped attending conferences, I was able to "coast into" tenure.  Letter writers would remember me.  I essentially stopped going to conferences and workshops as soon as I possibly could.  


Back to the beginning, or close to.

I was nervous at the first conference I attended as a graduate student.  One of the reasons I was nervous was that I was athletic at the time and planned on daily runs while I was attending -- I was worried that it might be viewed as a waste of time.  My advisor, who also went to the conference, found out about my athleticism and suggested we run together.  This was a relief to me.  That is, until we were running and he started talking about his lackluster sex life with his wife.  I responded by picking up the pace and feigning an illness on the remaining days.  On the last day of the conference we were out for dinner with a large group of people and dinner went late into the night.  I excused myself, as I had a 4AM bus to catch.  My advisor walked me out of the restaurant and awkwardly said something about wanting me to stay and that we should talk.  I stuck to leaving, knowing that I needed some sleep before the long trip home the next day.  He said we should talk when we were back in the office. Honestly, at the time I thought he was going to complain about my talk or my professional performance in some way.  I worried about it all through the weekend until we met next.  I brought it up at the end of our meeting, asking what he wanted to talk about, naively expecting professional criticism.  When he said I must surely know, in a certain voice, I knew he wasn't talking about work.  I feigned ignorance, and he eventually brushed it off and said not to worry.  In the coming months, he would cancel meetings and otherwise make himself unavailable.  After a half year I realized I wouldn't be able to be successful without having a supportive advisor and, despite first planning to quit grad school, found a new advisor and moved on.  That former advisor barely made eye contact with me for the remainder of my time in graduate school.

Fast forward many years.  I was at a small workshop as a postdoc.  A senior and highly respected researcher invited me to dinner.  I was excited at the opportunity to make a stronger connection that would hopefully lead to a collaboration.  However, at dinner he made it very clear that this was not professional by reaching across the table and stroking my hands repeatedly.  I don't even recall how I handled it.  Perhaps I should have expected it -- a grad school friend of mine had a similar, and probably worse, interaction with this same researcher.  Shortly after I got to my room at the hotel, my hotel room phone rang.  It was him.  He wanted to continue our conversation.  I did not.

Perhaps a year later, still as a postdoc, I was at a party and a colleague from another university was there too.  At the end of the party, we were alone. We flirted, mutually.  Flirting led to kissing, kissing led to him picking me up in a way that asserted how much stronger he is than me, which led to my utter discomfort, which led to me saying no, stop, repeatedly.  Which he didn't listen to.  Which led to a calculation in my head.  I could either resist and risk physical injury or I could submit.  I chose to submit, without consent.

For the record, that is called rape.

For a long while, I suppressed it.  I pretended in my own head that it didn't happen that way, that it was consensual.  I even tried to continue working with him -- always in public places, mind you.  The wall in my mind gradually broke down over the years until several years later, we were at the same workshop where the doors of the rooms didn't have locks.  You could lock them from the inside, but not the outside.  I remember worrying that he would be lurking in my room and took to making sure I knew where he was before I ventured back to sleep.


So why would I continue to go to workshops and conferences when that is the environment I know I will face?  Even if I felt safe, if 95% of the attendees are men, how many look at me as a colleague and how many look at me as a potential score?  When I was going up for tenure, I thought long and hard about listing the senior-and-highly-respected researcher on a do-not-ask-for-a-letter list.  But where would it stop?  Do I include all the people who hit on me?  All the people who stared at my breasts or commented on my body?  All the people who I had been given clear signals that they didn't see me as a colleague and equal member of the research community, but as a woman meant to be looked at, hit on, touched inappropriately.

Should I have quit grad school when I had the chance?  We all know it isn't any better in industry.  Should I have pursued another discipline?  No discipline, it seems, is immune to sexualization of women.  But I think the situation is uniquely horrible in fields where there are so few women.  At conferences in theoretical computer science, 5-10% of the attendees are women, as a generous estimate.  The numbers aren't in women's favor.  The chances that you will get hit on, harassed, assaulted are much higher.  There is a greater probability that you will be on your own in a group of men.  You can't escape working with men.  It is next to impossible to build a career when you start striking men off your list of collaborators in such a field.  That is not to say there aren't wonderful men to work with.  There are many men in our field that I have worked with and turned to for advice and spent long hours with and never once had detected so much as a creepy vibe.  But you can't escape having to deal with the many others who aren't good.  When you meet someone at a conference, and they invite you for a drink or dinner to continue the conversation, how do you know that they actually want to talk about work, or at least treat you as they would any colleague?  How do you make that decision?

I hung on until I no longer needed to go to conferences and workshops to advance my career to the stability of tenure.  But surely my career going forward will suffer.  My decision is also hard on my students, who go to conferences on their own without someone to introduce them around.  It is hard on my students who can't, for visa difficulties, go to the international conferences that I am also unwilling to go to, so we roll the dice on the few domestic conferences they can go to.

And now I am switching fields.  Completely.  I went to two conferences last summer.  The first, I brought the protective shield of my child and partner.  The second, I basically showed up for my talk and nothing else.  I wasn't interested in schmoozing.  It'll be difficult, for sure, to establish myself in a new field without fully participating in the expected ways.

Is all this why I am switching fields?  Not entirely, I'm sure, but it must have played a big role.  If I enjoyed conferences as much as everyone else seems to, and didn't feel shy about starting new collaborations, I might be too engrossed to consider reasons to leave.  And certainly, the directions I am pursuing are lending themselves to a much greater chance of working with women.

Why am I speaking out now?  The #MeToo moment is forcing me to think about it, of course.  But I have been thinking about this for years.  I hope it will be a relief to get it off my chest.  I have been "getting on with it" for long enough.  1 in 5 women will deal with rape in their lifetime.  1 in 5!  You would think that I would hear about this from friends.  But I hadn't told anyone about my rape.  And almost no one has told me about theirs.  I think it would help, in the very least therapeutically, to talk about it.


I thought about publishing this somewhere, anonymously, as a "woman in STEM".  I considered publishing it non-anonymously, but was shy to deal with the trolls.  I didn't want to deal with what many women who speak out about their experiences face: have their life be scrutinized, hear excuses being made on behalf of the predators, generally have their experiences denied.  But I think by posting it here, many people in theoretical computer science will read it, rather than a few from the choir.  I am hoping that you will talk to each other about it.  That you will start thinking of ways to make our community better for others.  In all my years of going to conferences and workshops, of all the inappropriate comments and behaviors that others have stood around and witnessed, never once did any of the good ones call that behavior out or intervene.  Maybe they did so in private, but I think it needs to be made public.  Even the good ones can do better.

What can you do?

While you couldn't have protected me from being raped, you can think about the situations we are expected to be in for our careers -- at workshops in remote locations, where we're expected to drink and be merry after hours.  I hope not many of us have been raped by a colleague, but even if you haven't, it doesn't take many instances of being hit on or touched inappropriately to begin to feel unsafe.

I remember being at a conference and, standing in a small group, an attendee interrupted a conversation I was having to tell me that my haircut wasn't good, that I shouldn't have cut my hair short.  I tried to ignore it, and continue my conversation, but he kept going on about it.  Saying how I would never attract a man with that haircut.  No one said anything.  Speak up.  Just say -- shut up! -- that's not appropriate.  Don't leave it up to the people who have to deal with this day in day out to deal with it on their own.  Create a culture where we treat each other with respect and don't silently tolerate objectification and worse.

I regret never reporting my first graduate advisor's behavior, but is it my fault?  I had no idea who to report it to.  I had no idea either in undergrad who I would report such behavior to.  Where I am now is the first place I've been that has had clear channels for reporting sexual harassment and other damaging situations.  The channels are not without problems, but I think the university is continuing to improve them.  Perhaps we should have a way of reporting incidents in our field.  I have a hard time believing, given that myself and a grad school friend had similar experiences with the same senior-and-highly-respected researcher, that others in the field don't know that he is a creep.  It is up to you to protect the vulnerable of our community from creeps and predators.  Keep an eye on them.  Talk to them.  Don't enable them.  As a last resort, shame and isolate them.


Update: I have turned on comment moderation. Be nice or else.

by Jeff Erickson at February 14, 2018 06:04 PM UTC

June 4-8, 2018 Institute for Advanced Study, Princeton https://www.math.ias.edu/ocit2018 Registration deadline: April 15, 2018 This workshop aims to explore connections between complexity and optimization with algebra and analysis, which have emerged from the works on operator scaling. The hope is to inform participants from different communities of both basic tools and new developments, and set … Continue reading Optimization, Complexity and Invariant Theory

by shacharlovett at February 14, 2018 05:58 PM UTC

The SIGecom Test of Time Award recognizes the author or authors of an influential paper or series of papers published between ten and twenty-five years ago that has significantly impacted research or applications exemplifying the interplay of economics and computation.

To be eligible, a paper or series of papers must be on a topic in the intersection of economics and computation, including topics in electronic commerce, and must have been first published, in preliminary or final form, in an archival journal or conference proceedings no less than ten years and no more than twenty-five years before the year the award is conferred. Papers for which all authors are deceased at the time the Award Committee makes its decision are not eligible for the award.

The 2018 SIGecom Test of Time Award will be given for papers published no earlier than 1993 and no later than 2008. Nominations are due by March 5th, 2018, and must be made by email to the Award Committee (sigecom-awards-tot@acm.org) with “ACM SIGecom Test of Time Award” in the subject.

Any member of SIGecom may submit a nomination. Self-nomination is not allowed. Nominations must include the following, preferably in a single PDF file:

1. Bibliographic data for the paper or series of papers demonstrating publication, in preliminary or final form, at least ten years and at most twenty-five years before the award year.

2. An endorsement letter by the nominator of no more than two pages describing the content of the paper or series of papers and the lasting contribution, significance, and impact of the work.

3. The names, email addresses, and affiliations of at least two other endorsers. Endorsers, like the nominator, may not be authors of the paper or papers under consideration.

4. A one-sentence statement that describes the contribution of the paper or series of papers.

The two additional endorsers should send letters directly to the Award Committee (sigecom-awards-tot@acm.org) by the same deadline. Each letter should specify the relationship of the endorser to nominees and describe, in 500 words or fewer, the lasting contribution, significance, and impact of the paper or papers.

An unsuccessful nomination can be reconsidered for three award cycles, with the option of updating the original nomination to reflect additional impact. Subsequently, a new nomination must be provided. All matters relating to the selection process that are not specified here are left to the discretion of the Award Committee.

The award, conferred annually at the ACM Conference on Economics and Computation, includes a plaque and complimentary conference registration for each winner and an honorarium of $1,000 to be shared among the winners. The award may not be given if the nominations are judged not to meet the standards of the award.

It is expected that at least one of the nominated authors, if selected for the award, will attend the next ACM Conference on Economics and Computation on June 18-22, 2018, in Ithaca, NY, USA, to accept the award and give a presentation on the work. The award includes complimentary registration but does not cover travel expenses to attend the conference.

The Award Committee welcomes questions from anyone considering or intending to submit a nomination. The Award Committee will accept informal proposals for potential nominees or tentative offers to prepare formal nominations, should they be needed.

On behalf of the 2017 Award Committee:

Tuomas Sandholm (Chair)
Robert Kleinberg
Nikhil Devanur
sigecom-awards-tot@acm.org

by robertkleinberg at February 14, 2018 05:04 PM UTC


Tid-bit: delicacy, dainty, snack, nibble, appetizer, hors d’oeuvre, goody, dipper, finger food

Adam Engst is the publisher of the site TidBITS. This is a site dedicated to technical insights about all aspects of Apple machines: from nano to servers.

Today I want to talk about mathematical tidbits not Apple devices, but look at the above site for information about Apple stuff of all kinds.

By the way:

“tasty tidbits” is a small and particularly interesting item of gossip or information. Origin mid 17th century (as tyd bit, tid-bit ): from dialect tid «tender» (of unknown origin).

TidBITS has been running since 1990, when Apple made only a certain kind of bulky device that went by the name “personal computer.” The Internet did not exist yet, so the site was distributed via a platform called HyperCard, which combined publishing, presentation, and database functions.

Some Tidbits

{\bullet} A Math Result: An Interesting Pattern

\displaystyle 111,111,111 \times 111,111,111 = 12,345,678,\mathbf{9}87,654,321.

{\bullet} Another Math Result: A Bad Joke
If you write out {\pi} to two decimal places, backwards it spells “pie”:

{\bullet} The New York Times: Downgrades The Size of The Human Genome

In a recent article in the Times it was reported that a certain sequence effort found that a bacteria had a large genome. It was actually so large that it was a thousand times larger than our human genome. The article then added that the human genome is about 3.5 million bases. Wrong. It is actually about 3.5 billion bases. I reported this typo to the Times by the way.

{\bullet} Senator Jack Reed: On CNN Today

I happen to tune in CNN’s broadcast of the Senate hearing on security today. There Reed asked security experts whether or not the US has a coherent plan for quantum computing. They basically said that they could not say much in an open hearing. I do find it remarkable that quantum computing is mentioned in a Senate hearing.

Another Tidbit

{\bullet} Gifted: The Movie

This is a movie about a young child, Mary, who is a math savant, and whether or not she should be placed in a special school. I recently watched the movie with my wife Kathryn Farley. We enjoyed the movie although it had a pretty simple plot. Indeed see this:

Colin Covert of the Star Tribune gave the film 3/4 stars, saying, “Sure, it’s a simple, straightforward film, but sometimes that’s all you need as long as its heart is true.” Richard Roeper gave the film 4 out of 4 stars and said, “Gifted isn’t the best or most sophisticated or most original film of the year so far—but it just might be my favorite.”


Mary’s mother had been a promising mathematician, who worked on the famous Navier-Stokes problem, before taking her own life when Mary was six months old. Indeed the plot of the movie hinges on the mother actually solving the problem. Of course, in the movie we get no hint how she may have done this. One of the key parts of the movie concerns when Mary is being examined by a math professor—this is to determine if she really is gifted. Mary is asked to evaluate the definite integral that is written on a chalk board in a lecture hall. The integral is:

\displaystyle \int_{-\infty}^{\infty} e^{x^{2}} dx.

She cannot figure it out and leaves the exam without answering the question. But finally she explains to her grandmother that it is a trick question. The above integral of course is equal to infinity. She comes back to the lecture hall and explains that she was taught to never correct adults. Now she corrects the problem with a minus sign and solves it:
\displaystyle \int_{-\infty}^{\infty} e^{-x^{2}} dx = \sqrt{\pi}

I must point out that when the problem came up I said to my wife that the first integral was incorrect. I thought perhaps the movie had an error in it. But no it was a trick question—very neat. No doubt this was based on advice from the math advisors—who include Terence Tao.

Open Problems

People have said that a mathematician is someone who thinks that

\displaystyle \int_{-\infty}^{\infty} e^{-x^{2}} dx = \sqrt{\pi}

is obvious. Well, if you multiply two copies of the equation, one with “{y}” in place of “{x},” you get an integral with {-(x^2 + y^2)} in the exponent on the left-hand side. Using {r^2 = x^2 + y^2} converts it to polar coordinates, and then you can intuit why what you get equals {\pi}. I wonder if there is a similar test for complexity theorists? Any suggestions?

by rjlipton at February 14, 2018 02:39 PM UTC

This is a guest post by a colleague in the TCS community, a person I know. If you read other TCS blogs you might come across this there. This is by design. Please do read it. 

Every #MeToo story over the last several months has made me pause. My heart races and my concentration fails. The fact that the stories have largely focused on the workplace adds to my difficulty.

Do I speak out too?

I have shared a few stories with colleagues about things that have happened to me in school and at work. But these stories have been somewhat lighthearted events that have been easy to share without outing the perpetrators.

For example, I have told a story about a university employee telling me, in so many words, that I should be barefoot and pregnant and not in the office. What I didn't share is that the same employee, later that year -- despite the fact that our common boss knew about this story because I did indeed report it -- was awarded a best employee award. How do you think that made me feel? Like my experience didn't matter and that such comments are condoned by our department. Why didn't I share that information widely? Because I was worried that folks would then be able to figure out who the culprit was. And isn't that even worse? Shouldn't it be the sexist who is worried and not the woman who, yet again, is made to feel like she doesn't belong?

---

Let me tangent a bit. For years I have not flown. Ostensibly I stopped flying because of the contribution to the climate crisis. When I travel, I go by train. It takes longer, but has been surprisingly pleasant. And when travel takes 3-4 times as long, you don't do it as often, further reducing your carbon footprint. Of course, that means that I don't go to conferences unless they are nearby.

But when I really think about it, is this really the reason I stopped going to conferences? A conference I would normally go to was held nearby a few years ago and I didn't go. Sure, I suffered a grievous injury two weeks before, but I hadn't even registered. I had planned to not go long before that injury.

So, really, why do I no longer attend conferences? Partly I don't feel that I need to anymore, now that I have tenure. When I stopped attending conferences, I was able to "coast into" tenure. Letter writers would remember me. I essentially stopped going to conferences and workshops as soon as I possibly could.

---

Back to the beginning, or close to.

I was nervous at the first conference I attended as a graduate student. One of the reasons I was nervous was that I was athletic at the time and planned on daily runs while I was attending -- I was worried that it might be viewed as a waste of time. My advisor, who also went to the conference, found out about my athleticism and suggested we run together. This was a relief to me. That is, until we were running and he started talking about his lackluster sex life with his wife. I responded by picking up the pace and feigning an illness on the remaining days. On the last day of the conference we were out for dinner with a large group of people and dinner went late into the night. I excused myself, as I had a 4AM bus to catch. My advisor walked me out of the restaurant and awkwardly said something about wanting me to stay and that we should talk. I stuck to leaving, knowing that I needed some sleep before the long trip home the next day. He said we should talk when we were back in the office. Honestly, at the time I thought he was going to complain about my talk or my professional performance in some way. I worried about it all through the weekend until we met next. I brought it up at the end of our meeting, asking what he wanted to talk about, naively expecting professional criticism. When he said I must surely know, in a certain voice, I knew he wasn't talking about work. I feigned ignorance, and he eventually brushed it off and said not to worry. In the coming months, he would cancel meetings and otherwise make himself unavailable. After a half year I realized I wouldn't be able to be successful without having a supportive advisor and, despite first planning to quit grad school, found a new advisor and moved on. That former advisor barely made eye contact with me for the remainder of my time in graduate school.

Fast forward many years. I was at a small workshop as a postdoc. A senior and highly respected researcher invited me to dinner. I was excited at the opportunity to make a stronger connection that would hopefully lead to a collaboration. However, at dinner he made it very clear that this was not professional by reaching across the table and stroking my hands repeatedly. I don't even recall how I handled it. Perhaps I should have expected it -- a grad school friend of mine had a similar, and probably worse, interaction with this same researcher. Shortly after I got to my room at the hotel, my hotel room phone rang. It was him. He wanted to continue our conversation. I did not.

Perhaps a year later, still as a postdoc, I was at a party and a colleague from another university was there too. At the end of the party, we were alone. We flirted, mutually. Flirting led to kissing, kissing led to him picking me up in a way that asserted how much stronger he is than me, which led to my utter discomfort, which led to me saying no, stop, repeatedly. Which he didn't listen to. Which led to a calculation in my head. I could either resist and risk physical injury or I could submit. I chose to submit, without consent.

For the record, that is called rape.

For a long while, I suppressed it. I pretended in my own head that it didn't happen that way, that it was consensual. I even tried to continue working with him -- always in public places, mind you. The wall in my mind gradually broke down over the years until several years later, we were at the same workshop where the doors of the rooms didn't have locks. You could lock them from the inside, but not the outside. I remember worrying that he would be lurking in my room and took to making sure I knew where he was before I ventured back to sleep.

---

So why would I continue to go to workshops and conferences when that is the environment I know I will face? Even if I felt safe, if 95% of the attendees are men, how many look at me as a colleague and how many look at me as a potential score? When I was going up for tenure, I thought long and hard about listing the senior-and-highly-respected researcher on a do-not-ask-for-a-letter list. But where would it stop? Do I include all the people who hit on me? All the people who stared at my breasts or commented on my body? All the people who I had been given clear signals that they didn't see me as a colleague and equal member of the research community, but as a woman meant to be looked at, hit on, touched inappropriately.

Should I have quit grad school when I had the chance? We all know it isn't any better in industry. Should I have pursued another discipline? No discipline, it seems, is immune to sexualization of women. But I think the situation is uniquely horrible in fields where there are so few women. At conferences in theoretical computer science, 5-10% of the attendees are women, as a generous estimate. The numbers aren't in women's favor. The chances that you will get hit on, harassed, assaulted are much higher. There is a greater probability that you will be on your own in a group of men. You can't escape working with men. It is next to impossible to build a career when you start striking men off your list of collaborators in such a field. That is not to say there aren't wonderful men to work with. There are many men in our field that I have worked with and turned to for advice and spent long hours with and never once had detected so much as a creepy vibe. But you can't escape having to deal with the many others who aren't good. When you meet someone at a conference, and they invite you for a drink or dinner to continue the conversation, how do you know that they actually want to talk about work, or at least treat you as they would any colleague? How do you make that decision?

I hung on until I no longer needed to go to conferences and workshops to advance my career to the stability of tenure. But surely my career going forward will suffer. My decision is also hard on my students, who go to conferences on their own without someone to introduce them around. It is hard on my students who can't, for visa difficulties, go to the international conferences that I am also unwilling to go to, so we roll the dice on the few domestic conferences they can go to.

And now I am switching fields. Completely. I went to two conferences last summer. The first, I brought the protective shield of my child and partner. The second, I basically showed up for my talk and nothing else. I wasn't interested in schmoozing. It'll be difficult, for sure, to establish myself in a new field without fully participating in the expected ways.

Is all this why I am switching fields? Not entirely, I'm sure, but it must have played a big role. If I enjoyed conferences as much as everyone else seems to, and didn't feel shy about starting new collaborations, I might be too engrossed to consider reasons to leave. And certainly, the directions I am pursuing are lending themselves to a much greater chance of working with women.

Why am I speaking out now? The #MeToo moment is forcing me to think about it, of course. But I have been thinking about this for years. I hope it will be a relief to get it off my chest. I have been "getting on with it" for long enough. 1 in 5 women will deal with rape in their lifetime. 1 in 5! You would think that I would hear about this from friends. But I hadn't told anyone about my rape. And almost no one has told me about theirs. I think it would help, in the very least therapeutically, to talk about it.

---

I thought about publishing this somewhere, anonymously, as a "woman in STEM". I considered publishing it non-anonymously, but was shy to deal with the trolls. I didn't want to deal with what many women who speak out about their experiences face: have their life be scrutinized, hear excuses being made on behalf of the predators, generally have their experiences denied. But I think by posting it here, many people in theoretical computer science will read it, rather than a few from the choir. I am hoping that you will talk to each other about it. That you will start thinking of ways to make our community better for others. In all my years of going to conferences and workshops, of all the inappropriate comments and behaviors that others have stood around and witnessed, never once did any of the good ones call that behavior out or intervene. Maybe they did so in private, but I think it needs to be made public. Even the good ones can do better.

What can you do?

While you couldn't have protected me from being raped, you can think about the situations we are expected to be in for our careers -- at workshops in remote locations, where we're expected to drink and be merry after hours. I hope not many of us have been raped by a colleague, but even if you haven't, it doesn't take many instances of being hit on or touched inappropriately to begin to feel unsafe.

I remember being at a conference and, standing in a small group, an attendee interrupted a conversation I was having to tell me that my haircut wasn't good, that I shouldn't have cut my hair short. I tried to ignore it, and continue my conversation, but he kept going on about it. Saying how I would never attract a man with that haircut. No one said anything. Speak up. Just say -- shut up! -- that's not appropriate. Don't leave it up to the people who have to deal with this day in day out to deal with it on their own. Create a culture where we treat each other with respect and don't silently tolerate objectification and worse.

I regret never reporting my first graduate advisor's behavior, but is it my fault? I had no idea who to report it to. I had no idea either in undergrad who I would report such behavior to. Where I am now is the first place I've been that has had clear channels for reporting sexual harassment and other damaging situations. The channels are not without problems, but I think the university is continuing to improve them. Perhaps we should have a way of reporting incidents in our field. I have a hard time believing, given that myself and a grad school friend had similar experiences with the same senior-and-highly-respected researcher, that others in the field don't know that he is a creep. It is up to you to protect the vulnerable of our community from creeps and predators. Keep an eye on them. Talk to them. Don't enable them. As a last resort, shame and isolate them.

by Suresh Venkatasubramanian (noreply@blogger.com) at February 14, 2018 02:00 PM UTC

Tonight at 8:00 Israel time TCS+ Dor Misner on 2-to-2 games.

  

On Monday, February 19, we will have a special day on “Quantum Coding and High Dimensional Expanders” organized by Gilles Zemor.

Sandwiches will be served for lunch, alongside cut vegetables and pastries.

Our calendar: https://iiashdc.wordpress.com/events-calendar/

Place: Room 130, IIAS, Feldman Building, Givat Ram

Program:

10:00 – 11:00 Gilles Zemor. Background on quantum computing and coding.

11:30 – 12:30 Gilles Zemor. Quantum stabilizer codes and quantum LDPC codes.

14:00 – 15:00 Dorit Aharonov. Quantum locally testable codes.

15:15 – 16:15 Gilles Zemor. Quantum LDPC codes and high-dimensional expanders.

by Gil Kalai at February 14, 2018 08:20 AM UTC

The Centre for Quantum Technologies at the National University of Singapore invites applications for a Postdoctoral Research Fellowship in its Computer Science Group in the broad area of quantum-safe cryptography.

Website: https://www.quantumlah.org/about/jobdesc.php?id=23
Email: divesh.aggarwal@gmail.com

by shacharlovett at February 14, 2018 05:46 AM UTC

Aaronson for local reductions: see for example, Jahanjou, Miles, and Viola [137]

Barak for pseudorandom functions: (e.g., see [MV12])

Wigderson for communication complexity: (e.g. see [Vio15])

I am not saying that these are not appropriate citation styles (I leave this determination to you). For me I am just happy that my work had an impact for example in three different areas.

by Emanuele at February 13, 2018 08:57 PM UTC

The University of Edinburgh has made a call to appoint some Chancellor’s Fellows in a number of areas, including “Digital Technology”. The emphasis is on data sciences, and algorithms is one of the areas of interest. Chancellor’s fellows are prestigious positions at the lecturer level (UK system) with reduced teaching in the first few years. See the website for detailed information.

Website: https://www.ed.ac.uk/informatics/about/work-with-us/vacancies/chancellor-fellowship-digital-technologies
Email: hguo@inf.ed.ac.uk

by shacharlovett at February 13, 2018 07:21 PM UTC

Various people pointed me to a Washington Post piece by Vivek Wadhwa, entitled “Quantum computers may be more of an immiment threat than AI.”  I know I’m late to the party, but in the spirit of Pete Wells’ famous New York Times “review” of Guy Fieri’s now-closed Times Square restaurant, I have a few questions that have been gnawing at me:

Mr. Wadhwa, when you decided to use the Traveling Salesman Problem as your go-to example of a problem that quantum computers can solve quickly, did the thought ever cross your mind that maybe you should look this stuff up first—let’s say, on Wikipedia?  Or that you should email one person—just one, anywhere on the planet—who works in quantum algorithms?

When you wrote of the Traveling Salesman Problem that “[i]t would take a laptop computer 1,000 years to compute the most efficient route between 22 cities”—how confident are you about that?  Willing to bet your house?  Your car?  How much would it blow your mind if I told you that a standard laptop, running a halfway decent algorithm, could handle 22 cities in a fraction of a second?

When you explained that quantum computing is “equivalent to opening a combination lock by trying every possible number and sequence simultaneously,” where did this knowledge come from?  Did it come from the same source you consulted before you pronounced the death of Bitcoin … in January 2016?

Had you wanted to consult someone who knew the first thing about quantum computing, the subject of your column, would you have been able to use a search engine to find one?  Or would you have simply found another “expert,” in the consulting or think-tank worlds, who “knew” the same things about quantum computing that you do?

Incidentally, when you wrote that quantum computing “could pose a greater burden on businesses than the Y2K computer bug did toward the end of the ’90s,” were you trying to communicate how large the burden might be?

And when you wrote that

[T]here is substantial progress in the development of algorithms that are “quantum safe.” One promising field is matrix multiplication, which takes advantage of the techniques that allow quantum computers to be able to analyze so much information.

—were you generating random text using one of those Markov chain programs?  If not, then what were you referring to?

Would you agree that the Washington Post has been a leader in investigative journalism exposing Trump’s malfeasance?  Do you, like me, consider them one of the most important venues on earth for people to be able to trust right now?  How does it happen that the Washington Post publishes a quantum computing piece filled with errors that would embarrass a high-school student doing a term project (and we won’t even count the reference to Stephen “Hawkings”—that’s a freebie)?

Were the fact-checkers home with the flu?  Did they give your column a pass simply because it was “perspective” rather than news?  Or did they trust you as a widely-published technology expert?  How does one become such an expert, anyway?

Thanks!

by Scott at February 13, 2018 05:18 PM UTC

The St.Petersburg State University opens 7 full-time positions of various level (Assistant to Full Professor) for advanced teaching (to very bright students!) within the new Math and TCS program headed by Stanislav Smirnov. The salary ranges from 121710 to 194736 RUB/month. This year teaching in Russian is required.

Deadline: 17:00 MSK, February 28, 2018.
Teaching starts: September 1, 2018.

Website: http://math-cs.spbu.ru/news/seven-new-positions/
Email: secretariat@chebyshev.spb.ru

by shacharlovett at February 13, 2018 08:19 AM UTC

The algorithms group in Duke Computer Science invites applications for a postdoctoral position. Candidates in geometric algorithms and data structures are of particular interest. Applications must be submitted by email to theory-jobs@cs.duke.edu with the Subject: “Postdoc 18 application” and include an up-to-date resume, a research statement, and the names of at least 3 reference letter writers.

Website: http://theorywiki.cs.duke.edu/index.php/Home
Email: theory-jobs@cs.duke.edu

by shacharlovett at February 13, 2018 07:03 AM UTC

The Duke Mathematics and ECE departments seek a post-doctoral teaching
fellow to help with the instruction of classes which combine the theory and implementation of algorithms. Knowledge of Python, data structures, analysis of algorithms, and graph algorithms is highly desirable. Position will be two years with the possibility of renewal.

Website: https://www.mathjobs.org/jobs/jobs/11699
Email: jonm@math.duke.edu

by shacharlovett at February 13, 2018 12:48 AM UTC

Juntas (or, with more words, “functions of few relevant attributes”) are a central concept in computational learning theory, analysis of Boolean functions, and machine learning. Without trying to motivate this here (see e.g. this blog post of Dick Lipton’s), let us first recap some notions.

A Boolean function f\colon \{-1,1\}^n \to \{-1,1\} is said to be a k-junta (where one should think of n as big, and k as smallish, constant or say at most \log n) if there is an unknown set of k indices i_1,\dots,x_k such that f depends only on the variables x_{i_1},\dots, x_{i_k}. Put differently, if there exists a Boolean function g\colon \{-1,1\}^k \to \{-1,1\} such that, for all x,

\Large f(x) = g(x_{i_1},\dots,x_{i_k})

(f is technically on n variables, but “morally” on k). In particular, any Boolean function is trivially an n-junta. Also, because names are fun: a 1-junta is called a dictator.

Now, if f turns out to be a k-junta for some small value of k, then one can hope to do many things more efficiently: e.g., learn f; test some interesting property of f. With a little bit of luck, now the complexity of all these tasks could be much milder, with k replacing (ish) all the n‘s, with maybe some \log n‘s thrown in for good measure.

So testing whether an unknown function f\colon \{-1,1\}^n \to \{-1,1\} is a k-junta (given, say, query access to it, or even random samples) could be a quite useful thing to have in our toolbox. Here enters property testing of juntas:

Given parameters k\geq 1, \varepsilon\in(0,1), and query access to an unknown Boolean function f\colon \{-1,1\}^n \to \{-1,1\}, distinguish with high probability between the case where f is a k-junta and the case where f is at least at distance \varepsilon (in Hamming distance) for any k-junta.

(In the above, the main parameter is n, then k, and \varepsilon comes last — and is often considered as a small constant for the sake of asymptotics. Further, the focus is on the worst-case number of queries made to the unknown function, the query complexity, and not the running time.)

Property testing algorithms come in many flavors: they can be non-adaptive (decide all the queries they will make to f beforehand, based only on their private randomness), adaptive, one-sided (accept juntas with probability 1 and only err, with small probability, on functions far from being juntas), two-sided; standard (as defined above) or tolerant (accept functions \varepsilon'-close to some k-junta, and reject those that are \varepsilon-far).

So what do we know thus far?

1 Surprise: there is no n

Nobody likes to have three parameters, and nobody likes n anyway. The first main insight (and surprising result), due to Fischer, Kindler, Ron, Safra, and Samorodnitsky [FKRSS04] who initiated the study of k-junta testing, is that, actually, one can get rid of n altogether!

Namely, they give a tester (actually, a couple) with query complexity O(k^2/\varepsilon^2), non-adaptive, and one-sided. The main idea underlying this result is the following: if one partitions randomly the n variables in \mathrm{poly}(k) bins, then with high probability the following happens. If f is indeed a k-junta, then clearly at most k of these bins will ever contain a relevant variable. Moreover, if f is far from being a k-junta, then either k+1 bins will contain significantly “influent” variables, or many bins will contain many “relatively influent” variables.

So then, it suffices to estimate the “influence” of each of these bins, and reject if more than k of them have noticeable influence.

Note that I used the word “influence” quite a lot in the previous paragraph, and this for a good reason: the quantity at play here is the influence of a set of variables, a generalization of the standard notion of influence of a variable in Boolean analysis. Defined as

\textrm{Inf}_f(S) \stackrel{\rm def}{=} 2\Pr_{x\sim \{-1,1\}^{[n]\setminus S}, y\sim \{-1,1\}^{S}}[ f(x\sqcup y) \neq f(x) ]

this quantity captures the probability that “re-randomizing” the variables in S will change the outcome of the function. Also, it is very simple to estimate given query access to f.

2 Let’s bring that k down

After this quite amazing result, Eric Blais [Blais08, Blais09] improved this bound twice: first, establishing a non-adaptive, two-sided upper bound of \tilde{O}(k^{3/2})/\varepsilon queries, which hinges on a clever balancing between two sub-algorithms: one to detect few high-influence variables, and the other to detect many low-influence variables. As before, this algorithm relies on random partitioning, and estimating the influence.

The second algorithm yields an adaptive, one-sided upper bound of {O}(k\log k + k/\varepsilon) queries—and proceeds by binary search, trying to find and eliminate influential bins one at a time, repeatedly starting with two inputs x,y with f(x)\neq f(y) and “moving” from x to y, changing all the variables inside a bin at once until the value of f flips.

These last two upper bounds have remained unchallenged. For a rather good reason: they’re more or less tight, each of them.

Indeed, Chockler and Gutfreund [CG04], and Blais, Brody, and Matulef [BBM12] proved that \Omega(k) queries were necessary, even for adaptive, two-sided algorithms. (This leaves a \log k and an \varepsilon hanging…) Then, after Servedio, Tan, and Wright [STW15] proved a slighter stronger lower bound (for some regime of \varepsilon) against non-adaptive tester, a result of Chen, Servedio, Tan, Waingarten, and Xie [CSTWX17] showed that, actually, \tilde{\Omega}(k^{3/2}/\varepsilon) query were necessary for non-adaptive, two-sided testing of k-juntas.

So, well, both of Blais’ testers are optimal. Are we done?

3 The Virtue of Tolerance

Not quite, actually. Up to some slack (see open problems below), we know the landscape of standard testing of k-juntas. But what about trying to distinguish between a very slightly noisy version of a k-junta, and something very far from being one? I.e., what about tolerant testing?

While all the above algorithms have some (very) small amount of tolerant built in (namely, something like \mathrm{poly}(\varepsilon/k)), the best algorithm known for “general” tolerant testing for a while was an \exp(k/\varepsilon)-query tolerant tester implied by… the algorithm of [Blais09]. At least, there is no n in there either. But since it is totally conceivable that a tolerant testing algorithm with polynomial (in k and 1/\varepsilon) query complexity exists—we have no separation, this is slightly unsatisfying.

Recently, with Eric Blais, Talya Eden, Amit Levi, and Dana Ron [BCELR18], we provided two different algorithms for tolerant testing of juntas.

The first provides a smooth trade-off between the amount of tolerance guaranteed and the query complexity: for \varepsilon \rho vs. \varepsilon, the query complexity is O((k\log k)/(\varepsilon \rho(1-\rho)^k). In particular, for \rho = 1/k this (slightly) improves on the weak  tolerance provided by the known (standard) testers, while having low polynomial query complexity. At the other end of the spectrum, setting \rho = O(1) ones gets a tolerant testing algorithm with query complexity \exp(k)/\varepsilon (so, at least, the \varepsilon moved out of the exponent).

The second builds on the properties of the influence function — which is not only directly related to the distance to k-junta$, but also happens to be monotone, submodular, and generally very nice — to phrase the question as a submodular minimization problem under cardinality constraints. Which turns out to be a drag, since this problem is NP-hard, even to approximate. However, relaxing the cardinality constraint (replacing it with a suitable linear penalization term in the objective) makes the problem tractable, at the price of losing a bit in the solution. Specifically, now one can distinguish, with \mathrm{poly}(k,1/\varepsilon) queries, functions which are \varepsilon-close to some k-junta from those which are O(\varepsilon)-far from every $2k$-juntas.

Which almost solves the question, but not quite.

4 Intolerance is Easier?

Mentioned earlier was the fact that we do not have any separation being tolerant and intolerance testers for k-juntas. That was a bit of a lie: in yet unpublished work, Levi and Waingarten [LW18] establish the following:

Any (possibly two-sided) non-adaptive tolerant tester for k-juntas  must have query complexity \tilde{\Omega}(k^2) (for \varepsilon',\varepsilon=\Theta(1)).

Since the standard testing version can be done with \tilde{O}(k^{3/2}) queries, this is a polynomial separation between standard and tolerant testing, and the only one I am aware of for a natural class of Boolean functions.

Now, the proof goes through a reduction to a graph testing question, in a model the authors introduce (that of rejection sampling oracle, which on query T\subseteq [n] returns \{i,j\}\cap T for an edge (i,j) sampled uniformly at random from the unknown graph G; and the cost of a query T is its size \lvert T\rvert). In more detail, they show a lower bound of \Omega(n^2) rejection sampling query cost to distinguish between (i) G being a complete balanced bipartite graph with side size n/2, and (ii) G being the union of two copies of K_{n/2}.

5 Open questions

The above may give the impression that all is done, and that the landscape is fully known (up to some technical details). Sadly (or fortunately), this is far from being true; below, I highlight a few question i personnally find very interesting and appealing. (I may have very bad taste, mind you) 

junta

  • The role of adaptivity in standard testing. We have pretty tight bounds (up to some \log k‘s and \varepsilon‘s) for both adaptive and non-adaptive testing of juntas. What about testing with bounded adaptivity (as introduced in [CG17])? Is there a smooth tradeoff between query complexity and number of rounds of adaptivity, or do things “jump” immediately?
  • Tolerant testing. Can we get a \textrm{poly}(k,1/\varepsilon)-query tolerant tester without the relaxation “close to k-junta vs. far from 2k-junta$?
  • Tolerant testing. Can we get a tester (even with query complexity exponential in k, but independent of n) which distinguishes “\varepsilon-close vs. 1.1\varepsilon-far”? (It looks like that all techniques relying on using the influence function, due to its slightly-loose relation to distance to k-junta, have to lose a factor 2 here). If not, can we prove a lower bound against “influence-based testers”?
  • Standard vs. tolerant testing. Can the separation of Levi and Waingarten be extended to adaptive algorithms?

And finally, one I am really fond of: changing the setting itself, say a function f\colon\mathbb{R}^n \to [-1,1] is a k-junta if there exists an unknown rotation of the space such that, in this unknown basis, f depends on at most k coordinates. (That is, f only depends on a low-dimensional subspace). Can we test efficiently whether an unknown f is a k-junta?


References.

[BBM12] Blais, Brody, and Matulef. Property testing lower bounds via communication complexity. CCC, 2012.
[BCELR18] Blais, Canonne, Eden, Levi, and Ron. Tolerant Junta Testing and the Connection to Submodular Optimization and Function Isomorphism. SODA, 2018.
[Blais08] Blais. Improved bounds for testing juntas. RANDOM, 2008.
[Blais09] Blais. Testing juntas nearly optimally. STOC, 2009.
[CG04] Chockler and Gutfreund. A lower bound for testing juntas. Information Processing Letters, 2004.
[CG17] Canonne and Gur. An adaptivity hierarchy theorem for property testing. CCC, 2017.
[CSTWX17] Chen, Servedio, Tan, Waingarten,  and Xie. Settling the query complexity of non-adaptive junta testing. CCC, 2017.
[FKRSS04] Fischer, Kindler, Ron, Safra, and Samorodnitsky. Testing juntas. J. Computer
& System Sciences, 2004.
[STW15] Servedio, Tan, and Wright. Adaptivity helps for testing juntas. CCC, 2015.

by ccanonne at February 12, 2018 02:46 PM UTC

In NIPS 2017, Ali Rahimi and Ben Recht won the test of time award for their paper “Random Features for Large-scale Kernel Machines”. Ali delivered the following acceptance speech (see also addendum) in which he said that Machine Learning has become “alchemy” in the sense that it involves more and more “tricks” or “hacks” that work well in practice, but are very poorly understood. (Apparently alchemists were also successful in making many significant practical  discoveries.) Similarly, when I teach cryptography I often compare the state of “pre modern” cryptography  (before Shannon and Diffie-Hellman) to alchemy.

Yann LeCun was not impressed with the speech, saying that sticking to using methods for which we have theoretical understanding is “akin to looking for your lost car keys under the street light knowing you lost them someplace else.” There is a sense in which LeCun is very right. For example, already in the seminal paper in which Jack Edmonds defined the notion of  polynomial time he said that “it would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion.” But I do want to say something in defense of “looking under the streetlight”. When we want to understand the terrain, rather than achieve some practical goal, it can make a lot of sense to start in the simplest regime (e.g. “most visible” or “well lit”) and then expand our understanding (e.g., “shine new lights”). Heck, it may well be that when the super intelligent robots are here, then they would look for their keys by first making observations under the light and then extrapolating to the unlit area.

by Boaz Barak at February 12, 2018 02:15 AM UTC