Theory of Computing Blog Aggregator

If you finitely color the natural numbers there will be a monochromatic solution to

x+2y+3z - 5w = 0

There is a finite coloring of the natural numbers such that there is NO monochromatic solution to

x+2y+3z - 7w = 0

More generally:

An equation is REGULAR if any finite coloring of the naturals yields a mono solution.

RADO's THEOREM: A linear equation a1 x1 + ... + an xn = 0 is regular IFF some subset of the ai's sums to 0 (the ai's are all integers).

Rado's theorem is well known.

What about other equations? Ronald Graham has offered $100 to prove the following:

For all two colorings of the naturals there is a mono x,y,z such that

x2 + y2 = z

I've seen this conjecture before and I thought (as I am sure did others) that first there would be a prove that gave an ENORMOUS bound on

f(c) = the least n such that for all c-colorings of {1,...,n} there is a mono (x,y,z) such that ...

and then there would be some efforts using SAT solvers and such to get better bounds on f(c).

This is NOT what has happened. Instead there is now a paper by Heule, Kullmann, Marek, where they show f(2)=7285.

It is a computer proof and is the longest math proof ever. They also have a program that checked that the proof was correct.

And what did they get for their efforts? A check from Ronald Graham for $100.00 and a blog entry about it!

While I am sure there proof is correct I wish there was a human-readable proof that f(2) existsed even if it gave worse bounds. For that matter I wish there was a proof tha,t for all c, f(c) exists. Maybe one day; however, I suspect that we are not ready for such problems.

by GASARCH ( at May 30, 2016 04:20 AM UTC

Authors: Dan Garber, Elad Hazan, Chi Jin, Sham M. Kakade, Cameron Musco, Praneeth Netrapalli, Aaron Sidford
Download: PDF
Abstract: We give faster algorithms and improved sample complexities for estimating the top eigenvector of a matrix $\Sigma$ -- i.e. computing a unit vector $x$ such that $x^T \Sigma x \ge (1-\epsilon)\lambda_1(\Sigma)$:

Offline Eigenvector Estimation: Given an explicit $A \in \mathbb{R}^{n \times d}$ with $\Sigma = A^TA$, we show how to compute an $\epsilon$ approximate top eigenvector in time $\tilde O([nnz(A) + \frac{d*sr(A)}{gap^2} ]* \log 1/\epsilon )$ and $\tilde O([\frac{nnz(A)^{3/4} (d*sr(A))^{1/4}}{\sqrt{gap}} ] * \log 1/\epsilon )$. Here $nnz(A)$ is the number of nonzeros in $A$, $sr(A)$ is the stable rank, $gap$ is the relative eigengap. By separating the $gap$ dependence from the $nnz(A)$ term, our first runtime improves upon the classical power and Lanczos methods. It also improves prior work using fast subspace embeddings [AC09, CW13] and stochastic optimization [Sha15c], giving significantly better dependencies on $sr(A)$ and $\epsilon$. Our second running time improves these further when $nnz(A) \le \frac{d*sr(A)}{gap^2}$.

Online Eigenvector Estimation: Given a distribution $D$ with covariance matrix $\Sigma$ and a vector $x_0$ which is an $O(gap)$ approximate top eigenvector for $\Sigma$, we show how to refine to an $\epsilon$ approximation using $ O(\frac{var(D)}{gap*\epsilon})$ samples from $D$. Here $var(D)$ is a natural notion of variance. Combining our algorithm with previous work to initialize $x_0$, we obtain improved sample complexity and runtime results under a variety of assumptions on $D$.

We achieve our results using a general framework that we believe is of independent interest. We give a robust analysis of the classic method of shift-and-invert preconditioning to reduce eigenvector computation to approximately solving a sequence of linear systems. We then apply fast stochastic variance reduced gradient (SVRG) based system solvers to achieve our claims.

at May 30, 2016 12:00 AM UTC

Authors: Jason Crampton, Gregory Gutin, Rémi Watrigant
Download: PDF
Abstract: We introduce a new parameterized complexity method based on an Integer Linear Programming (ILP) approach developed by H.P. Williams (1976, 1988, 1992) using Fourier-Motzkin elimination for Linear Programming. The new method allows us to show that two parameterized problems are fixed-parameter tractable. One of the problems is called Resiliency Checking Problem (RCP) and was introduced by Li et al. (ACM Trans. Inf. Syst. Sec. 2009). Our result for RCP answers an open question we raised in a previous paper, and completes a multivariate complexity classification of the problem. The other problem is Closest String for which we show a resiliency result for the problem extending a fixed-parameter tractability result obtained by Gramm et al. (Algorithmica 2003) using Lenstra's ILP theorem.

at May 30, 2016 12:00 AM UTC

Authors: Oliver J. D. Barrowclough
Download: PDF
Abstract: We present an approach to finding the implicit equation of a planar rational parametric cubic curve, by defining a new basis for the representation. The basis, which contains only four cubic bivariate polynomials, is defined in terms of the B\'ezier control points of the curve. An explicit formula for the coefficients of the implicit curve is given. Moreover, these coefficients lead to simple expressions which describe aspects of the geometric behaviour of the curve. In particular, we present an explicit barycentric formula for the position of the double point, in terms of the B\'ezier control points of the curve. We also give conditions for when an unwanted singularity occurs in the region of interest. Special cases in which the method fails, such as when three of the control points are collinear, or when two points coincide, will be discussed separately.

at May 30, 2016 12:00 AM UTC

Authors: Oliver J. D. Barrowclough, Tor Dokken
Download: PDF
Abstract: In this paper we consider a family of algorithms for approximate implicitization of rational parametric curves and surfaces. The main approximation tool in all of the approaches is the singular value decomposition, and they are therefore well suited to floating point implementation in computer aided geometric design (CAGD) systems. We unify the approaches under the names of commonly known polynomial basis functions, and consider various theoretical and practical aspects of the algorithms. We offer new methods for a least squares approach to approximate implicitization using orthogonal polynomials, which tend to be faster and more numerically stable than some existing algorithms. We propose several simple propositions relating the properties of the polynomial bases to their implicit approximation properties.

at May 30, 2016 12:00 AM UTC

Authors: João Pedro Pedroso, Shiro Ikeda
Download: PDF
Abstract: This paper addresses the problem of maximizing the expected size of a matching in the case of unreliable vertices and/or edges. The assumption is that upon failure, remaining vertices that have not been matched may be subject to a new assignment. This process may be repeated a given number of times, and the objective is to end with the overall maximum number of matched vertices.

The origin of this problem is in kidney exchange programs, going on in several countries, where a vertex is an incompatible patient-donor pair; the objective is to match these pairs so as to maximize the number of served patients. A new scheme is proposed for matching rearrangement in case of failure, along with a prototype algorithm for computing the optimal expectation for the number of matched vertices.

Computational experiments reveal the relevance and limitations of the algorithm, in general terms and for the kidney exchange application.

at May 30, 2016 12:00 AM UTC

Authors: Rémy Belmonte, Yota Otachi, Pascal Schweitzer
Download: PDF
Abstract: Given two graphs $G$ and $H$, we say that $G$ contains $H$ as an induced minor if a graph isomorphic to $H$ can be obtained from $G$ by a sequence of vertex deletions and edge contractions. We study the complexity of Graph Isomorphism on graphs that exclude a fixed graph as an induced minor. More precisely, we determine for every graph $H$ that Graph Isomorphism is polynomial-time solvable on $H$-induced-minor-free graphs or that it is GI-complete. Additionally, we classify those graphs $H$ for which $H$-induced-minor-free graphs have bounded clique-width. These two results complement similar dichotomies for graphs that exclude a fixed graph as an induced subgraph, minor, or subgraph.

at May 30, 2016 12:00 AM UTC

Authors: Nate Veldt, David F. Gleich, Michael W. Mahoney
Download: PDF
Abstract: Many graph-based learning problems can be cast as finding a good set of vertices nearby a seed set, and a powerful methodology for these problems is based on maximum flows. We introduce and analyze a new method for locally-biased graph-based learning called SimpleLocal, which finds good conductance cuts near a set of seed vertices. An important feature of our algorithm is that it is strongly-local, meaning it does not need to explore the entire graph to find cuts that are locally optimal. This method solves the same objective as existing strongly-local flow-based methods, but it enables a simple implementation. We also show how it achieves localization through an implicit L1-norm penalty term. As a flow-based method, our algorithm exhibits several ad- vantages in terms of cut optimality and accurate identification of target regions in a graph. We demonstrate the power of SimpleLocal by solving problems on a 467 million edge graph based on an MRI scan.

at May 30, 2016 12:00 AM UTC

Authors: Erik D. Demaine, Jayson Lynch, Geronimo J. Mirano, Nirvan Tyagi
Download: PDF
Abstract: We initiate the systematic study of the energy complexity of algorithms (in addition to time and space complexity) based on Landauer's Principle in physics, which gives a lower bound on the amount of energy a system must dissipate if it destroys information. We propose energy-aware variations of three standard models of computation: circuit RAM, word RAM, and transdichotomous RAM. On top of these models, we build familiar high-level primitives such as control logic, memory allocation, and garbage collection with zero energy complexity and only constant-factor overheads in space and time complexity, enabling simple expression of energy-efficient algorithms. We analyze several classic algorithms in our models and develop low-energy variations: comparison sort, insertion sort, counting sort, breadth-first search, Bellman-Ford, Floyd-Warshall, matrix all-pairs shortest paths, AVL trees, binary heaps, and dynamic arrays. We explore the time/space/energy trade-off and develop several general techniques for analyzing algorithms and reducing their energy complexity. These results lay a theoretical foundation for a new field of semi-reversible computing and provide a new framework for the investigation of algorithms.

at May 30, 2016 12:00 AM UTC

Let $G=(V,E)$ be a connected undirected graph with $k$ vertices. Suppose that on each vertex of the graph there is a player having an $n$-bit string. Each player is allowed to communicate with its neighbors according to an agreed communication protocol, and the players must decide, deterministically, if their inputs are all equal. What is the minimum possible total number of bits transmitted in a protocol solving this problem ? We determine this minimum up to a lower order additive term in many cases (but not for all graphs). In particular, we show that it is $kn/2+o(n)$ for any Hamiltonian $k$-vertex graph, and that for any $2$-edge connected graph with $m$ edges containing no two adjacent vertices of degree exceeding $2$ it is $mn/2+o(n)$. The proofs combine graph theoretic ideas with tools from additive number theory.

at May 29, 2016 03:33 PM UTC

Forwarding an announcement by Oded Goldreich:

I would like to seek the help of this community regarding my forthcoming book Introduction to Property Testing (see Specifically, I would be grateful for feedback regarding any aspect and part of the current text, although detailed comments are likely to be more helpful at this time than suggestions for drastic and/or structural changes. Please do not shy from indicating relevant works that may be mentioned (rather than described in detail), since it is quite possible that I was not aware of them or forgot to mention them (rather than chose not to include a detailed description due to various considerations).

Since I am likely to continue revising the text and posting the revisions on the website, please indicate the text-locations to which you refer in a manner that is most robust to revision (e.g., indicate relative location with respect to sectioning and/or theorem-environment numbers rather than with respect to page numbers).

by Clement Canonne at May 29, 2016 05:33 AM UTC

New results on computing with modular gates


Shiteng Chen and Periklis Papakonstaninou have just written an interesting paper on modular computation. Its title, “Depth Reduction for Composites,” means converting a depth-{d}, size-{s} {\mathsf{ACC^0}} circuit into a depth-2 circuit that is not too much larger in terms of {d} as well as {s}.

Today Ken and I wish to talk about their paper on the power of modular computation.

One of the great mysteries in computation, among many others, is: what is the power of modular computation over composite numbers? Recall that a gate {\mathsf{MOD}_{r}(x)} outputs {1} if {(x_{1}+\cdots+x_{n)} \equiv 0 \bmod r} and {0} otherwise. It is a simple computation: Add up the inputs modulo {r} and see if the sum is {0}. If so output {1}, else output {0}. This can be recognized by a finite-state automaton with {r} states. It is not a complex computation by any means.

But there lurk in this simple operation {\mathsf{MOD}_{r}} some dark secrets. When {r} is a prime the theory is fairly well understood. There remain some secrets but by Fermat’s Little Theorem a {\mathsf{MOD}_r} gate has the same effect as a polynomial. In general, when {r} is composite, this is not true. This makes understanding {\mathsf{MOD}} gates over composites much harder: simply because polynomials are easy to handle compared to other functions. As I once heard someone say:

“Polynomials are our friends.”

Chen and Papakonstaninou (CP) increase our understanding of modular gates by proving a general theorem about the power of low depth circuits with modular gates. This theorem is an exponential improvement over previous results when the depth is regarded as a parameter rather than constant. Their work also connects with the famous work of Ryan Williams on the relation between {\mathsf{NEXP}} and {\mathsf{ACC^0}}.

Main Theorem

We will just state their main result and then state one of their key lemmas. Call a circuit of {\mathsf{AND}}, {\mathsf{OR}}, {\mathsf{NOT}}, and {\mathsf{MOD}_{r}} gates (for some {r}) an {\mathsf{ACC}}-circuit.

Theorem 1 There is an efficient algorithm that given an {\mathsf{ACC}} circuit of depth {d}, input length {n}, and size {s \ge n}, outputs a depth-2 circuit of the form {\mathsf{SYM}\circ\mathsf{AND}} of size {2^{(log s)^{O(d)}}}, where {\mathsf{SYM}} denotes some gate whose output depends only on the number of {1}s in its input.

This type of theorem is a kind of normal-form theorem. It says that any circuit of a certain type can be converted into a circuit of a simpler type, and this can be done without too much increase in size. In complexity theory we often find that it is very useful to replace a complicated type of computational circuit with a much cleaner type of circuit even if the new circuit is bigger. The import of such theorems is not that the conversion can happen, but that it can be done in a manner that does not blow up the size too much.

This happens all through mathematics: finding normal forms. What makes computational complexity so hard is that the conversion to a simpler type often can be done easily—but doing so without a huge increase in size is the rub. For example, every map

\displaystyle  f \colon A \rightarrow \mathbb{Z},

can be easily shown to be equal to an integer-valued polynomial with coefficients in {\mathbb{Q}} provided {A} is a finite subset of {\mathbb{Z}^{n}}. For every point {a = (a_1,\dots,a_n) \in A}, set

\displaystyle  g_a(x_1,\dots,x_n) = \prod_{i=1}^n \prod_{b_i \neq a_i} (x_i - b_i),

where the inner product is over the finitely many {b_i} that appear in the {i}-th place of some member of {A}. Then {v_a = g_a(a_1,\dots,a_n)} is an integer and is the only nonzero value of {g_a} on {A}. We get

\displaystyle  f'(x_1,\dots,x_n) = \sum_{a \in A}\frac{f(a)}{v_a}g_a(x_1,\dots,x_n),

which is a polynomial that agrees with {f} on {A}.

Well, this is easy but brutish—and exponential size if {A} is. The trick is to show that when {f} is special in some way then the size of the polynomial is not too large.

Lemma 5

One of the key insights of CP is a lemma, Lemma 5 in their paper, that allows us to replace a product of many {\mathsf{MOD}} gates by a summation. We have changed variables in the statement around a little; see the paper for the full statement and context.

Lemma 5 Let {x_{1},\dots,x_{n}} be variables over the integers and let {r,q} be relatively prime. Then there exist {m \leq r^{n+1}} integral linear combinations {y_{1},\dots,y_{m}} of the variables and integer coefficients {c_{j} \in [q]} so that

\displaystyle  \prod_{1 \le i \le n} \mathsf{MOD}_{r}(x_{i}) = \left(\sum_{1 \le j \le m} c_{j}\mathsf{MOD}_{r}(y_{j})\right) \bmod{q}.

The value of {r} can be composite. The final modulus can be {s = qr} in place of {q} and this helps in circuit constructions. Three points to highlight—besides products being replaced by sums—are:

  1. The bound {m \leq r^{n+1}} on the number of terms in the sum depends only on {r}, not {q} (or {s}); this may have other uses.

  2. The arithmetic of the sum is over an extension of {r} to {s}.

  3. The coefficients are integral. That is, the conclusion is doing more than just linearizing with complex coefficients, which as they remark in their proof would be easier. This also helps in building circuits where bits set to {1} are being counted.

Further all of this can be done in a uniform way, so the lemma can be used in algorithms. This is important for their applications. Note this is a type of normal form theorem like we discussed before. It allows us to replace a product by a summation. The idea is that going from products to sums is often a great savings. Think about polynomials: the degree of a multi-variate polynomial is a often a better indicator of its complexity of a polynomial than its number of terms. It enables them to remove layers of large {\mathsf{AND}} gates that were implementing the products (Lemma 8 in the paper) and so avoids the greatest source of size blowup in earlier constructions.

A final point is that the paper makes a great foray into mixed-modulus arithmetic, coupled with the use of exponential sums. This kind of arithmetic is not so “natural” but is well suited to building circuits. Ken once avoided others’ use of mixed-modulus arithmetic by introducing new variables—see the “additive” section of this post which also involves exponential sums.

Open Problems

The result of CP seems quite strong. I am, however, very intrigued by their Lemma 5. It seems that there should be other applications of this lemma. Perhaps we can discover some soon.

by RJLipton+KWRegan at May 28, 2016 04:05 PM UTC

We obtain a new depth-reduction construction, which implies a super-exponential improvement in the depth lower bound separating $NEXP$ from non-uniform $ACC$. In particular, we show that every circuit with $AND,OR,NOT$, and $MOD_m$ gates, $m\in\mathbb{Z}^+$, of polynomial size and depth $d$ can be reduced to a depth-$2$, $SYM\circ AND$, circuit of size $2^{{(\log n)}^{O(d)}}$. This is an exponential size improvement over the traditional Yao-Beigel-Tarui, which has size blowup $2^{{(\log n)}^{2^{O(d)}}}$. Therefore, depth-reduction for composite $m$ matches the size of the Allender-Hertrampf construction for primes from 1989. One immediate implication of depth reduction is an improvement of the depth from $o(\log\log n)$ to $o(\log n/\log\log n)$, in Williams' program for $ACC$ circuit lower bounds against $NEXP$. This is just short of $O(\log n/\log\log n)$ and thus pushes William's program to the $NC^1$ barrier, since $NC^1$ is contained in $ACC$ of depth $O(\log n/\log\log n)$. A second, but non-immediate, implication regards the strengthening of the $ACC$ lower bound in the Chattopadhyay-Santhanam interactive compression setting.

at May 28, 2016 05:27 AM UTC

I generally avoid movies about mathematicians, or mathematics.

I didn't watch Beautiful Mind, or even the Imitation game. Often, popular depiction of mathematics and mathematicians runs as far away from the actual mathematics as possible, and concocts all kinds of strange stories to make a human-relatable tale.

Not that there's anything wrong with that, but it defeats the point of talking about mathematics in the first place, by signalling it as something less interesting.

So I was very worried about going to see The Man Who Knew Infinity, about Srinivas Ramanujan and his collaboration with G. H. Hardy. In addition to all of the above, watching movies about India in the time of the British Raj still sets my teeth on edge.

To cut a long story short, I was happy to be proven completely wrong. TMWKI is a powerful and moving depiction of someone who actually deserves the title of genius. The movie focuses mostly on the time that Ramanujan spent at Cambridge during World War I working with Hardy. There are long conversations about the nature of intuition and proof that any mathematician will find exquisitely familar, and even an attempt to explain the partition function. The math on the boards is not hokey at all (I noticed that Manjul Bhargava was an advisor on the show).

You get a sense of a real tussle between minds: even though the actual discussions of math were only hinted at, the way Hardy and Ramaujan (and Littlewood) interact is very realistic. The larger context of the war, the insular environment of Cambridge, and the overt racism of the British during that period are all signalled without being overbearing, and the focus remains on the almost mystical nature of Ramanujan's insights and the struggle of a lifelong atheist who finally discovers something to believe in.

It took my breath away. Literally. Well done.

by Suresh Venkatasubramanian ( at May 27, 2016 06:35 PM UTC

In earlier posts I proposed a homological approach to the Erdos-Rado sunflower conjecture.  I will describe again this approach in the second part of this post. Of course, discussion of other avenues for the study of the conjecture are welcome. The purpose of this post is to discuss another well known problem for which a related  homological approach,  might be relevant.  The problem is the Turan (4,3) problem from 1940.

We will not regard attacks on the sunflower conjecture based on the recent solution of the cap set problem and the Erdos Szemeredi sunflower conjecture (which is a weaker version of the Erdos-Rado conjecture that we considered in post 5) as part of the present polymath10 project, but, of course, I will be happy to hear also reports on progress or comments on these directions. Some updates on this story: Eric Naslund and Will Sawin gave a direct proof based on the polynomial method for the Erdos-Szemeredi sunflower conjecture, and an even  stronger result is given by Naslund here. (Eric also has stronger quantitative bounds for Erdos-Szemeredi based on bounds for cap sets.)   More cap set updates are added to this post, and can be found in the comment threads here and here.

Turan’s (4,3) problem

Turan’s 1940 problem is very easy to state.

What is the minimum of edges in a 3-uniform hypergraph on n vertices with the property that every four vertices span at least one triangle? 

We talked about the problem (and a little about the homological approach to it) in this post and this post.

Four things that the Erdos-Rado sunflower problem and the Turan (4,3) problem have in common.

4. 1000 dollars or so Erdos prize

If I remember correctly, the Turan’s problem is the only question not asked by Erdos himself for which he offered a monetary award.

3.  The homological approach  might be relevant.

This is what this post is going to be about. But while this connection is still tentative and speculative, the next connections between the two problems are solid.

2. Sasha Razborov

Sasha used the Erdos-Rado sunflower theorem in his famous theorem on superpolynomial lower bounds for monotone circuits, and his flag-algebra theory have led to remarkable progress and the best known upper bound for the Turan (4,3) problem. (See here and here .)

1. Sasha Kostochka

Sasha holds the best known upper bound  for the sunflower conjecture and he found a large class of examples for the equality cases for the Turan (4,3) conjecture.

Quasi-isomorphism of hypergraphs

Compound matrices, weak isomorphism and dominance.

Let X=(x_{ij})_{1 \le i \le n, 1 \le j \le n} be a generic matrix. The k-th compound matrix C_k(X) is the matrix of k by k minors. Namely, C_k(X)=x_{ST}, S,T \in {{[n]} \choose {k}} where x_{ST}=det(x_{ij})_{i \in S,j\in T}.

Given two k-unform hypergraphs F,G we say that F and G are weakly isomorphic if the m\times m minor C_{F,G}(X) of C_k(X) whose rows and columns correspond to sets in F and G respectively is non-singular. (It is fairly easy to see that if F and G are isomorphic then they are weakly isomorphic. This relies on the condition that X is generic.) We will say that F dominates G if  |F|\ge |G| and C_{F,G}(X) is full rank. Thus, F and G are weakly isomorphic if each dominates the other.

A class of matroids defined on hypergraphs

Let G(k,r,n) be the k-uniform hypergraph which consists of all k-subsets of [n] that intersect [r]. For a k-uniform hypergraph F on the vertex set [n] let rank_r(F) = rank C_{F,G(k,r,n)}. For the complete k-uniform hypergraph K on n vertices (n \ge r) rank_r(K)={{n}\choose {k}} - {{n-r} \choose {k}}.

 Homological approach to Turan’s (4,3) problem.

We refer to a 3-uniform hypergraph  with the property that every four vertices span at least one triangle as a Turan (4,3)-hypergraph.

Conjecture: If F is a Turan (4,3)-hypergraph with n vertices then

rank_r(F) \ge r {{n-r-1}\choose {2}}.

This conjecture is a refinement of Turan’s conjecture. (The conjectured 1940 lower bound by Turan can be written as  \max (r{{n-r-1} \choose {2}}: r\ge 1).) It is known for r=1 (see this post) and an analogous statement is known for Turan (3,2)-graphs.

We would like to find even stronger algebraic statements which amounts not only to upper bounds on certain homology-like groups but to stronger statements about vanishing of certain homology-like  groups.

I am also curious about

Question: Are all extremal examples with n vertices for the Turan (4,3) problem quasi-isomorphic? If this is the case we can also conjecture that every Turan (4,3) hypergraph dominates  Turan’s example on the same number of vertices.

I hope to be able to present some experimental data on these problems.

Algebraic shifting

A family F of k-subsets of [n] is shifted if whenever S \in F and R is obtained by replacing an element by a smaller element then R \in F.  It can be shown that two shifted families of the same size are weakly isomorphic only if they are equal! We can use our compound matrix to describe an operation (in fact, several operations) called shifting which associated to a family F a shifted family \Delta_T(F).  Suppose that |F|=m. \Delta (F) is the lexicographically smallest family of sets which is weakly isomorphic to F. In more details: we first consider a total ordering T on k-subsets of [n]. Then we greedily  build a hypergraph which is dominated by F.  When we reach m sets we obtain a  hypergraph \Delta_T(F) weakly isomorphic to F.

Now, if the total ordering is the lexicographic order on {{[n]} \choose {k}} then we denote \Delta(F)=\Delta_T(F)) and call \Delta(F) the “algebraic shifting” of F. In this case, it can be shown that the resulting family is shifted.

Also of special importance is the case that T=RL is the reverse lexicographic order.

For sets of integers of size k, the lexicographic order refers to the lexicographic order when we ordered the elements of every set from increasingly, and the reverse lexicographic order is the lexicographic order when we order the elements decreasingly.

From 12<13<14<15<…<21<22<…<31<32<… we get

\{1,2\} <_L \{1,3\} <_L \{1,4\} \dots <_L \{ 2,3\} <_L \{2,4\} <_L \dots

and from  21<31<32<41<42<43<51<52<…  we get

\{1,2\} <_{RL} \{1,3\}<_{RL}\{2,3\}<_{RL}\{1,4\}\dots

We mention again some connection with acyclicity and homology: F  is acyclic if all sets in \Delta (F) contains ‘1’. F is [r,1]-acyclic iff all sets in in \Delta (F) intersect [r]. F is [m,m]-acyclic iff all sets in \Delta(F) contains [r]. For general b,c, [b,c]-acyclicity is not expressed by those two versions of algebraic shifting, however, F is [s,k]-cyclic if \Delta_{RL}(F) \subset {{[s]}\choose{k}}.

The (current) homological approach to the Sunflower problem: a reminder.

Our ultimate conjecture is:

Main Conjecture:  If F has no sunflower of size r then it is [rk,k]-acyclic. (I.e., Z_{k-1}[(rk,k](K)=0.)

An equivalent formulation in terms of reverse lexicographic shifting is:

(**) \Delta_{RL}(F) \subset {{[rk]}\choose{k}}.

Our current proposal  is to use the following theorem and (a greatly modify) Conjecture B. (For general families.)

Theorem: Let F is a family of k-sets without a sunflower of size r. Then

(*) For every family of i-sets F' which is the link of a set of size k-i (including the case F'=F) , Every set in \Delta _{RL}(F') intersect [(r-1)i].

Conjecture B (from post 4, greatly modified from the one discussed in posts 2,3): For a family F of k-sets satisfying (*) we have

(**) \Delta_{RL}(F) \subset {{[rk]}\choose{k}}.

Also here, I hope to be able to present some experimental data soon.

by Gil Kalai at May 27, 2016 08:11 AM UTC

We provide new query complexity separations against sensitivity for total Boolean functions: a power 3 separation between deterministic (and even randomized or quantum) query complexity and sensitivity, and a power 2.1 separation between certificate complexity and sensitivity. We get these separations by using a new connection between sensitivity and a seemingly unrelated measure called one-sided unambiguous certificate complexity ($UC_{\min}$). Finally, we show that $UC_{\min}$ is lower-bounded by fractional block sensitivity, which means we cannot use these techniques to get a super-quadratic separation between bs(f) and s(f).

at May 27, 2016 07:30 AM UTC

Authors: Camille Marchet, Antoine Limasset, Lucie Bittner, Pierre Peterlongo
Download: PDF
Abstract: Genomic and metagenomic fields, generating huge sets of short genomic sequences, brought their own share of high performance problems. To extract relevant pieces of information from the huge data sets generated by current sequencing techniques, one must rely on extremely scalable methods and solutions. Indexing billions of objects is a task considered too expensive while being a fundamental need in this field. In this paper we propose a straightforward indexing structure that scales to billions of element and we propose two direct applications in genomics and metagenomics. We show that our proposal solves problem instances for which no other known solution scales-up. We believe that many tools and applications could benefit from either the fundamental data structure we provide or from the applications developed from this structure.

at May 27, 2016 01:01 AM UTC

Authors: Jakub Pachocki
Download: PDF
Abstract: We show that schemes for sparsifying matrices based on iteratively resampling rows yield guarantees matching classic 'offline' sparsifiers (see e.g. Spielman and Srivastava [STOC 2008]).

In particular, this gives a formal analysis of a scheme very similar to the one proposed by Kelner and Levin [TCS 2013].

at May 27, 2016 01:01 AM UTC

Authors: Ashish Goel, David T. Lee
Download: PDF
Abstract: Though deliberation is a critical component of democratic decision-making, existing deliberative processes do not scale to large groups of people. Motivated by this, we propose a model in which large-scale decision-making takes place through a sequence of small group interactions. Our model considers a group of participants, each having an opinion which together form a graph. We show that for median graphs, a class of graphs including grids and trees, it is possible to use a small number of three-person interactions to tightly approximate the wisdom of the crowd, defined here to be the generalized median of participant opinions, even when agents are strategic. Interestingly, we also show that this sharply contrasts with small groups of size two, for which we prove an impossibility result. Specifically, we show that it is impossible to use sequences of two-person interactions satisfying natural axioms to find a tight approximation of the generalized median, even when agents are non-strategic. Our results demonstrate the potential of small group interactions for reaching global decision-making properties.

at May 27, 2016 01:13 AM UTC

Authors: Omer Gold, Micha Sharir
Download: PDF
Abstract: We give improved algorithmic time bounds for two fundamental problems, and establish a new complexity connection between them. The first is computing dominance product: given a set of $n$ points $p_1,\ldots, p_n$ in $\mathbb{R}^d$, compute a matrix $D$, such that $D[i,j] = \bigl| \{k \mid p_i[k] \leq p_j[k]\} \bigr|$; this is the number of coordinates at which $p_j$ dominates $p_i$. Dominance product computation has often been applied in algorithm design over the last decade.

The second problem is the $L_\infty$ Closest Pair in high dimensions: given a set $S$ of $n$ points in $\mathbb{R}^d$, find a pair of distinct points in $S$ at minimum distance under the $L_\infty$ metric. When $d$ is constant, there are efficient algorithms that solve this problem, and fast approximate solutions are known for general $d$. However, obtaining an exact solution in very high dimensions seems to be much less understood. We significantly simplify and improve previous results, showing that the problem can be solved by a deterministic strongly-polynomial algorithm that runs in $O(DP(n,d)\log n)$ time, where $DP(n,d)$ is the time bound for computing the dominance product for $n$ points in $\mathbb{R}^d$. For integer coordinates from some interval $[-M, M]$, and for $d=n^r$ for some $r > 0 $, we obtain an algorithm that runs in $\tilde{O}\left(\min\{Mn^{\omega(1,r,1)},\, DP(n,d)\}\right)$ time, where $\omega(1,r,1)$ is the exponent of multiplying an $n \times n^r$ matrix by an $n^r \times n$ matrix.

at May 27, 2016 12:00 AM UTC

In the fall we point to theory jobs, in the spring we see who got them. How is the CS enrollment explosion affecting the theory job market? We've seen some big name moves but that's only part of the picture.

Like last year and years past I created a fully editable Google Spreadsheet to crowd source who is going where. Ground rules:
  • I set up separate sheets for faculty, industry and postdoc/visitors.
  • People should be connected to theoretical computer science, broadly defined.
  • Only add jobs that you are absolutely sure have been offered and accepted. This is not the place for speculation and rumors.
  • You are welcome to add yourself, or people your department has hired.
This document will continue to grow as more jobs settle. So check it often.


by Lance Fortnow ( at May 26, 2016 12:23 PM UTC

Our good colleague and friend Zoltán Ésik passed away suddenly yesterday afternoon in the hotel room where he was staying with his wife during a visit to our group at Reykjavik University. He had delivered a survey talk at Reykjavik University on the Equational Logic of Fixed Point Operations on Tuesday and we were making plans for the coming days.

Zoltán was a scientist of the highest calibre; he was one of the prime movers in the monumental development of Iteration Theories, amongst many other achievements. He had served the EATCS as a member of its Council for many years, had recently been named as one of the 2016 EATCS Fellows and he had been a member of the Presburger Award Committee for the last two years.

There is much more to be said about his scientific achievements and warm personality, but this will have to wait for better times.

R.I.P. Zoltán. 

by Luca Aceto ( at May 26, 2016 12:17 PM UTC

SODA PC chair Phil Klein asked me to publicize this quick announcement because of delays in getting this information online in a more official way: for next January's SODA (ACM-SIAM Symposium on Discrete Algorithms) in Barcelona, the submission deadlines will be July 6 (short abstract and paper registration) and July 13 (full submission).

For now, you can visit for the basic information (deadlines, submission site, and program committee).

at May 26, 2016 03:11 AM UTC

Authors: Shiqiang Wang, Murtaza Zafer, Kin K. Leung
Download: PDF
Abstract: Mobile edge computing is a new cloud computing paradigm which makes use of small-sized edge-clouds to provide real-time services to users. These mobile edge-clouds (MECs) are located in close proximity to users, thus enabling users to seamlessly access applications running on MECs. Due to the co-existence of the core (centralized) cloud, users, and one or multiple layers of MECs, an important problem is to decide where (on which computational entity) to place different components of an application. This problem, known as the application or workload placement problem, is notoriously hard, and therefore, heuristic algorithms without performance guarantees are generally employed in common practice, which may unknowingly suffer from poor performance as compared to the optimal solution. In this paper, we address the application placement problem and focus on developing algorithms with provable performance bounds. We model the user application as an application graph and the physical computing system as a physical graph, with resource demands/availabilities annotated on these graphs. We first consider the placement of a linear application graph and propose an algorithm for finding its optimal solution. Using this result, we then generalize the formulation and obtain online approximation algorithms with polynomial-logarithmic (poly-log) competitive ratio for tree application graph placement. We jointly consider node and link assignment, and incorporate multiple types of computational resources at nodes.

at May 26, 2016 12:43 AM UTC

Authors: Hung T. Nguyen, My T. Thai, Thang N. Dinh
Download: PDF
Abstract: Influence Maximization (IM), that seeks a small set of key users who spread the influence widely into the network, is a core problem in multiple domains. It finds applications in viral marketing, epidemic control, and assessing cascading failures within complex systems. Despite the huge amount of effort, IM in billion-scale networks such as Facebook, Twitter, and World Wide Web has not been satisfactorily solved. Even the state-of-the-art methods such as TIM+ and IMM may take days on those networks.

In this paper, we propose SSA and D-SSA, two novel sampling frameworks for IM-based viral marketing problems. SSA and D-SSA are up to 1200 times faster than the SIGMOD 15 best method, IMM, while providing the same $(1- 1/e-\epsilon)$ approximation guarantee. Underlying our frameworks is an innovative Stop-and-Stare strategy in which they stop at exponential check points to verify (stare) if there is adequate statistical evidence on the solution quality. Theoretically, we prove that SSA and D-SSA are the first approximation algorithms that use (asymptotically) minimum numbers of samples, meeting strict theoretical thresholds characterized for IM. The absolute superiority of SSA and D-SSA are confirmed through extensive experiments on real network data for IM and another topic-aware viral marketing problem, named TVM.

at May 26, 2016 12:41 AM UTC

Authors: Tomáš Masařík, Tomáš Toufar
Download: PDF
Abstract: Edge deletion problems are those where given a graph G and a graph property $\pi$, the goal is to find a subset of edges such that after its removal the graph G will satisfy the property $\pi$. Typically, we want to minimize the number of edges removed. In fair deletion problem we change the objective: we minimize the maximum number of edges incident to a single vertex.

We study the parameterized complexity of fair deletion problems with respect to the structural parameters of the tree-width, the path-width, the size of a minimum feedback vertex set, the neighborhood diversity, and the size of minimum vertex cover of graph G.

We prove the W[1]-hardness of the fair MSO edge-deletion with respect to the first three parameters combined. Moreover, we show that there is no algorithm for fair MSO edge-deletion running in time $n^{o(\sqrt k)}$, where n is the size of the graph and k is the sum of the first three mentioned parameters, provided that the Exponential Time Hypothesis holds.

On the other hand, we provide an FPT algorithm for the fair MSO edge-deletion parameterized by the size of minimum vertex cover and an FPT algorithm for the fair MSO vertex-deletion parameterized by the neighborhood diversity.

at May 26, 2016 12:00 AM UTC

Authors: Marco Attene
Download: PDF
Abstract: The class of models that can be represented by STL files is larger than the class of models that can be printed using additive manufacturing technologies. In this paper such a gap is formalized while providing an unambiguous description of all the mathematical entities involved in the modeling-printing pipeline. Possible defects of an STL file are formally defined and classified, and a fully automatic procedure is described to turn "any" such file into a printable model. The procedure is as exact as possible, meaning that no visible distortion is introduced unless it is strictly imposed by limitations of the printing device. Thanks to such an unprecedented flexibility and accuracy, this algorithm is expected to significantly simplify the modeling-printing process, in particular within the continuously emerging non-professional "maker" communities.

at May 26, 2016 12:45 AM UTC

Phil Klein passed on that there's a delay at SIAM in getting the SODA 2017 CFP up, and of course we want to get out the relevant information out to the community.  So he asked me to post the following:   

SODA 2017: The official SIAM symposium webpage is This page does not yet have the call for papers. (My understanding is that the call for papers has yet to be approved by some SIAM staff who are out this week.) The deadlines are as follows: July 6 (short abstract and paper registration), July 13 (full submission).

The symposium will take place on January 16-19, 2017, in Barcelona, Spain.

For now, you can visit for the basic information (deadlines, submission site, and program committee).

by Michael Mitzenmacher ( at May 25, 2016 04:38 PM UTC

As the third installment of the series in which Fellows of the EATCS provide their advice to the budding TCS researcher, I am posting the advice from Giuseppe Italiano. Happy reading!

The advice I would give to a student interested in TCS There’s a great quote by Thomas Huxley: “Try to learn something about everything and everything about something.” When working through your PhD, you might end up focusing on a narrow topic so that you will fully understand it. That’s really great! But one of the wonderful things about Theoretical Computer Science is that you will still have the opportunity to learn the big picture!

The advice I would give a young researcher in TCS Keep working on the problems you love, but don’t be afraid to learn things outside of your own area. One good way to learn things outside your area is to attend talks (and even conferences) outside your research interests. You should always do that!

A short description of a research topic that excites me at this moment in time (and possibly why) I am really excited by recent results on conditional lower bounds, sparkled by the work of Virginia Vassilevska Williams et al. It is fascinating to see how a computational complexity conjecture such as SETH (Strong Exponential Time Hypothesis) had such an impact on the hardness results for many well-known basic problems. (Editor's notes: You might be interested in the slides for the presentations given at this workshop that was co-located with STOC 2015.)

by Luca Aceto ( at May 25, 2016 11:03 AM UTC

Derandomization of Chernoff bound with union bound is already proven in many papers. We here give another explicit version of it that obtains a construction of size that is arbitrary close to the probabilistic nonconstructive size. We apply this to give a new simple polynomial time constructions of almost $k$-wise independent sets. We also give almost tight lower bounds for the size of $k$-wise independent sets.

at May 25, 2016 09:05 AM UTC

Authors: Cameron Musco, Christopher Musco
Download: PDF
Abstract: We give the first algorithms for kernel matrix approximation that run in time linear in the number of data points and output an approximation which is provably strong enough for use in many downstream learning tasks, including kernel principal component analysis, kernel k-means clustering, kernel ridge regression, and kernel canonical correlation analysis.

Our methods require just $\tilde O(n\cdot k)$ kernel evaluations and $\tilde O(n \cdot k^2)$ additional runtime, where $n$ is the number of training data points and $k$ is a target rank or effective dimensionality parameter. These runtimes are significantly sub-linear in the size of the $n \times n$ kernel matrix and apply to any kernel matrix, without assuming regularity or incoherence conditions.

The algorithms are based on a ridge leverage score Nystr\"om sampling scheme (RLS-Nystr\"om) which was recently shown to yield strong kernel approximations, but which had no efficient implementation. We address this shortcoming by introducing fast recursive sampling methods for RLS-Nystr\"om, while at the same time proving extended approximation guarantees for this promising new method.

at May 25, 2016 12:43 AM UTC

Authors: Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, R. Ryan Williams
Download: PDF
Abstract: Given a set of numbers, the $k$-SUM problem asks for a subset of $k$ numbers that sums to zero. When the numbers are integers, the time and space complexity of $k$-SUM is generally studied in the word-RAM model; when the numbers are reals, the complexity is studied in the real-RAM model, and space is measured by the number of reals held in memory at any point.

We present a time and space efficient deterministic self-reduction for the $k$-SUM problem which holds for both models, and has many interesting consequences. To illustrate:

* $3$-SUM is in deterministic time $O(n^2 \lg\lg(n)/\lg(n))$ and space $O\left(\sqrt{\frac{n \lg(n)}{\lg\lg(n)}}\right)$. In general, any polylogarithmic-time improvement over quadratic time for $3$-SUM can be converted into an algorithm with an identical time improvement but low space complexity as well. * $3$-SUM is in deterministic time $O(n^2)$ and space $O(\sqrt n)$, derandomizing an algorithm of Wang.

* A popular conjecture states that 3-SUM requires $n^{2-o(1)}$ time on the word-RAM. We show that the 3-SUM Conjecture is in fact equivalent to the (seemingly weaker) conjecture that every $O(n^{.51})$-space algorithm for $3$-SUM requires at least $n^{2-o(1)}$ time on the word-RAM.

* For $k \ge 4$, $k$-SUM is in deterministic $O(n^{k - 2 + 2/k})$ time and $O(\sqrt{n})$ space.

at May 25, 2016 12:41 AM UTC

Authors: Rong Ge, Jason D. Lee, Tengyu Ma
Download: PDF
Abstract: Matrix completion is a basic machine learning problem that has wide applications, especially in collaborative filtering and recommender systems. Simple non-convex optimization algorithms are popular and effective in practice. Despite recent progress in proving various non-convex algorithms converge from a good initial point, it remains unclear why random or arbitrary initialization suffices in practice. We prove that the commonly used non-convex objective function for matrix completion has no spurious local minima -- all local minima must also be global. Therefore, many popular optimization algorithms such as (stochastic) gradient descent can provably solve matrix completion with \textit{arbitrary} initialization in polynomial time.

at May 25, 2016 12:42 AM UTC

Authors: Cewei Cui, Zhe Dang
Download: PDF
Abstract: This paper develops two heuristic algorithms to solve graph isomorphism, using free energy encoding. The ?rst algorithm uses four types of encoding re?nement techniques such that every graph can be distinguished by a canonical number computed by the algorithm. The second algorithm injects energy into the graph to conduct individualiza- tion such that the correspondence relation between a pair of isomorphic graphs can be found. The core principle behind the two algorithms is encoding discrete structures as real numbers. A large set of experiments demonstrated the e?ectiveness of our algorithms.

at May 25, 2016 12:43 AM UTC

Authors: Shreyas Sekar, Milan Vojnovic, Se-Young Yun
Download: PDF
Abstract: We consider the problem of maximizing a submodular set function that can be expressed as the expected value of a function of an $n$-size collection of independent random variables with given prior distributions. This is a combinatorial optimization problem that arises in many applications, including the team selection problem that arises in the context of online labour platforms. We consider a class of approximation algorithms that are restricted to use some statistics of the prior distributions to estimate the outputs of value oracle calls, which can be interpreted as test scores. We establish that the existence of test scores that provide an approximation guarantee is equivalent to that a special type of test scores, so called replication test scores, provide this approximation guarantee. We also identify sufficient conditions for replication test scores to provide this approximation guarantee. These sufficient conditions are shown to hold for a large number of models of production, including a monotone concave function of total production, best-shot, and constant elasticity of substitution production function. We also study a more general submodular welfare maximization problem, which accommodates the case of multiple projects, and derive an $\Omega(1/\log(k))$-approximation, algorithm where $k$ is the maximum number of participants in a project. We evaluate the quality of approximation provided by test scores in a case study using data from a popular online labour platform for software development.

at May 25, 2016 12:40 AM UTC

Tomorrow, Wednesday May 25, is the international Towel Day in honor of Douglas Adams, author of the 5-book trilogy “The hitchhiker’s Guide to the Galaxy”. In his book (and his prior 1978 radio series) Adams gave a nice illustration of computational complexity and non uniform computation in his story about the “deep thought” computer who took 7.5 million years to answer the ultimate question of life, the universe, and everything, though today Google’s calculator can do this in 0.66 seconds.

If you want to celebrate towel day in Cambridge, bring your towel to Tselil Schramm’s talk on refuting random constraint satisfaction problems using Sums of Squares in MIT’s algorithms and complexity seminar (4pm, room 32-G575).


by Boaz Barak at May 24, 2016 08:53 PM UTC

(Workshop for women in computational topology in August: see here. For a post about these kinds of workshops see here.)

(I have already posted twice on stuff I saw or heard at the Gathering Conference here and here,)

Meta Point- At the Gathering for Gardner conference I learned lots of math (prob more accuarte to say I learned ABOUT lots of math) that I want to tell you about which is why this is my third post on it, and I post more.

The pamplets of  Lewis Carol: Games, Puzzles, and related pieces: This was mostly puzzles that are by now familiar, but one new (to me) think struck me: an aloof word  is a word where if you change any one letter to anything else then its no longer a word. I think aloof is such a word.

Some talk don't know which one was about the Piet Hein Egg, also called a superegg. The talk (which differs slightly from he page pointed to) said it was a solid whose surface has the equation

(x/a)2.5 + (y/a)2.5 + (z/b)2.5

and its an egg which can stand on its end. (Note the x/a,y/a,z/b- that is correct, not a typo).
(Personal Note: Piet Hein invented Soma Cubes which is a puzzle where you put together 3-d pieces
made of small cubes into a large cube or other shapes. I learned about these in a Martin Gardner column and bought a set. I was very good at this- I put together every figure in the booklet within a week. This was the ONLY sign that I was GOOD at math when I was a kid, though there are many signs that was INTERESTED in math. About 30 years ago my girlfriend at that time and I went to a restaurant and there was a SOMA set on the table, assembled into a cube. I took it apart and she said ``Bill, you'll never be able to put it back together!!!'' I then ``tried'' to and ended up putting together instead a bathtub, a dog, a wall, and a W. But gee, it ``seemed'' like I was fumbling around and couldn't get a cube. ``Gee Bill, I think you've seen this puzzle before''. And who is this insightful girlfriend? My wife of over 20 years!)

Magic Magic Square (Sorry, dont know which talk) Try to construct a 4x4 magic square where (as usual) all rows and columns sum to the same thing. But also try to make all sets of four numbers that form a square (e.g., all four corners) also add to that number. Can you? If you insist on using naturals then I doubt it. Integers I also doubt it. But you CAN do it with rationals. How? If you want to figure it out yourself then DO NOT go to the answer which is at this link: here

Droste Effect: When a picture appears inside itself. For an example and why its called that see here

Black Hole Numbers: If you have a rule that takes numbers to numbers, are there numbers that ALL numbers eventually goto? If so, they are black hole numbers for that rule.

Map a number to the number of letters in its name

20 (twenty) --> 6 (six) --> 3 (three) --> 5 (five) --> four (4) --> four(4) --> ...

It turns out that ANY number eventually goes to 4.

Map a number to the sum of the digits of its divisors

12 has divisors 1,2,3,4,6,12 --> 1+2+3+4+6+1+2=19

19 has divisors 1,19 so --> 1+1+9 = 11

11 has divisors 1,11 so --> 1+1+1 = 3

3 has divisors 1,3 so --> 1+3=4

4 has divisors 1,2,4 so --> 1+2+4=7

7 has divisors 1,7 so --> 1+7=8

8 has divisors 1,2,4,8, --> 15

15 has divisors 1,3,5,15 --> 1+3+5+1+5 = 15

AH. It turns out ALL numbers eventually get to 15.

Boomerang Fractions: Given a fraction f do the following:

x1=1,  x2=1+f, x3- you can either add f to x2 or invert x2. Keep doing this. Your goal is to get back to 1 as soo nas possible.  Here is a paper on it: here. This notion can be generalized: given (s,f) start with s and try to get back so s. Can you always? how long would it take? Upper bounds?

Liar/Truth teller patterns on a square plane b Kotani Yoshiyuki. You have an 4 x 4 grid. Every grid point has a person. They all say ``I have exactly one liar adjacet (left, right, up, or down) to me.''
How many ways can this happen.  This can be massively generalized.

Speed Solving Rubit's cube by Van Grol and Rik. A robot can do it in 0.9 seconds: here.

by GASARCH ( at May 24, 2016 01:33 PM UTC

The very real problem of (un)fairness in algorithmic decision making in general, and machine learning in particular seems to have finally reached the forefront of public attention. Every day there is a new popular article about the topic. Just in the last few weeks, we have seen articles in the Times about built in bias in facebook, and an in-depth ProPublica study about racial bias in statistical models for predicting criminal recidivism. Earlier this month, the White House released a report on the challenges in promoting fairness in Big Data.

The tricky thing is saying something concrete and technical about this problem -- even defining what "fairness" is is delicate. There has been some good technical work in this area that I have long admired from afar -- see e.g. the "FATML" (Fairness and Transparency in Machine Learning) Workshop to get an idea of the range of work being done, and the folks doing it. People like Cynthia DworkMoritz HardtSolon BarocasSuresh VenkatasubramanianSorelle Friedler, Cathy O'Neil, and others have been doing important work thinking about these problems for quite some time. A particularly nice early paper that I recommend everyone interested in the area read is Fairness Through Awareness, by Dwork, Hardt, Pitassi, Reingold, and Zemel. It was first posted online in 2011(!), and in retrospect is quite prescient in its discussion of algorithmic fairness.

So I'm happy to finally have something interesting to say about the topic! My student Matthew JosephMichael KearnsJamie Morgenstern, and I just posted a new paper online that I'm excited about: Fairness in Learning: Classic and Contextual Bandits. I'll mostly let the paper speak for itself, but briefly, we write down a simple but (I think) compelling definition of fairness in a stylized general model of sequential decision making called the "contextual bandit setting". To keep a canonical problem in your mind, imagine the following: There are a bunch of different populations (say racial or socioeconomic groups), and you are a loan officer. Every day, an individual from each population applies for a loan. You get to see the loan application for each person (this is the "context"), and have to decide who to give the loan to. When you give out the loan, you observe some reward (e.g. you see if they paid back the loan), but you don't see what reward you -would- have gotten had you given the loan to someone else. Our fairness condition says roughly that an algorithm is "fair" if it never preferentially gives a loan to a less qualified applicant over a more qualified applicant -- where the quality of an applicant in our setting is precisely the probability that they pay back the loan. (It prohibits discriminating against qualified applicants on an individual basis -- even if  they happen to come from a population that is less credit-worthy on average, or from a population that the bank doesn't understand as well).

It might seem like this definition of fairness is entirely consistent with the profit motivation of a bank -- why would a bank ever want to give a loan to an applicant less likely to pay it back? Indeed, this would be true if the bank had nothing to learn -- i.e. if it already knew the optimal rule mapping loan applications to credit-worthiness. Said another way, implementing the optimal policy is entirely consistent with our fairness definition. Our main conceptual message is that fairness can nevertheless be an obstruction to learning the optimal policy.

What our results say is that "fairness" always has a cost in terms of the optimal learning rate achievable by algorithms in this setting. For some kinds of problems, the cost is mild in that the cost of fairness on the learning rate is only polynomial (e.g. when credit-worthiness is determined by a simple linear regression model on the features of a loan application). On the other hand, for other kinds of problems, the cost of fairness on the learning rate is severe, in that it can slow learning by an exponential factor (e.g. when credit-worthiness is determined by an AND of features in the loan application). Put another way, for the problems in which the cost of fairness is severe, if the bank were to use a fast learning algorithm (absent a fairness constraint), the algorithm might be "unfair" for a very long time, even if in the limit, once it learned the truly optimal policy, it would eventually be fair. One friction to fairness is that we don't live in the limit -- we are always in a state of learning.

by Aaron Roth ( at May 24, 2016 01:18 PM UTC

As second installment of the series in which Fellows of the EATCS provide their advice to the budding TCS researcher, I am posting the advice from David Harel. Enjoy!

Advice I would give to a student interested in TCS:

If you are already enrolled in a computer science program, then unless you feel you are of absolutely stellar theoretical quality and the real world and its problems do not attract you at all, I’d recommend that you spend at least 2/3 of your course efforts on a variety of topics related to TCS but not “theory for the sake of theory”. Take lots of courses on languages, verification AI, databases, systems, hardware, etc. But clearly don’t shy away from pure mathematics. Being well-versed in a variety of topics in mathematics can only do you good in the future. If you are still able to choose a study program, go for a combination: TCS combined with software and systems engineering, for example, or bioinformatics/systems biology. I feel that computer science (not just programing, but the deep underlying ideas of CS and systems) will play a role in the science of the 21st century (which will be the century of the life sciences) similar to that played by mathematics in the science of the 20th century (which was the century of the physical sciences).

Advice I would give a young researcher in TCS:

Much of the above is relevant to young researchers too. Here I would add the following two things. First, if you are doing pure theory, then spend at least 1/3 of your time on problems that are simpler than the real hard one you are trying to solve. You might indeed succeed in settling the P=NP? problem, or the question of whether PTIME on general finite structures is r.e., but you might not. Nevertheless, in the latter case you’ll at least have all kinds of excellent, if less spectacular, results under your belt. Second, if you are doing research that is expected to be of some practical value, go talk to the actual people “out there”: engineers, programmers, system designers, etc. Consult for them, or just sit with them and see their problems first-hand. There is nothing better for good theoretical or conceptual research that may have practical value than dirtying your hands in the trenches.

A short description of a research topic that excites me at this moment in time (and possibly why):

I haven’t done any pure TCS for 25 years, although in work my group and I do on languages and software engineering there is quite a bit of theory too, as is the case in our work on biological modeling. However, for many years, I’ve had a small but nagging itch for trying to make progress on the problem of artificial olfaction ̶ the ability to record and remotely produce faithful renditions of arbitrary odors. This is still a far-from-solved issue, and is the holy grail of the world of olfaction. Addressing it involves chemistry, biology, psychophysics, engineering, mathematics and algorithmics (and is a great topic for young TCS researchers!). More recently, I’ve been thinking about the question of how to test the validity of a candidate olfactory reproduction system, so that we have an agreed-upon criterion of success for when such systems are developed. It is a kind of common-sense question, but one that appears to be very interesting, and not unlike Turing’s 1950 quest for testing AI, even though such systems were nowhere in sight at the time. In the present case, trying to compare testing artificial olfaction to testing the viability of sight and sound reproduction will not work, for many reasons. After struggling with this for quite a while, I now have a proposal for such a test, which is under review.

by Luca Aceto ( at May 24, 2016 11:56 AM UTC

The deadline for AAAI Conference on Human Computation (HCOMP) 2016 is nearly here.  It is an application domain where the depth and reasoning of theory CS folks might find unexpectedly rich outlet. You will see our folks deeply involved in organizing the conference including Arpita G, Sid S, Santosh V,  Jenn W. V, and others. 

The theme for HCOMP 2016 is Interaction:
  • between people and technology that is foundational to human computation
  • between theoretical foundations, experimental work, and engineering
  • between the computational, scientific, and social applications of crowdsourcing
  • between diverse disciplines and perspectives, within our community and beyond
HCOMP strongly believes in inviting, fostering, and promoting broad, interdisciplinary research on crowdsourcing and human computation. Submissions may present principles, studies, and/or applications of systems that rely on programmatic interaction with crowds, or where human perception, knowledge, reasoning, or physical activity and coordination contributes to the operation of computational systems, applications, or services. More generally, we invite submissions from the broad spectrum of related fields and application areas including (but not limited to):

  • human-centered crowd studies: e.g., human-computer interaction, social computing, design, cognitive and behavioral sciences (psychology and sociology), management science, economics, policy, ethics, etc.
  • applications and algorithms: e.g., computer vision, cultural heritage, databases, digital humanities, information retrieval, machine learning, natural language (and speech) processing, optimization, programming languages, systems, etc.
  • crowdsourcing areas: e.g., citizen science, collective action, collective knowledge, crowdsourcing contests, crowd creativity, crowd funding, crowd ideation, crowd sensing, distributed work, freelancer economy, open innovation, microtasks, prediction markets, wisdom of crowds, etc.
To ensure relevance, submissions are encouraged to include research questions and contributions of broad interest to crowdsourcing and human computation, as well as discuss relevant open problems and prior work in the field. When evaluation is conducted entirely within a specific domain, authors are encouraged to discuss how findings might generalize to other communities and application areas using crowdsourcing and human computation.
Full CFP is hereMay 31, 2016: Abstracts (for Full Papers) due. June 7, 2016: Full Papers due. 

by metoo ( at May 23, 2016 09:15 PM UTC