If you’re in New Haven next week, you could do worse than checking out this talk at Yale’s CS Colloquium by my stellar PhD student Mahdi Zamani.

by Jared at April 18, 2015 04:04 PM UTC

If you’re in New Haven next week, you could do worse than checking out this talk at Yale’s CS Colloquium by my stellar PhD student Mahdi Zamani.

by Jared at April 18, 2015 04:04 PM UTC

This interesting article in today’s NYT tells the story of the fad of Tibetan mastiffs as high-end pets in China.

It is an appealing story about social changes, new riches, inequalities, and so on, but it also, finally, explains why I could never find in San Francisco hot pot that tasted like in Beijing:

Instead, earlier this year Nibble and 20 more unlucky mastiffs found themselves stuffed into metal chicken crates and packed onto a truck with 150 other dogs. If not for a band of Beijing animal rights activists who literally threw themselves in front of the truck, Nibble and the rest would have ended up at a slaughterhouse in northeast China where, at roughly $5 a head, they would have been rendered into

hot pot ingredients, imitation leather and the lining for winter gloves.

(Emphasis added)

by luca at April 18, 2015 01:38 AM UTC

My first encounter with the term *algorithm* did not come from Don Knuth. I learned it from the Internal Revenue Service. Sometime in the late 1960s or early 70s the IRS introduced a redesigned Form 1040 based on a principle borrowed from the world of computing: the algorithm. What this meant, I soon discovered, was that the wording of the instructions would be procedural rather than declarative. Instead of “Your tax is 15 percent of the amount on line 42,” we had “Multiply the amount on line 42 by 0.15 and write the result on line 43.” I had expected something more revolutionary, but at least I expanded my vocabulary.

I’ve filled out a lot of 1040s since then, but until yesterday I had never become acquainted with Schedule D (Capital Gains and Losses). What a treat I had waiting for me! Tucked inside the Schedule D instruction book, I found a marvel of labyrinthine arithmetic and logic. The tax worksheet on pages D-15 and D-16 might well be the most complex algorithm that ordinary people are ever asked to perform.

Below is my attempt to represent the worksheet as a data-flow diagram. Inputs (mostly dollar amounts copied from elsewhere in the tax return) are in blue; the eventual output (tax owed) is in red; the flow is mostly from bottom to top. The numbers in the boxes correspond to line numbers in the worksheet.

The directed graph has 82 nodes and 96 edges. Twelve subtractions, seven additions, four multiplications, ten comparisons, and two table lookups. Now *that’s* an algorithm! It’s gnarlier than calculating the date of Easter.

What are the chances that I correctly followed all the steps of this algorithm? What are the chances that the published algorithm correctly implements the intent of the tax code?

by Brian Hayes at April 17, 2015 01:30 AM UTC

My latest arXiv preprint, The Parametric Closure Problem (arXiv:1504.04073, to appear at WADS) concerns an old optimization problem that can be used, among other applications, in the planning process for open-pit mining.

Suppose you have the mining rights to a three-dimensional patch of earth and rock, in which the ore is of a type and depth that make it appropriate to remove the ore by digging down to it from above rather than by tunneling. You can make a three-dimensional model of your mining area, in which different three-dimensional blocks of material might represent ore of different values or worthless overburden (the stuff on top of the ore that you have to remove to get to the ore). Each block has its own value: the profit that can be extracted from its ore minus the cost of digging it out and processing it. Additionally, each block has some blocks above it (maybe staggered in a three-dimensional brick-wall pattern) that have to be removed first before you can get to it. Some blocks are worth digging for; others are buried so deeply under other worthless material that it would cost more to dig them out than you would get in profit from them. How should you go about deciding which blocks to excavate and which to leave in place?

This can be modeled mathematically by the closure problem, in which you have as input a partially ordered set (the blocks of the mine, ordered by which ones have to be excavated first before you can get to which other ones) with weights on each element (the net profit of excavating each block). The goal is to find a downward-closed subset of the partial order (a set of blocks such that, whenever a block is in the set, so is all of its overburden) with maximum total weight. Alternatively, instead of a partial order, you can think about a directed acyclic graph, in which you have to find a set of vertices with no outgoing edges; the problem is essentially the same. It has long been known that this can be solved in polynomial time using a transformation to the minimum cut problem.

Ok, but that assumes that the price of the material you're extracting (gold, say) is fixed. What happens as the price of gold varies? If gold is more expensive, it will be worthwhile to dig deeper for it; if it is cheap enough, you might even prefer to shut down the whole mine. How many different mining plans do you need for different prices of gold, and how can you compute them all? This is an example of a parametric optimization problem, one in which the weight of each element depends continuously on a parameter rather than being a fixed number.

Alternatively, what if you want to optimize a quantity that isn't just a sum of element weights? Suppose, for instance, that it takes a certain up-front cost to extract a block of ore, but that you only get the value of the gold in the ore later. How can you choose a mining plan that maximizes your return-on-investment, the ratio between the profit you expect and the cost you have to pay now? This can also be modeled as a parametric problem, where the weight of a block has the form C × profit − cost for an unknown parameter C. If you can find all the different mining plans that would be obtained by different choices of C, you can then search through them to choose the plan with the optimal return-on-investment, and this turns out to be optimal.

My paper defines the parametric (and bicriterion) closure problems, but I was only able to find polynomial-time solutions (and polynomial bounds on the number of different solutions to be found) for some special cases of partial orders, including series-parallel partial orders, semiorders, and orders of bounded width. However, the partial orders arising in the mining problem are unlikely to be any of these, so a lot more remains to be done. In particular I'd like to know whether there can exist a partial order whose parametric closure problem has exponentially many solutions, or whether they all have only a polynomial number of solutions. (Anything in between would also be interesting.)

Incidentally, it's tempting to try to generalize closures of partial orders to feasible sets of antimatroids, and ask for an algorithm that can find the maximum weight feasible set. Unfortunately, this antimatroid closure problem is NP-complete. Consider, for instance, an antimatroid defined from a family of sets*S*_{i} in which there is one antimatroid element *x*_{i} corresponding to each set *S*_{i}, another antimatroid element *y*_{j} corresponding to each element of a set, and the feasible sets consist of any subset of the *x*_{i}'s together with any of the *y*_{j}'s that are covered by sets among the chosen *x*_{i}'s. If we give the *x*_{i}'s small equal negative weights and the *y*_{j}'s big equal positive weights, then the optimal feasible set is given by the optimal solution to a set cover problem. Although this complexity result doesn't prove anything about the number of solutions to the corresponding parametric problem, it makes me think that the parametric antimatroid problem is likely to be exponential.

Suppose you have the mining rights to a three-dimensional patch of earth and rock, in which the ore is of a type and depth that make it appropriate to remove the ore by digging down to it from above rather than by tunneling. You can make a three-dimensional model of your mining area, in which different three-dimensional blocks of material might represent ore of different values or worthless overburden (the stuff on top of the ore that you have to remove to get to the ore). Each block has its own value: the profit that can be extracted from its ore minus the cost of digging it out and processing it. Additionally, each block has some blocks above it (maybe staggered in a three-dimensional brick-wall pattern) that have to be removed first before you can get to it. Some blocks are worth digging for; others are buried so deeply under other worthless material that it would cost more to dig them out than you would get in profit from them. How should you go about deciding which blocks to excavate and which to leave in place?

This can be modeled mathematically by the closure problem, in which you have as input a partially ordered set (the blocks of the mine, ordered by which ones have to be excavated first before you can get to which other ones) with weights on each element (the net profit of excavating each block). The goal is to find a downward-closed subset of the partial order (a set of blocks such that, whenever a block is in the set, so is all of its overburden) with maximum total weight. Alternatively, instead of a partial order, you can think about a directed acyclic graph, in which you have to find a set of vertices with no outgoing edges; the problem is essentially the same. It has long been known that this can be solved in polynomial time using a transformation to the minimum cut problem.

Ok, but that assumes that the price of the material you're extracting (gold, say) is fixed. What happens as the price of gold varies? If gold is more expensive, it will be worthwhile to dig deeper for it; if it is cheap enough, you might even prefer to shut down the whole mine. How many different mining plans do you need for different prices of gold, and how can you compute them all? This is an example of a parametric optimization problem, one in which the weight of each element depends continuously on a parameter rather than being a fixed number.

Alternatively, what if you want to optimize a quantity that isn't just a sum of element weights? Suppose, for instance, that it takes a certain up-front cost to extract a block of ore, but that you only get the value of the gold in the ore later. How can you choose a mining plan that maximizes your return-on-investment, the ratio between the profit you expect and the cost you have to pay now? This can also be modeled as a parametric problem, where the weight of a block has the form C × profit − cost for an unknown parameter C. If you can find all the different mining plans that would be obtained by different choices of C, you can then search through them to choose the plan with the optimal return-on-investment, and this turns out to be optimal.

My paper defines the parametric (and bicriterion) closure problems, but I was only able to find polynomial-time solutions (and polynomial bounds on the number of different solutions to be found) for some special cases of partial orders, including series-parallel partial orders, semiorders, and orders of bounded width. However, the partial orders arising in the mining problem are unlikely to be any of these, so a lot more remains to be done. In particular I'd like to know whether there can exist a partial order whose parametric closure problem has exponentially many solutions, or whether they all have only a polynomial number of solutions. (Anything in between would also be interesting.)

Incidentally, it's tempting to try to generalize closures of partial orders to feasible sets of antimatroids, and ask for an algorithm that can find the maximum weight feasible set. Unfortunately, this antimatroid closure problem is NP-complete. Consider, for instance, an antimatroid defined from a family of sets

at April 17, 2015 01:08 AM UTC

**Authors: **Christian Glasser, Peter Jonsson, Barnaby Martin **Download:** PDF**Abstract: **We study interactions between Skolem Arithmetic and certain classes of
Constraint Satisfaction Problems (CSPs). We revisit results of Glass er et al.
in the context of CSPs and settle the major open question from that paper,
finding a certain satisfaction problem on circuits to be decidable. This we
prove using the decidability of Skolem Arithmetic. We continue by studying
first-order expansions of Skolem Arithmetic without constants, (N;*), where *
indicates multiplication, as CSPs. We find already here a rich landscape of
problems with non-trivial instances that are in P as well as those that are
NP-complete.

at April 17, 2015 12:40 AM UTC

**Authors: **Merav Parter, David Peleg **Download:** PDF**Abstract: **This paper initiates the study of fault resilient network structures that mix
two orthogonal protection mechanisms: (a) {\em backup}, namely, augmenting the
structure with many (redundant) low-cost but fault-prone components, and (b)
{\em reinforcement}, namely, acquiring high-cost but fault-resistant
components. To study the trade-off between these two mechanisms in a concrete
setting, we address the problem of designing a $(b,r)$ {\em fault-tolerant} BFS
(or $(b,r)$ FT-BFS for short) structure, namely, a subgraph $H$ of the network
$G$ consisting of two types of edges: a set $E' \subseteq E$ of $r(n)$
fault-resistant {\em reinforcement} edges, which are assumed to never fail, and
a (larger) set $E(H) \setminus E'$ of $b(n)$ fault-prone {\em backup} edges,
such that subsequent to the failure of a single fault-prone backup edge $e \in
E \setminus E'$, the surviving part of $H$ still contains an BFS spanning tree
for (the surviving part of) $G$, satisfying $dist(s,v,H\setminus \{e\}) \leq
dist(s,v,G\setminus \{e\})$ for every $v \in V$ and $e \in E \setminus E'$. We
establish the following tradeoff between $b(n)$ and $r(n)$: For every real
$\epsilon \in (0,1]$, if $r(n) = {\tilde\Theta}(n^{1-\epsilon})$, then $b(n) =
{\tilde\Theta}(n^{1+\epsilon})$ is necessary and sufficient.

at April 17, 2015 12:41 AM UTC

**Authors: **Moein Falahatgar, Ashkan Jafarpour, Alon Orlitsky, Venkatadheeraj Pichapathi, Ananda Theertha Suresh **Download:** PDF**Abstract: **There has been considerable recent interest in distribution-tests whose
run-time and sample requirements are sublinear in the domain-size $k$. We study
two of the most important tests under the conditional-sampling model where each
query specifies a subset $S$ of the domain, and the response is a sample drawn
from $S$ according to the underlying distribution.

For identity testing, which asks whether the underlying distribution equals a specific given distribution or $\epsilon$-differs from it, we reduce the known time and sample complexities from $\tilde{\mathcal{O}}(\epsilon^{-4})$ to $\tilde{\mathcal{O}}(\epsilon^{-2})$, thereby matching the information theoretic lower bound. For closeness testing, which asks whether two distributions underlying observed data sets are equal or different, we reduce existing complexity from $\tilde{\mathcal{O}}(\epsilon^{-4} \log^5 k)$ to an even sub-logarithmic $\tilde{\mathcal{O}}(\epsilon^{-5} \log \log k)$ thus providing a better bound to an open problem in Bertinoro Workshop on Sublinear Algorithms [Fisher, 2004].

at April 17, 2015 12:00 AM UTC

**Authors: **David Eppstein **Download:** PDF**Abstract: **We define the parametric closure problem, in which the input is a partially
ordered set whose elements have linearly varying weights and the goal is to
compute the sequence of minimum-weight lower sets of the partial order as the
weights vary. We give polynomial time solutions to many important special cases
of this problem including semiorders, reachability orders of bounded-treewidth
graphs, partial orders of bounded width, and series-parallel partial orders.
Our result for series-parallel orders provides a significant generalization of
a previous result of Carlson and Eppstein on bicriterion subtree problems.

at April 17, 2015 12:44 AM UTC

**Authors: **Mahmoud Abo Khamis, Hung Q. Ngo, Christopher Ré, Atri Rudra **Download:** PDF**Abstract: **We define and study the $\sf FAQ$ ($\bf F$unctional $\bf A$ggregate $\bf
Q$uery) problem, which encompasses many frequently asked questions in
constraint satisfaction, databases, matrix operations, probabilistic graphical
models and logic. This is our main conceptual contribution.

We then present a simple algorithm called $\sf InsideOut$ to solve this general problem. $\sf InsideOut$ is a variation of the traditional dynamic programming approach for constraint programming based on variable elimination. Our variation adds a couple of simple twists to basic variable elimination to deal with the generality of $\sf FAQ$, as well as to take full advantage of the (relatively) recent fractional edge cover framework of Grohe and Marx, and of the analysis of recent worst-case optimal relational join algorithms.

As is the case with constraint programming and graphical model inference, to make $\sf InsideOut$ run efficiently we need to solve an optimization problem to compute an appropriate variable ordering. Our main technical contribution is a precise characterization of when a variable ordering is "semantically equivalent" to the ordering given by the input $\sf FAQ$ expression. Then, we design an approximation algorithm to find an equivalent ordering that has the best "fractional $\sf FAQ$-width". Our results imply a host of known and a few new results in graphical model inference, relational joins, and logic.

$\sf FAQ$ can be thought of as a declarative language over functions. We examine how the input/output function representations affect the tractability of the problem. We show that dynamic programming is still powerful in some cases where the input functions are compactly represented; in particular, we briefly explain how recent algorithms on beyond worst-case analysis for joins and for $\sf SAT$ and $\sf\#SAT$ can be viewed as variable elimination to solve $\sf FAQ$.

at April 17, 2015 12:43 AM UTC

On behalf of the organizers of *the* workshop on the subject, this is a test of *the* social and information network. If you think you are influential, be sure to share this with all of your colleagues. If you are submitting a paper, be sure to include with your submission that you heard about the workshop here on *Turing’s Invisible Hand* and who first shared it with you. (Or don’t.)

http://networks.seas.harvard.edu/

(with the Conference on Economics and Computation)

June 15, 2015 in Portland, Oregon, USA.

Social and economic networks have recently attracted great interest within computer science, operations research, and economics, among other fields. How do these networks mediate important processes, such as the spread of information or the functioning of markets? This research program emerges from and complements a vast literature in sociology. Much of the recent excitement is due to the availability of social data. Massive digital records of human interactions offer a unique system-wide perspective on collective human behavior as well as opportunities for new experimental and empirical methods.

This workshop seeks to feature some of the most exciting recent research across the spectrum of this interdisciplinary area. On the computational end, we invite work on applications of machine learning, algorithms, and complex network theory to social and economic networks. On the social science end, we welcome new theoretical perspectives, empirical studies, and experiments that expand the economic understanding of network phenomena. As an organizing theme, we emphasize the flow of information in networks, but the workshop is not limited to this.

Submissions are due on April 30th, 2015; see the workshop webpage for more details on the workshop and submission process.

by Jason Hartline at April 16, 2015 10:45 PM UTC

I asked this question on SO on April 7 and added a bounty which has now expired but no poly time solution has been found yet.

I am trying to write code to detect if a matrix is a permutation of a Hankel matrix. Here is the spec.

**Input:** An n by n matrix M whose entries are 1 or 0.

**Output:** A permutation of the rows and columns of M so that M is a Hankel matrix if that is possible. A Hankel matrix has constant skew-diagonals (positive sloping diagonals).

When I say a permutation, I mean we can apply one permutation to the order of the rows and a possibly different one to the columns.

A very nice $O(n^2)$ time algorithm is known for this problem if we only allow permutation of the order of rows.

Peter de Rivaz pointed out this paper as a possible route to proving NP-hardness but I haven't managed to get that to work.

by Lembik at April 16, 2015 05:44 PM UTC

With FOCS submissions sent off and EC rejections in hand, its time to think about presenting your work at a workshop, and chat with your colleagues doing similar things.

If you are working on something at the intersection of algorithmic game theory and machine learning (this includes e.g. the sample complexity of auction design, or learning from revealed preferences, or learning from censored feedback), then you should consider the "Algorithmic Game Theory and Data Science" workshop that we'll be running during EC 2015. Conveniently, this is at FCRC, so if you were planning on attending EC or STOC (or SIGmetrics, or CCC, or...) you'll already be there in Portland.

Deadline is in 10 days!

https://sites.google.com/site/agtanddatascienceworkshop2015/

---------------------------

by Aaron Roth (noreply@blogger.com) at April 16, 2015 05:11 PM UTC

Benjamin Rossman, Rocco Servedio and Li-Yang Tan show new circuit lower bounds that imply, among other things, that the polynomial-time hierarchy is infinite relative to a random oracle. What does that mean, and why is it important?

The polynomial-time hierarchy can be defined inductively as follows: Σ^{P}_{0 }= P, the set of problems solvable in polynomial-time. Σ^{P}_{i+1 }= NP^{ΣPi}, the set of problems computable in nondeterministic polynomial-time that can ask arbitrary questions to the previous level. We say the polynomial-time hierarchy is infinite if Σ^{P}_{i+1 }≠ Σ^{P}_{i} for all i and it collapses otherwise.

Whether the polynomial-time hierarchy is infinite is one of the major assumptions in computational complexity and would imply a large number of statements we believe to be true including that NP-complete problems do not have small circuits and that Graph Isomorphism is not co-NP-complete.

We don't have the techniques to settle whether or not the polynomial-time hierarchy is infinite so we can look at relativized worlds, where all machines have access to the same oracle. The Baker-Gill-Solovay oracle that makes P = NP also collapses the hierarchy. Finding an oracle that makes the hierarchy infinite was a larger challenge and required new results in circuit complexity.

In 1985, Yao in his paper Separating the polynomial-time hierarchy by oracles showed that there were functions that had small depth d+1 circuits but large depth d circuits which was needed for the oracle. Håstad gave a simplified proof. Cai proved that PSPACE ≠ Σ^{P}_{i} for all i even if we choose the oracle at random (with probability one). Babai later and independently gave a simpler proof.

Whether a randomly chosen oracle would make the hierarchy infinite required showing the depth separation of circuits in the average case which remained open for three decades. Rossman, Servedio and Tan solved that circuit problem and get the random oracle result as a consequence. They build on Håstad's proof technique of randomly restricting variables to true and false. Rossman et al. generalize to a random projection method that projects onto a new set of variables. Read their paper to see all the details.

In 1994, Ron Book showed that if the polynomial-time hierarchy was infinite that it remained infinite relativized to a random oracle. Rossman et al. thus gives even more evidence to believe that the hierarchy is indeed infinite, in the sense that if they had proven the opposite result than the hierarchy would have collapsed.

I used Book's paper to show that a number of complexity hypothesis held simultaneously with the hierarchy being infinite, now a trivial consequence of the Rossman et al. result. I can live with that.

The polynomial-time hierarchy can be defined inductively as follows: Σ

Whether the polynomial-time hierarchy is infinite is one of the major assumptions in computational complexity and would imply a large number of statements we believe to be true including that NP-complete problems do not have small circuits and that Graph Isomorphism is not co-NP-complete.

We don't have the techniques to settle whether or not the polynomial-time hierarchy is infinite so we can look at relativized worlds, where all machines have access to the same oracle. The Baker-Gill-Solovay oracle that makes P = NP also collapses the hierarchy. Finding an oracle that makes the hierarchy infinite was a larger challenge and required new results in circuit complexity.

In 1985, Yao in his paper Separating the polynomial-time hierarchy by oracles showed that there were functions that had small depth d+1 circuits but large depth d circuits which was needed for the oracle. Håstad gave a simplified proof. Cai proved that PSPACE ≠ Σ

Whether a randomly chosen oracle would make the hierarchy infinite required showing the depth separation of circuits in the average case which remained open for three decades. Rossman, Servedio and Tan solved that circuit problem and get the random oracle result as a consequence. They build on Håstad's proof technique of randomly restricting variables to true and false. Rossman et al. generalize to a random projection method that projects onto a new set of variables. Read their paper to see all the details.

In 1994, Ron Book showed that if the polynomial-time hierarchy was infinite that it remained infinite relativized to a random oracle. Rossman et al. thus gives even more evidence to believe that the hierarchy is indeed infinite, in the sense that if they had proven the opposite result than the hierarchy would have collapsed.

I used Book's paper to show that a number of complexity hypothesis held simultaneously with the hierarchy being infinite, now a trivial consequence of the Rossman et al. result. I can live with that.

by Lance Fortnow (noreply@blogger.com) at April 16, 2015 01:14 PM UTC

* Congratulations to John Nash and Louis Nirenberg on the 2015 Abel Prize *

Combined from src1, src2. |

John Nash and Louis Nirenberg have jointly won the 2015 Abel Prize for their work on partial differential equations (PDEs). They did not write any joint papers, but Nirenberg evidently got Nash excited about David Hilbert’s 19th problem during Nash’s frequent visits to New York University’s Courant Institute in the mid-1950s. Nash in return stimulated Nirenberg by his verbal approach of barraging a problem with off-kilter ideas. The Norwegian Academy of Sciences and Letters recognized their ‘great influence on each other’ in its prize announcement.

Today we congratulate both men on their joint achievement.

Hilbert’s 19th problem asked whether all solutions to certain partial differential equations must be analytic functions—that is, expressible as power series on local neighborhoods. Enough progress had been made since the 1930s that the remaining task could be likened to building a short road bridge without central stanchions or much room below for support. If you just shoot the road across it is hard to maintain the level needed to reach the other side. But if you aim up then you create more room to make an arch for best support.

The level known before Nash went to work—and Ennio De Giorgi slightly earlier in Italy—was that solutions to Hilbert’s equations gave a property on second derivatives (pardoning a negligible set of points with discontinuities or other bad non-differentiable behavior) that was insufficient. The support structure on the other side of the bridge needed some kind of continuity condition on the first partial derivatives. The task was aiming at a condition low enough to prove but high enough to land where needed on the other side. This makes us wonder whether we have similar situations in computational complexity without fully realizing it.

Nirenberg is one of few surviving researchers who worked on the Manhattan Project—in his case, on a part that had been contracted to Canada’s National Research Council in Montreal. Richard Courant’s son Ernst was a co-worker and suggested NYU as a destination for a Master’s, which led to doctoral work and affiliation there. For his PhD thesis he completed an attack by Hermann Weyl on the problem of embedding the 2-sphere equipped with any Riemannian metric having positive Gaussian curvature into as a convex surface with the standard Euclidean metric so that paths of corresponding points have the same length under the respective metrics. With Louis Caffarelli and Joseph Kohn he gave what are still considered the most stringent restrictions on possible singularities in solutions to the Navier-Stokes equations. He is acclaimed as the grand master of enduringly useful inequalities, which he said he “loves” more than equations.

The basic definition for a function to be **continuous** is that for every and there exists such that whenever , . Actually, a more basic definition is that for every open subset of , is open as a subset of , but we are presupposing metrics on and so that is defined for each.

If for every there is a that works for all , then is **uniformly continuous**. In much of real or complex analysis this is the strongest uniformity condition one needs. It comes for free if is compact. We can postulate a mapping sending to :

However, this still does not articulate a numerical relationship between and . It does not guarantee differentiability, much less that the first derivatives be continuous.

The key conditions have the form

where and are real constants. If and then is a **contracting mapping**. Contracting mappings can be called fellow-travelers of Nash’s work. Nash used the Brouwer fixed-point theorem to prove his famous theorem about equilibria in non-zero-sum games, but one can also use a more-general fixed-point theorem together with contracting mappings. Matthias Günther found an alternative proof of Nash’s equally great embedding theorem for Riemannian manifolds into Euclidean space via contracting mappings.

If and is arbitrary, then satisfies a **Lipschitz condition**, named for Rudolf Lipschitz. Although Lipschitz conditions are commonly available and frequently useful, they were still too high to aim for this problem. What De Giorgi and Nash accomplished was showing that things could work with any appropriately given or chosen . The criterion with allowed is called **Hölder continuity**, named for Otto Hölder.

Hölder continuity turned out to be the key for Hilbert’s 19th. The proof again was like building a bridge. For any instance of Hilbert’s equations, one could take high enough and find to make the inequality work. Given any (and ), analyticity could be shown to follow. I wonder if we can solve open problems in computer theory not by attacking them directly but by trying to set up this kind of proof structure.

Applying this idea could be as simple as the condition for saying one complexity class is contained in another class . Consider the statement

where the classes are represented by standard computable enumerations of poly-time NTMs and of poly-time DTMs, respectively. The enumerations are nondecreasing with respect to code size. In terms of those machines, the statement is:

We can strengthen this by insisting that be given by a computable mapping of :

Thus a complexity class containment involves a mapping between “spaces” of machines. We can ask what further conditions such a mapping may or must meet. If we start with machines and that are “close” in some respect, how far apart can the machines and be?

Because has complete sets we get some further properties for free. If then there is an such that . The mapping from executes the reduction to and composes its output with to get such that .

It is important to note that although inputs of length given to are expanded by the reduction into formulas of size more than linear in which are input to , the *code* of simply embeds that of and and so has size linear in . Moreover, if we weaken the mapping condition to say

where means that is finite, then we can employ Leonid Levin’s universal search algorithm to write the code of in advance. This ensures that the code expansion from to has a reasonable additive constant. In any event, with respect to the ‘metric’ of code size we can deduce a kind of Lipschitz condition: for all :

And with respect to running time, although that of can be astronomical (as we noted in last year’s post), it is still for some fixed . The running time of does expand inputs into formulas of size (the tilde means ignoring polynomials in ), which makes an overall runtime of . Rather than use “” for exact runtimes, let us ignore more than just factors by defining a function to be if for all ,

What we’d like to do take two machines and —deterministic or nondeterministic—that have runtimes in and , respectively, and define a distance in terms of and . We’d further like to arrange at least that under the hypothesized mapping ,

perhaps with . This uses the putative runtime of to create an analogue of a Hölder condition.

If we define the metric simply on the exponents as then we get a Lipschitz condition. The running times of and become and , so their -distance is (at most) . However, we would like to involve quantities like “” and “” or something else that is exponential in and/or in the metric. We could try , but then to get even a Hölder condition on the mapping we are seeking such that

This is not valid without further qualification because is possible, among other things. We would be interested to find a reasonable metric based on running-time and/or program size that gives a Hölder but not Lipschitz condition.

Can happen anyway with a Hölder or even Lipschitz condition under a metric like ? It does with an oracle. The construction giving

basically maps each oracle NTM to an oracle DTM that simply bundles the translation of the code of into a formula into the oracle queries, and so has the same polynomial running time as up to log factors. Hence we can get a Lipschitz property under various distances that use the exponents in running times . This property does not necessarily “relativize,” and it may be interesting to ask what happens if it does.

Perhaps ideas like this can help probe other complexity class relations. When the classes do not have complete sets (or are not known to have them), even getting a computable embedding function can be problematic. That the *concepts* may be simple is not a block; the point is to find a combination of ideas that are conducive to deep uses. For instance, the maximum principle simply states that solutions to elliptic and parabolic PDEs attain their maximum on any connected open subset on the boundary of that subset. A Simons Foundation feature on Nirenberg quotes him as saying,

“I have made a living off the maximum principle.”

Of course this is similar to principles in convex optimization which Nash initially studied.

As with similar ideas we’ve posted, we’re casting about for a new handle on open problems. To quote Sylvia Nasar’s biography *A Beautiful Mind* on pages 218–221 about Hilbert’s 19th problem:

[Nash] had a theory that difficult problems couldn’t be attacked frontally. He approached the problem in an ingeniously roundabout manner, first transforming the nonlinear equations into linear equations and then attacking these by nonlinear means.

At worst we can pass on advice from De Giorgi, who narrowly beat Nash to the solution with a markedly different proof:

“If you can’t prove your theorem, keep shifting parts of the conclusion to the assumptions, until you can.”

Wikipedia’s bio of De Giorgi cites this from a MathOverflow thread titled “Should one attack hard problems?” that leads with

Nasar finishes her account by addressing the “shock” of De Giorgi’s earlier proof on Nash, quoting Peter Lax that when the two met at Courant in 1957, “it was like Stanley meeting Livingstone.” She puts more blame for Nash’s subsequent troubles, quoting Nash himself, on “his attempt to resolve the contradictions in quantum theory.” Which we have also been guilty of promoting. Oh well.

Can such ideas of continuity, metrics, and more broadly topology help to gain insight about complexity classes?

[typo fix: oracle NTM to oracle *D*TM, P_j –> P_k consistently, some other word changes]

by KWRegan at April 16, 2015 04:35 AM UTC

**Authors: **Afonso S. Bandeira **Download:** PDF**Abstract: **The largest eigenvalue of a matrix is always larger or equal than its largest
diagonal entry. We show that for a large class of random Laplacian matrices,
this bound is essentially tight: the largest eigenvalue is, up to lower order
terms, often the size of the largest diagonal entry.

Besides being a simple tool to obtain precise estimates on the largest eigenvalue of a large class of random Laplacian matrices, our main result settles a number of open problems related to the tightness of certain convex relaxation-based algorithms. It easily implies the optimality of the semidefinite relaxation approaches to problems such as $\mathbb{Z}_2$ Synchronization and Stochastic Block Model recovery. Interestingly, this result readily implies the connectivity threshold for Erd\H{o}s-R\'{e}nyi graphs and suggests that these three phenomena are manifestations of the same underlying principle. The main tool is a recent estimate on the spectral norm of matrices with independent entries by van Handel and the author.

at April 16, 2015 12:41 AM UTC

**Authors: **Sangxia Huang **Download:** PDF**Abstract: **We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs
with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices.
There has been much focus on hardness of hypergraph coloring recently.
Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is
quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with
$2^{2^{\Omega(\sqrt{\log\log N})}}$ colors. Their result is obtained by
composing standard Label Cover with an inner-verifier based on Low Degree Long
Code, using Reed-Muller code testing results by Dinur and Guruswami. Using a
different approach, Khot and Saket constructed a new variant of Label Cover,
and composed it with Quadratic Code to show quasi-NP-hardness of coloring
2-colorable 12-uniform hypergraphs with $2^{(\log N)^c}$ colors, for some $c$
around 1/20. Their construction of Label Cover is based on a new notion of
superposition complexity for CSP instances. The composition with inner-verifier
was subsequently improved by Varma, giving the same hardness result for
8-uniform hypergraphs.

Our construction uses both Quadratic Code and Low Degree Long Code, and builds upon the work by Khot and Saket. We present a different approach to construct CSP instances with superposition hardness by observing that when the number of assignments is odd, satisfying a constraint in superposition is the same as "odd-covering" the constraint. We employ Low Degree Long Code in order to keep the construction efficient. In the analysis, we also adapt and generalize one of the key theorems by Dinur and Guruswami in the context of analyzing probabilistically checkable proof systems.

at April 16, 2015 12:40 AM UTC

**Authors: **Emmanuelle Anceaume, Yann Busnel, Ernst Schulte-Geers, Bruno Sericola **Download:** PDF**Abstract: **We study in this paper a generalized coupon collector problem, which consists
in analyzing the time needed to collect a given number of distinct coupons that
are drawn from a set of coupons with an arbitrary probability distribution. We
suppose that a special coupon called the null coupon can be drawn but never
belongs to any collection. In this context, we prove that the almost uniform
distribution, for which all the non-null coupons have the same drawing
probability, is the distribution which stochastically minimizes the time needed
to collect a fixed number of distinct coupons. Moreover, we show that in a
given closed subset of probability distributions, the distribution with all its
entries, but one, equal to the smallest possible value is the one, which
stochastically maximizes the time needed to collect a fixed number of distinct
coupons. An computer science application shows the utility of these results.

at April 16, 2015 12:41 AM UTC

**Authors: **Marc Bury **Download:** PDF**Abstract: **OBDD-based graph algorithms deal with the characteristic function of the edge
set E of a graph $G = (V,E)$ which is represented by an OBDD and solve
optimization problems by mainly using functional operations. We present an
OBDD-based algorithm which uses randomization for the first time. In
particular, we give a maximal matching algorithm with $O(\log^3 \vert V \vert)$
functional operations in expectation. This algorithm may be of independent
interest. The experimental evaluation shows that this algorithm outperforms
known OBDD-based algorithms for the maximal matching problem.

In order to use randomization, we investigate the OBDD complexity of $2^n$ (almost) $k$-wise independent binary random variables. We give a OBDD construction of size $O(n)$ for $3$-wise independent random variables and show a lower bound of $2^{\Omega(n)}$ on the OBDD size for $k \geq 4$. The best known lower bound was $\Omega(2^n/n)$ for $k \approx \log n$ due to Kabanets. We also give a very simple construction of $2^n$ $(\varepsilon, k)$-wise independent binary random variables by constructing a random OBDD of width $O(n k^2/\varepsilon)$.

at April 16, 2015 12:41 AM UTC

**Authors: **Michael Hamann, Ben Strasser **Download:** PDF**Abstract: **We introduce FlowCutter, a novel algorithm to compute a set of edge cuts or
node separators that optimize cut size and balance in the Pareto-sense. Our
core algorithm solves the balanced connected st-edge-cut problem, where two
given nodes s and t must be separated by removing edges to obtain two connected
parts. Using the core algorithm we build variants that compute node-cuts and
are independent of s and t. Using the Pareto-set we can identify cuts with a
particularly good trade-off that can be used to compute contraction and minimum
fill-in orders. Our core algorithm has a running time in O(cm) where m is the
number of edges and c the cut size. This makes it well-suited for large graphs
with very small cuts, such as road graphs, which are our primary application.

at April 16, 2015 12:41 AM UTC

**Authors: **Tamal K. Dey, Facundo Memoli, Yusu Wang **Download:** PDF**Abstract: **Summarizing topological information from datasets and maps defined on them is
a central theme in topological data analysis. Mapper, a tool for such
summarization, takes as input both a possibly high dimensional dataset and a
map defined on the data, and produces a summary of the data by using a cover of
the codomain of the map. This cover, via a pullback operation to the domain,
produces a simplicial complex connecting the data points.

The resulting view of the data through a cover of the codomain offers flexibility in analyzing the data. However, it offers only a view at a fixed scale at which the cover is constructed.} Inspired by the concept, we explore a notion of hierarchical family of coverings which induces a hierarchical family of simplicial complexes connected by simplicial maps, which we call {\em multiscale mapper. We study the resulting structure, its associated persistence module, and its stability under perturbations of the maps and the coverings. The information encoded in multiscale mapper complements that of individual mappers at fixed scales. An upshot of this development is a practical algorithm for computing the persistence diagram of multiscale mapper when the domain is a simplicial complex and the map is a real-valued piecewise-linear function.

at April 16, 2015 12:41 AM UTC

**Authors: **Amir Ali Ahmadi, Raphael Jungers **Download:** PDF**Abstract: **We show that for any positive integer $d$, there are families of switched
linear systems---in fixed dimension and defined by two matrices only---that are
stable under arbitrary switching but do not admit (i) a polynomial Lyapunov
function of degree $\leq d$, or (ii) a polytopic Lyapunov function with $\leq
d$ facets, or (iii) a piecewise quadratic Lyapunov function with $\leq d$
pieces. This implies that there cannot be an upper bound on the size of the
linear and semidefinite programs that search for such stability certificates.
Several constructive and non-constructive arguments are presented which connect
our problem to known (and rather classical) results in the literature regarding
the finiteness conjecture, undecidability, and non-algebraicity of the joint
spectral radius. In particular, we show that existence of an extremal piecewise
algebraic Lyapunov function implies the finiteness property of the optimal
product, generalizing a result of Lagarias and Wang. As a corollary, we prove
that the finiteness property holds for sets of matrices with an extremal
Lyapunov function belonging to some of the most popular function classes in
controls.

at April 16, 2015 12:40 AM UTC

**Authors: **J. M. Landsberg, Mateusz Michałek **Download:** PDF**Abstract: **We analyze tensors in the tensor product of three m-dimensional vector spaces
satisfying Strassen's equations for border rank m. Results include: two purely
geometric characterizations of the Coppersmith-Winograd tensor, a reduction to
the study of symmetric tensors under a mild genericity hypothesis, and numerous
additional equations and examples. This study is closely connected to the study
of the variety of m-dimensional abelian subspaces of the space of endomorphisms
of an m-dimensional vector space, and the subvariety consisting of the Zariski
closure of the variety of maximal tori, called the variety of reductions.

at April 16, 2015 12:40 AM UTC

The field of property testing originated in work on program checking, and has evolved into an established and very active research area. In this work, we survey the developments of one of its most recent and prolific offspring, distribution testing. This subfield, at the junction of property testing and Statistics, is concerned with studying properties of probability distributions.
We cover the current status of distribution testing in several settings, starting with the traditional sampling model where the algorithms obtains independent samples from the distribution. We then discuss different recent models, in which one either grants the testing algorithms more powerful types of queries, or evaluates their performance against that of an information-theoretical optimal ``adversary.'' In each setting, we describe the state-of-the-art for a variety of testing problems.
We hope this survey will serve as a self-contained introduction for those considering research in this field.

at April 15, 2015 08:51 PM UTC

We show that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{(\log N)^{1/4-o(1)}}$ colors, where $N$ is the number of vertices. There has been much focus on hardness of hypergraph coloring recently. Guruswami, H{\aa}stad, Harsha, Srinivasan and Varma showed that it is quasi-NP-hard to color 2-colorable 8-uniform hypergraphs with $2^{2^{\Omega(\sqrt{\log\log N})}}$ colors. Their result is obtained by composing standard Label Cover with an inner-verifier based on Low Degree Long Code, using Reed-Muller code testing results by Dinur and Guruswami. Using a different approach, Khot and Saket constructed a new variant of Label Cover, and composed it with Quadratic Code to show quasi-NP-hardness of coloring 2-colorable 12-uniform hypergraphs with $2^{(\log N)^c}$ colors, for some $c$ around 1/20. Their construction of Label Cover is based on a new notion of superposition complexity for CSP instances. The composition with inner-verifier was subsequently improved by Varma, giving the same hardness result for
8-uniform hypergraphs.
Our construction uses both Quadratic Code and Low Degree Long Code, and builds upon the work by Khot and Saket. We present a different approach to construct CSP instances with superposition hardness by observing that when the number of assignments is odd, satisfying a constraint in superposition is the same as "odd-covering" the constraint. We employ Low Degree Long Code in order to keep the construction efficient. In the analysis, we also adapt and generalize one of the key theorems by Dinur and Guruswami in the context of analyzing probabilistically checkable proof systems.

at April 15, 2015 02:57 PM UTC

I recently started teaching a “polynomial method” class, and I’m trying to write detailed lecture notes for it. So far I put the first three chapters online. I’d appreciate any comments about these, from pointing out serious mistakes, to pointing out minor typos, or even just to ask about things that are not so clear. […]

by adamsheffer at April 15, 2015 04:13 AM UTC

**Authors: **Arman Boyacı, Tınaz Ekim, Mordechai Shalom **Download:** PDF**Abstract: **A \emph{co-bipartite chain} graph is a co-bipartite graph in which the
neighborhoods of the vertices in each clique can be linearly ordered with
respect to inclusion. It is known that the maximum cut problem (MaxCut) is
NP-Hard in co-bipartite graphs. We consider MaxCut in co-bipartite chain
graphs. We first consider the twin-free case and present an explicit solution.
We then show that MaxCut is polynomial time solvable in this graph class.

at April 15, 2015 12:43 AM UTC

**Authors: **Jason Crampton, Andrei Gagarin, Gregory Gutin, Mark Jones **Download:** PDF**Abstract: **A workflow specification defines sets of steps and users. An authorization
policy imposes constraints on which users may perform particular steps. Other
security requirements, such as separation-of-duty, impose constraints on which
groups of users may perform sets of steps. The \emph{workflow satisfiability
problem} (WSP) is the problem of determining whether there exists an assignment
of users to workflow steps that satisfies all such constraints. An algorithm
for solving WSP is important, both as a static analysis tool for workflow
specifications, and for the construction of run-time reference monitors for
workflow management systems. Given the difficulty of WSP, it is important,
particularly for the second application, that such algorithms are as efficient
as possible.

A constraint is said to be \emph{user-independent} if the identities of users are irrelevant to the satisfaction of a constraint. Recent work has developed fixed-parameter tractable algorithms for solving WSP, under the assumption that all constraints are user-independent. In this paper, we generalize the notion of a user-independent constraint to a \emph{class-independent} constraint, enabling us to model scenarios where the set of users may be partitioned into user groups. We prove that solving WSP remains fixed-parameter tractable for this more general class of constraints and develop an algorithm derived from our results. We compare the performance of our bespoke algorithm with that of SAT4J (a pseudo-Boolean SAT solver). Our results demonstrate that our algorithm is more suitable than SAT4J for many instances of WSP.

at April 15, 2015 12:41 AM UTC

**Authors: **Benjamin Rossman, Rocco A. Servedio, Li-Yang Tan **Download:** PDF**Abstract: **We prove an average-case depth hierarchy theorem for Boolean circuits over
the standard basis of $\mathsf{AND}$, $\mathsf{OR}$, and $\mathsf{NOT}$ gates.
Our hierarchy theorem says that for every $d \geq 2$, there is an explicit
$n$-variable Boolean function $f$, computed by a linear-size depth-$d$ formula,
which is such that any depth-$(d-1)$ circuit that agrees with $f$ on $(1/2 +
o_n(1))$ fraction of all inputs must have size $\exp({n^{\Omega(1/d)}}).$ This
answers an open question posed by H{\aa}stad in his Ph.D. thesis.

Our average-case depth hierarchy theorem implies that the polynomial hierarchy is infinite relative to a random oracle with probability 1, confirming a conjecture of H{\aa}stad, Cai, and Babai. We also use our result to show that there is no "approximate converse" to the results of Linial, Mansour, Nisan and Boppana on the total influence of small-depth circuits, thus answering a question posed by O'Donnell, Kalai, and Hatami.

A key ingredient in our proof is a notion of \emph{random projections} which generalize random restrictions.

at April 15, 2015 12:40 AM UTC

**Authors: **Vitaly Feldman, Jan Vondrak **Download:** PDF**Abstract: **Submodular and fractionally subadditive (or equivalently XOS) functions play
a fundamental role in combinatorial optimization, algorithmic game theory and
machine learning. Motivated by learnability of these classes of functions from
random examples, we consider the question of how well such functions can be
approximated by low-degree polynomials in $\ell_2$ norm over the uniform
distribution. This question is equivalent to understanding of the concentration
of Fourier weight on low-degree coefficients, a central concept in Fourier
analysis. We show that

1. For any submodular function $f:\{0,1\}^n \rightarrow [0,1]$, there is a polynomial of degree $O(\log (1/\epsilon) / \epsilon^{4/5})$ approximating $f$ within $\epsilon$ in $\ell_2$, and there is a submodular function that requires degree $\Omega(1/\epsilon^{4/5})$.

2. For any XOS function $f:\{0,1\}^n \rightarrow [0,1]$, there is a polynomial of degree $O(1/\epsilon)$ and there exists an XOS function that requires degree $\Omega(1/\epsilon)$.

This improves on previous approaches that all showed an upper bound of $O(1/\epsilon^2)$ for submodular and XOS functions. The best previous lower bound was $\Omega(1/\epsilon^{2/3})$ for monotone submodular functions. Our techniques reveal new structural properties of submodular and XOS functions and the upper bounds lead to nearly optimal PAC learning algorithms for these classes of functions.

at April 15, 2015 12:43 AM UTC

**Authors: **Clemens Huemer, Pablo Pérez-Lantero **Download:** PDF**Abstract: **We prove that for any convex pentagon there are two disks, among the five
disks having a side of the pentagon as diameter and the midpoint of the side as
its center, that do not intersect. This shows that $K_5$ is never the
intersection graph of such five disks.

at April 15, 2015 12:43 AM UTC

As baseball starts its second week, lets reflect a bit on
how data analytics has changed the game. Not just the Moneyball phenomenon of
ranking players but also the extensive use of defensive shifts (repositioning
the infielders and outfielders for each batter) and other maneuvers. We're not
quite to the point that technology can replace managers and umpires but give it
another decade or two.

We've seen a huge increase in data analysis in sports. ESPN
ranked teams based on their use of analytics and it correlates well with how
those teams are faring. Eventually everyone will use the same learning
algorithms and games will just be a random coin toss with coins weighted by how
much each team can spend.

Steve Kettmann wrote an NYT op-ed piece Don't Let StatisticsRuin Baseball. At first I thought this was just another luddite who will be
left behind but he makes a salient point. We don’t go to baseball to watch the
stats. We go to see people play. We enjoy the suspense of every pitch, the one-on-one
battle between pitcher and batter and the great defensive moves. Maybe
statistics can tell which players a team should acquire and where the fielders
should stand but it still is people that play the game.

Kettmann worries about the obsession of baseball writers
with statistics. Those who write based on stats can be replaced by machines.
Baseball is a great game to listen on the radio for the best broadcasters don't
talk about the numbers, they talk about the people. Otherwise you might as well
listen to competitive tic-tac-toe.

by Lance Fortnow (noreply@blogger.com) at April 14, 2015 05:01 PM UTC

The DIMACS Center at Rutgers University (dimacs.rutgers.edu) is seeking an Associate Director. DIMACS facilitates research, education, and outreach in discrete mathematics, computer science theory, algorithms, mathematical and statistical methods, and their applications. The Associate Director is expected to play a leadership role in planning, developing, and running DIMACS activities and programs, including setting new directions. A PhD in computer science, mathematics, operations research, statistics, or a related field is preferred. Applicants with a doctorate will be considered for Associate Director with a non-tenure-track calendar-year research faculty appointment at Rutgers. Highly qualified applicants without a doctorate will be considered for a staff appointment as Assistant Director. For more details, visit dimacs.rutgers.edu/AssociateDirector.

by Boaz Barak at April 14, 2015 02:11 PM UTC

We study the possibility of computing cryptographic primitives in a fully-black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits which make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions.
We prove several positive and negative results in this model for various cryptographic tasks.
On the positive side, we show that, under reasonable assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, multiplicative-homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.

at April 14, 2015 11:12 AM UTC

Information complexity is the interactive analogue of Shannon's classical information theory. In recent years this field has emerged as a powerful tool for proving strong communication lower bounds, and for addressing some of the major open problems in communication complexity and circuit complexity. A notable achievement of information complexity is the breakthrough in understanding of the fundamental direct sum and direct product conjectures, which aim to quantify the power of parallel computation. This survey provides a brief introduction to information complexity, and overviews some of the recent progress on these conjectures and their tight relationship with the fascinating problem of compressing interactive protocols.

at April 14, 2015 06:28 AM UTC

Ido Erev, Eyal Ert, and Ori Plonsky are organizing an interesting competition under the title: From Anomalies to Forecasts: Choice Prediction Competition for Decisions under Risk and Ambiguity (CPC2015). The idea is to be able to quantitatively predict the magnitude of a multiple known human “biases” and “non-rational” behaviors. The first prize is to be invited to be a co-author of a paper about the competition written by the organizers.

Experimental studies of human choice behavior have documented clear violations of rational economic theory and triggered the development of behavioral economics. Yet, the impact of these careful studies on applied economic analyses, and policy decisions, is not large. One justification for the tendency to ignore the experimental evidence involves the assertion that the behavioral literature highlights contradicting deviations from maximization, and it is not easy to predict which deviation is likely to be more important in specific situations.

To address this problem Kahneman and Tversky (1979) proposed a model (Prospect theory) that captures the joint effect of four of the most important deviations from maximization: the certainty effect (Allais paradox, Allais, 1953), the reflection effect, overweighting of low probability extreme events, and loss aversion (see top four rows in Table 1). The current paper extends this and similar efforts (see e.g., Thaler & Johnson, 1990; Brandstätter, Gigerenzer, & Hertwig, 2006; Birnbaum, 2008; Wakker, 2010; Erev et al., 2010) by facilitating the derivation and comparison of models that capture the joint impact of the four “prospect theory effects” and ten additional phenomena (see Table 1).

These choice phenomena were replicated under one “standard” setting (Hertwig & Ortmann, 2001): choice with real stakes in a space of experimental tasks wide enough to replicate all the phenomena illustrated in Table 1. The results suggest that all 14 phenomena emerge in our setting. Yet, their magnitude tends to be smaller than their magnitude in the original demonstrations.

[[ Table 1 omitted here and appears in the source page]]

The current choice prediction competition focuses on developing models that can capture all of these phenomena but also predict behavior in other choice problems. To calibrate the models we ran an “estimation set” study that included 60, randomly selected, choice problems.

The participants in each competition will be allowed to study the results of the estimation set.

Thus, we use the generalization criterion methodology (see Busemeyer & Wang, 2000).Their goal will be to develop a model that will predict the results of the competition set. In order to qualify to the competition, the model will have to capture all 14 choice phenomena of Table 1. The model should be implemented in a computer program that reads the parameters of the problems as an input and predicts the proportion of choices of Option B as an output.

The deadline for registration is April 20th. Submission deadline is May 17th.

by Noam Nisan at April 14, 2015 05:24 AM UTC

**Authors: **Artur Czumaj, Pan Peng, Christian Sohler **Download:** PDF**Abstract: **We study the problem of recognizing the cluster structure of a graph in the
framework of property testing in the bounded degree model. Given a parameter
$\varepsilon$, a $d$-bounded degree graph is defined to be $(k,
\phi)$-clusterable, if it can be partitioned into no more than $k$ parts, such
that the (inner) conductance of the induced subgraph on each part is at least
$\phi$ and the (outer) conductance of each part is at most
$c_{d,k}\varepsilon^4\phi^2$, where $c_{d,k}$ depends only on $d,k$. Our main
result is a sublinear algorithm with the running time
$\widetilde{O}(\sqrt{n}\cdot\mathrm{poly}(\phi,k,1/\varepsilon))$ that takes as
input a graph with maximum degree bounded by $d$, parameters $k$, $\phi$,
$\varepsilon$, and with probability at least $\frac23$, accepts the graph if it
is $(k,\phi)$-clusterable and rejects the graph if it is $\varepsilon$-far from
$(k, \phi^*)$-clusterable for $\phi^* = c'_{d,k}\frac{\phi^2
\varepsilon^4}{\log n}$, where $c'_{d,k}$ depends only on $d,k$. By the lower
bound of $\Omega(\sqrt{n})$ on the number of queries needed for testing graph
expansion, which corresponds to $k=1$ in our problem, our algorithm is
asymptotically optimal up to polylogarithmic factors.

at April 14, 2015 12:41 AM UTC

**Authors: **Pedro Henrique González, Luidi Simonetti, Philippe Michelon, Carlos Martinhon, Edcarllos Santos **Download:** PDF**Abstract: **This paper presents an iterated local search for the fixed-charge
uncapacitated network design problem with user-optimal flow (FCNDP-UOF), which
concerns routing multiple commodities from its origin to its destination by
signing a network through selecting arcs, with an objective of minimizing the
sum of the fixed costs of the selected arcs plus the sum of variable costs
associated to the flows on each arc. Besides that, since the FCNDP-UOF is a
bi-level problem, each commodity has to be transported through a shortest path,
concerning the edges length, in the built network. The proposed algorithm
generate a initial solution using a variable fixing heuristic. Then a local
branching strategy is applied to improve the quality of the solution. At last,
an efficient perturbation strategy is presented to perform cycle-based moves to
explore different parts of the solution space. Computational experiments shows
that the proposed solution method consistently produces high-quality solutions
in reasonable computational times.

at April 14, 2015 12:42 AM UTC

**Authors: **Serge Lawrencenko, Irina A. Duborkina **Download:** PDF**Abstract: **Logistics networks arise whenever there is a transfer of material substance
or objects (such as checked baggage on international flights) as well as
energy, information, or finance through links (channels). A general concept of
logistics network is suggested and motivated for modeling a service of any kind
supplied through links between the nodes of the network. The efficiency of a
single link is defined to be the ratio of the volume of useful service at the
output node to the volume of expended service at the input node of the link
(for a specific period of time). Similarly, the efficiency of a chain is the
ratio of the volume of service at the output to the volume of service at the
input of the chain. The overall efficiency of the chain is calculated as the
product of the efficiencies of its links; the more efficiency of the chain, the
less are the losses in the chain. This paper introduces the notion of
inadequacy of service in such a way that the overall inadequacy of a chain is
equal to the sum of the inadequacies of its links. So the efficiencies are
being multiplied, whereas the inadequacies are being added. Thus, the
antagonistic pair (efficiency, inadequacy) appears to be analogous to the pair
(reliability, entropy) in communication theory. Various possible
interpretations of the proposed logistic model are presented: energy, material,
information and financial networks. Four algorithms are provided for logistics
chain search: two algorithms for finding the most effective chain from a
specified origin to a specified destination, and two algorithms for finding the
guaranteed minimum level of service between any pair of unspecified nodes in a
given network. An example is shown as to how one of the algorithms finds the
most efficient energy chain from the electrical substation to a specified user
in a concrete energy network.

at April 14, 2015 12:42 AM UTC

**Authors: **Leonard J. Schulman, Alistair Sinclair **Download:** PDF**Abstract: **We study a classical iterative algorithm for the problem of balancing
matrices in the $L_\infty$ norm via a scaling transformation. This algorithm,
which goes back to Osborne, and Parlett and Reinsch in the 1960s, is
implemented as a standard preconditioner in many numerical linear algebra
packages. Surprisingly, despite its widespread use over several decades, no
bounds were known on its rate of convergence. In this paper we prove that, for
a large class of irreducible $n\times n$ (real or complex) input matrices $A$,
a natural variant of the algorithm converges in $O(n^3\log(n\rho/\varepsilon))$
elementary balancing operations, where $\rho$ measures the initial imbalance of
$A$ and $\varepsilon$ is the target imbalance of the output matrix. (The
imbalance of $A$ is $\max_i |\log(a_i^{\text{out}}/a_i^{\text{in}})|$, where
$a_i^{\text{out}},a_i^{\text{in}}$ are the maximum entries in magnitude in the
$i$th row and column respectively.) This bound is tight up to the $\log n$
factor. A balancing operation scales the $i$th row and column so that their
maximum entries are equal, and requires $O(m/n)$ arithmetic operations on
average, where $m$ is the number of non-zero elements in $A$. Thus the running
time of the iterative algorithm is $\tilde{O}(n^2m)$. This is the first time
bound of any kind on any variant of the Osborne-Parlett-Reinsch algorithm. The
class of matrices for which the above analysis holds are those which satisfy a
condition we call Unique Balance, meaning that the limit of the iterative
balancing process does not depend on the order in which balancing operations
are performed. We also prove a combinatorial characterization of the Unique
Balance property, which had earlier been conjectured by Chen.

at April 14, 2015 12:41 AM UTC