ICALP 2015 accepted papers

(congrats to DR!)

~$500K to study complexity theory (in UK), wow, amazing. wonder if any US grants in the field come (anywhere?) close to this.

any ICALP papers stand out to you guys?

@DavidRicherby I used the reply function, as I was not successful in invoking your name on chat ... some features I have not understood yet.

Taking the statement that "complexity refers to the problem, not the algorithm", it could be that a solution is expressed as a program with a size depending on one size parameter of the problem, which sometimes is the case with hardware. Then some resource (surface area, number of connection layers, ...) could well be dependent on otherwise ignored measure, such as cyclomatic complexity, or some other graph property.

Then, in such a context, would not this justify considering cyclomatic complexity as a form of computational complexity.

I may well have missed a point. But I would like to be sure.

@babou Trying to use hardware to measure complexity is difficult because a fixed piece of hardware can only take inputs of a certain size. This means you have to define a family of pieces of hardware to deal with arbitrary input sizes. Circuit complexity uses this approach and is currently very active.

Trying to measure the complexity of problems by the length of programs required to solve them makes sense as a concept but I'm not sure it would work well in practice. Having a short program doesn't seem to correspond to our intuition about what it means for a problem to be hard to solve.

For example, consider a string S of high Kolmogorov complexity. The problem "Is my input equal to S" is computationally very easy but no short program solves it. In contrast, something like 3SAT can be solved by relatively short programs: just check all the possible assignments.

Also, short programs don't necessarily correspond to good algorithms: for example, bogosort probably has much shorter code than quicksort.

So, in this sense, I don't think that things like cyclomatic complexity have a lot to do with computational complexity because they're measuring a different thing. Of course, there might be some subtle connections that I didn't think of while writing this. But the big picture seems to be that they're aimed in different directions.

(BTW, I didn't downvote that particular answer. I don't think it's a particularly good answer but its score's already low enough.)

@DavidRicherby I would think that complexity comes into play as soon as you have a limited resource. There are systems where program size is the major limiting factor, at least for the range of applications considered.

@babou I agree. But, typically, data is larger than programs. So if your "computer" is so resource-bounded that it can only run tiny programs, it can only run on tiny data, too. Program size can't be completely ignored, but it doesn't really fit into a world where you're measuring things asymptotically as the size of the input goes to infinity.

RJLipton recently blogged on program size as a (sometimes overlooked) complexity measure.

he also refers to so-called "galactic algorithms" as another "hidden" or "glossed over" complexity aspect...

@DavidRicherby Well, I would grant you half a point. It is true that complexity is being much abused. I complained about it in a linguistics discussion, as people were people were giving importance to asymptotic phenomena, in a context where their problems are usually very small. However, complexity is often well behaved even for small values, so that it is a proper indicator of how algorithms scale very early on.

Also, in a hardware context, or in space limited context, you may have code that evolves with the data ... is the distinction between code and data always so relevant. It more a feeling though than something I can prove.

agreed that kolmogorov complexity is highly related to "program complexity".

TCS & complexity theory is not merely the study of asymptotic complexity measures. its a big part but that is one subbranch "hijacking" the overall paradigm.

(which reminds me...) there is an old semifamous result by stockmeyer sometimes quoted that looks at program complexity.

@babou why dont you simply upvote the answer to counteract what you think is unjustified/ unmerited downvoting? (or is that too bold a move for you?)

@babou Something like code evolving with the data doesn't seem to fit in current models of complexity so I think that would need something new, perhaps along the lines of what you're suggesting.

actually just saw that stockmeyer result cited somewhere but cant remember where.... maybe even reddit... hmmm... the curse of too much surfing...

@vzn Not sure which result by Stockmeyer you mean, so can't really comment on that.

@vzn As @babou says, the asymptotic behaviour is often quite accurate for quite small inputs so I don't think it's fair to say that asymptotics has "hijacked" the field.

@vzn This is an interesting complement.. These are clearly complexity issues. The question is whether it qualifies as computational complexity. I would think the criterion is: it is computational complexity when it can exhaust a resource.

Then, we are free to mix all kinds of resources in the computational model we choose to solve the problem, and may have complexity with regard to any of them ... provided we have some king of uniform (computable) use of all resources on a given problem size.

@vzn I did not simply upvote because I first wish to get some understanding. My feeling is that the answer is not well motivated (which I am trying to do, with my lacking knowledge of issues). On the other hand, my feeling was that the downvote (as often, especially when without explicit motivation) is more based on bias than on clear argument that it has to be wrong.

@DavidRicherby thx to miracle of google AI it is not hard to find this. its old TCS folklore but delighted it has now been published.

Cosmological Lower Bound on the Circuit Complexity of a Small Problem in Logic stockmeyer/ meyer

stockmeyer/ meyer are the authors of other delightful classic TCS proofs such as (one of my favorites) emptiness problem for regular expressions with exponentiation is EXPSpace complete.

the paper is from 1974, cited by "insiders" but rarely mentioned to students eg in classes/ books. coincidentally have been saving links on this subj of "program complexity" for some kind of blog post.

surfing RJLs blog there are quite a few posts relevant to the subj.

"program size" (SAT encodings) shows up in the celebrated 2014 konev/ lisitsa erdos discrepancy proof

ah! yes the ref to stockmeyer/ meyer 1974 was in rjliptons recent blog here.

transcomputational problems / rjlipton blog

which also mentions levins search where program size plays a role (unf seems no good wikipedia entry on that! a gap!)

another key blog on subj may 2014 also mentions levins search

does program size matter? / rjlipton blog

RJLipton also introduced the term galactic algorithm 2010 which is relevant. the main idea seems to be large hidden constants in the asymptotic complexity. but it can also relate to code size

> A galactic algorithm is an algorithm that is wonderful in its asymptotic behavior, but is never used to actual compute anything.

> Yet, often algorithms are created that cannot be run because their running time is too large, or there are less sophisticated ones that would out-perform them on realistic data.

sedgewick cites lipton/ galactic algorithms p20 of this presentation

algorithms for the masses / sedgewick

> - too complicated to implement