Theory of Computing Blog Aggregator

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.

data-flow diagram for IRS Schedule D tax 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 Si in which there is one antimatroid element xi corresponding to each set Si, another antimatroid element yj corresponding to each element of a set, and the feasible sets consist of any subset of the xi's together with any of the yj's that are covered by sets among the chosen xi's. If we give the xi's small equal negative weights and the yj'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.

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.)

The Workshop on Social and Information Networks
(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!


Call for Papers

In conjunction with the Sixteenth ACM Conference on Economics and Computation (EC'15), we solicit submissions for the First Workshop on Algorithmic Game Theory and Data Science, to be held on June 15, 2015 in Portland, Oregon, USA.

Computer systems have become the primary mediator of social and economic interactions, enabling transactions at ever-increasing scale.  Mechanism design when done on a large scale needs to be a data-driven enterprise.  It seeks to optimize some objective with respect to a huge underlying population that the mechanism designer does not have direct access to.  Instead, the mechanism designer typically will have access to sampled behavior from that population (e.g. bid histories, or purchase decisions).  This means that, on the one hand, mechanism designers will need to bring to bear data-driven methodology from statistical learning theory, econometrics, and revealed preference theory.  On the other hand, strategic settings pose new challenges in data science, and approaches for learning and inference need to be adapted to account for strategization.  

The goal of this workshop is to frame the agenda for research at the interface of algorithms, game theory, and data science.  Papers from a rich set of experimental, empirical, and theoretical perspectives are invited.  Topics of interest include but are not limited to:
  • Can good mechanisms be learned by observing agent behavior in response to other mechanisms?  How hard is it to "learn'' a revenue maximizing auction given a sampled bid history?  How hard is it to learn a predictive model of customer purchase decisions, or better yet, a set of prices that will accurately maximize profit under these behavioral decisions? 
  • What is the sample complexity of mechanism design?  How much data is necessary to enable good mechanism design?
  • How does mechanism design affect inference?  Are outcomes of some mechanisms more informative than those of others from the viewpoint of inference?
  • How does inference affect mechanism design?  If participants know that their data is to be used for inference, how does this knowledge affect their behavior in a mechanism?
  • Can tools from computer science and game theory be used to contribute rigorous guarantees to interactive data analysis?  Strategic interactions between a mechanism and a user base are often interactive (e.g. in the case of an ascending price auction, or repeated interaction with a customer and an online retailer), which is a setting in which traditional methods for preventing data over-fitting are weak.
  • Is data an economic model? Can data be used to evaluate or replace existing economic models?  What is the consequence for game theory and economics for replacing the model with data.

Submission Instructions

Any submission format between abstracts and full papers will be considered.  Abstracts may be rejected if we cannot sufficiently evaluate their contribution.  Full papers will be evaluated after page 10 only at the discretion of the committee.
We solicit both new work and work recently published or soon to be published in another venue.  For submissions of the latter kind, authors must clearly state the venue of publication.  This workshop will have no published proceedings.  Papers appearing in published conference proceedings or journals subsequent to EC 2014 will be considered, though preference may be given to papers that have not yet appeared.  Papers that have appeared or are to appear at EC or affiliated workshops will not be considered.
Authors are encouraged to provide a link to an online version of the paper (such as on arXiv).  If accepted, such papers will be linked via an index to give an informal record of the workshop.
All submissions should be sent electronically to on or before April 26th, 2015.  Notification of acceptance will be on May 11, 2015.

Organizing Committee

Shuchi Chawla, U. of Wisconsin 
Hu Fu, Microsoft Research
Jason Hartline, Northwestern U.
Denis Nekipelov, U. of Virginia
Aaron Roth, U. of Pennsylvania
Kane Sweeney, eBay and Stubhub

by Aaron Roth ( 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= P, the set of problems solvable in polynomial-time. ΣPi+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 ΣPi+1 ≠ ΣPi 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 ≠ ΣPi 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.

by Lance Fortnow ( 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 {\mathbb{R}^3} 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.

Continuity Conditions

The basic definition for a function {f : A \rightarrow B} to be continuous is that for every {x \in A} and {\epsilon > 0} there exists {\delta > 0} such that whenever {||x - y|| < \delta}, {||f(x) - f(y)|| < \epsilon}. Actually, a more basic definition is that for every open subset {S} of {B}, {f^{-1}(S)} is open as a subset of {A}, but we are presupposing metrics on {A} and {B} so that {||\cdot||} is defined for each.

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

\displaystyle  (\exists g)(\forall \epsilon)(\forall x): ||x - y|| < g(\epsilon) \implies ||f(x) - f(y)|| < \epsilon.

However, this still does not articulate a numerical relationship between {||x - y||} and {||f(x) - f(y)||}. It does not guarantee differentiability, much less that the first derivatives be continuous.

The key conditions have the form

\displaystyle  ||f(x) - f(y)|| \leq C||x - y||^{\alpha},

where {C} and {\alpha} are real constants. If {\alpha = 1} and {C < 1} then {f} 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 {\alpha = 1} and {C} is arbitrary, then {f} 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 {\alpha}. The criterion with {\alpha > 1} 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 {\alpha} high enough and find {C} to make the inequality work. Given any {\alpha} (and {C}), 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.

Continuity and Containment

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

\displaystyle \mathsf{NP = P},

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

\displaystyle  (\forall i)(\exists k)\,L(N_i) = L(P_k).

We can strengthen this by insisting that {k} be given by a computable mapping of {i}:

\displaystyle  (\exists g)(\forall i): L(N_i) = L(P_{g(i)}).

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 {N_i} and {N_j} that are “close” in some respect, how far apart can the machines {P_{g(i)}} and {P_{g(j)}} be?

Because {\mathsf{NP}} has complete sets we get some further properties for free. If {\mathsf{NP = P}} then there is an {s} such that {\mathsf{SAT} = L(P_s)}. The mapping {g} from {N_i} executes the reduction to {\mathsf{SAT}} and composes its output with {P_s} to get {P_k = P_{g(i)}} such that {L(P_k) = L(N_i)}.

It is important to note that although inputs {x} of length {n} given to {P_{g(i)}} are expanded by the reduction into formulas of size more than linear in {n} which are input to {P_s}, the code of {P_{g(i)}} simply embeds that of {N_i} and {P_s} and so has size linear in {|N_i|}. Moreover, if we weaken the mapping condition to say

\displaystyle  (\exists g)(\forall i): L(N_i) \equiv^F L(P_{g(i)}),

where {A \equiv^F B} means that {(A \setminus B) \cup (B \setminus A)} is finite, then we can employ Leonid Levin’s universal search algorithm to write the code of {P_s} in advance. This ensures that the code expansion from {N_i} to {P_{g(i)}} 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 {i < j}:

\displaystyle  |P_{g(j)}| - |P_{g(i)}| \leq C\cdot(|N_j| - |N_i|).

And with respect to running time, although that of {P_s} can be astronomical (as we noted in last year’s post), it is still {O(n^{\alpha})} for some fixed {\alpha}. The running time {n^c} of {N_i} does expand inputs {x} into formulas of size {\tilde{O}(n^c)} (the tilde means ignoring polynomials in {\log n}), which makes an overall runtime of {\tilde{O}(n^{c\alpha})}. Rather than use “{\tilde{\Theta}}” for exact runtimes, let us ignore more than just {\log} factors by defining a function {t(n)} to be {\Phi(n^c)} if for all {b < c < d},

\displaystyle  n^b = o(t(n)) = o(n^d).

What we’d like to do take two machines {M} and {N}—deterministic or nondeterministic—that have runtimes in {\Phi(n^b)} and {\Phi(n^c)}, respectively, and define a distance {d(M,N)} in terms of {b} and {c}. We’d further like to arrange at least that under the hypothesized mapping {g},

\displaystyle  d(P_{g(i)},P_{g(j)}) \leq C\cdot d(N_i,N_j)^{\alpha'},

perhaps with {\alpha' > \alpha}. This uses the putative runtime {\Phi(n^\alpha)} of {P_s} to create an analogue of a Hölder condition.

If we define the metric simply on the exponents as {|c - b|} then we get a Lipschitz condition. The running times of {P_{g(i)}} and {P_{g(j)}} become {\Phi(n^{\alpha b})} and {\Phi(n^{\alpha c})}, so their {d}-distance is (at most) {\alpha\cdot|c - b|}. However, we would like to involve quantities like “{n^b}” and “{n^c}” or something else that is exponential in {b} and/or {c} in the metric. We could try {d'(N_i,N_j) = |2^c - 2^b|}, but then to get even a Hölder condition on the mapping we are seeking {\alpha'} such that

\displaystyle  |2^{\alpha c} - 2^{\alpha b}| \leq C\cdot|2^c - 2^b|^{\alpha'}.

This is not valid without further qualification because {2^c - 2^b = 1} 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 {\mathsf{P = NP}} happen anyway with a Hölder or even Lipschitz condition under a metric like {d'}? It does with an oracle. The construction giving

\displaystyle  \mathsf{NP^{QBF} = P^{QBF}}

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

Some Quotes

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 {g} 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 {\mathsf{P = NP?}}

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.

Open Problems

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

[typo fix: oracle NTM to oracle DTM, 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 ( at April 14, 2015 05:01 PM UTC

The DIMACS Center at Rutgers University ( 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

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. 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. Thus, we use the generalization criterion methodology (see Busemeyer & Wang, 2000).

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