Bored...

I am writing a compiler. But to some extend, a compiler writes itself. It just needs someone to do the monkey business of typing it in, which is me. It really is an abusive relation. So, if I am clear, I write and meantime just end up thinking about circuit minimization.

A circuit consists of terms, a term describes a combination of a number of state spaces -at least, that is how I like to think about it,- and a state space describes an exponential number of states. So, the only thing interesting are the terms. What to do?

Again some silly idea: At every point insert a new term by using that E=ite(x, E, E) and rewrite part of the term below it. Which means, you got N points to insert one of the terms below it, do some minimization, and see if the term shrinks. Or just rewrite and take the minimal term. If P!=NP, it can't shrink, of course, because that would lead to a deterministic algorithm. It has prohibitive complexity, and you might end up just factoring out states one by one, but still, interesting. Yeah, I know, a definite 5+ on the Richter scale of weirdoness.

Anyway, if anyone reads this blog and isn't interested in boring stuff, the picture shows a light storage device. It collects light at day, emits it at night. I want one!

Gotta get me one of these...

Can't... Count...

A brief thought on semi-tractable decision tree minimization, for a moment I assume that a minimal circuit equals a minimal decision tree. It just popped into my head, I am not too confident on it, but thought it would be worthwhile to write down anyway.

Circuit minimization deals with the question: What is the minimal circuit for a boolean function f:{0,1}ⁿ->{0,1}? In general, the question is considered to be intractable since the algorithms probe the size 2ⁿ state space. I looked at some solutions, which looked like kludges to me. But I am bad at understanding things I don't understand, that seems to be true for a lot of people.

How would I go at it? Well, to distinguish between all vectors, you need to find the bit which halves the state space best, you could try that by counting the {0,1} x {0,1} relation between the value of a bit, and the result of the function, for each bit. By factoring out bits, you could derive the minimal circuit. And there you see minimal circuitry is related to the ability to count - both intractable.

Counting is prohibitive directly on the state space, but circuits distinguish between symbols of form v = v0 ∧ ¬v1 ∧ ..∧ vn, a conjunction of number |v| variables where a variable may be negated, and such a symbol encodes 2^n-|v| states of the state space. That number can be decomposed and stored directly.

Let's rephrase the question to minimization of small Nand terms Φ(v), which only distinguishes between small numbers of symbols. Thus: How to minimize f:Φ(v)->{0,1}? Well, with the same procedure it could be tried. Or one could start of at the bottom and build minimized decision trees. Trees which are the combination of two other trees under a logical connective could be minimized by probing recursively the square of all endpoints of the trees. But that leads to an intractable algorithm.


A small example, first an informal description of the algorithm.

For a formula Φ depending on {v0, .., vn}:
   0. If Φ consists of one variable or a constant, return Φ.
   1. Count the correlation between each variable vi and the formula Φ 
      with sign 1.
   2. Count the correlation between each variable vi and the negation of the formula ¬Φ 
      with sign 0.
   3. Select either the formula or it's negation, whichever describes the 
      smallest space, Ψ = b ⊕ Φ.
   4. Select the variable vk which splits that state space the best in halves.
   5. Recursively determine the terms for Ψ[vk=1] and Ψ[vk=0].
   6. Return b ⊕ Ite(vk, Ψ[vk=1], Ψ[vk=0]). 

The algorithm for counting is trivial. It takes a DNF and a sign, DNFs can be obtained by sat solving the term. For each conjunction and for each variable occurring in the term, the entry with the variable and sign is increased with 2^n-|v|. For each variable not occurring, it and its negation are increased with 2^n-|v|-1 given the sign.

Note that decision trees encode DNFs, and the the combination of a DNF under most boolean connectives has at most squared complexity.

Lets try it on a(ba). This decomposes into ¬a ∨ (a ∧ b). The algorithm starts of with empty tables. The table as holds the counts for a variable a and a sign s, the sign states whether the elements in the proposition or the negation are counted.

as 00 0 01 0 10 0 11 0

bs 00 0 01 0 10 0 11 0

After processing ¬a, two occurrences of ¬a and one occurrence of b and ¬b are counted.

as 00 0 01 2 10 0 11 0

bs 00 0 01 1 10 0 11 1

After processing (a ∧ b), one occurrence of a and b are counted.

as 00 0 01 2 10 0 11 1

bs 00 0 01 1 10 0 11 2

The algorithm proceeds with counting the negation of the formula of which the DNF is (a ∧ ¬ b).

as 00 0 01 2 10 1 11 1

bs 00 1 01 1 10 0 11 2

The negation of the state space is selected, since the state space with sign 0 totals one element, the other three. The algorithm derives ¬ite(a, ¬b, 0) which trivializes to a(bb).

Counting is linear in the DNF of Φ. The algorithm seems to split the DNF too on every recursion, so its complexity seems to be the number of variables times the DNF, which may be exponential, but for certain decision trees may be tractable. Hence the semi-tractable part.

Guess what rests is determining all the mistakes I made. It looks way too simple not to be know.

012910: It might give small trees, but not minimal circuits. Shared variables among trees are not factored out. Also, it doesn't take into account that the left-hand side of a circuit may be expressed in terms of factors of the right-hand side.


This mind never stops.

Technology at an Unbelievable Price

When I read that Apple introduced a new device, the 'iPad,' at an unbelievable price, I thought it must be irony. They make quality products, but are hardly known for their competitive pricing. Still, at a starting price of five hundred bucks, you can own a tablet -a computer consisting of one touchscreen- build by Apple, which is always good for your coolness attribute.

The specs: 0.5 inches thin. 1.5 pounds. 9.87 inch iPS display, full capacity multi-touch, 1 ghz Apple A4 chip, 16, 32, or 64 GB Flash storage. Extensions and add-ons: 3G, dock, keyboard. Best of all, 10 hours of battery life.

Its smaller and lighter than any netbook, and just looks like an oversized iPhone. What they really did right is running a variant of the iPhone OS on top of it instead of MacOs. Instead of point-and-click you can now touch, scale, wave, prod, gesture around applications, folders, photos, puppets which is the exact right thing to do on a tablet. Yes, you can type, but that remains a kludge.

And that's the thing, from the start I disliked windows, because of its, well, windows. Its all about pixel real-estate, and I always want my application to hold the maximum numbers of em, preferably almost the whole screen. My MacBook pro has a functional multi-touch pad: Why am I still bound to a menu and windows, where I repeatedly need to point at a few pixels, when a wave and a click could easily do the same?

Point-and-click? The same future as VHS.

Waving...

Susskind, 't Hooft and Billiards

Susskind, in his lectures at Stanford, made a bold claim that the universe has a unique future and a unique past. Moreover, his view was that the both future and past can be determined from any given point in time. A reasonable view for a physicist, and it follows our perception of time as linear. We may not hit rewind, still, and play, but, we experience it as a movie.

If I read 't Hooft correctly, who is developing an alternative to QM, then he beliefs that the future can have multiple pasts, i.e., two states may converge to one new state. There's loss of information. An equally bold claim, but somewhat predicted by mathematics. Multiply or add two numbers and you can't uniquely reconstruct the original values.

It seem the problem boils down to a game of billiards: Is it possible to hit the balls such that a new position doesn't tell what the original position was? Often, it would seem so, but there's a way out in the sense that we could consider the state of whole room, not only the table.

Anyway, in case of doubt, I suggest they ask Ben Davies.

Just kidding here, I don't know anything about physics. Now I am really going back to programming...

Subset-Sum?

Why does SUBSET-SUM, sometimes, trivialize so fast? Say S = {a, b, ... } is a set of integers adding up to d, then I can represent each integer, say a, it with its bitwise encoding an, .., a0, and you end up with (a bit confusing but c is the carry, an expression in terms of variables of the following column):

    cn  cn-1 ... c1 c0 
    an  an-1 ... a1 a0 . s0
    bn  bn-1 ... b1 b0 . s1
   
    ------------------+
    dn  dn-1 ... d1 d0

Now, a,b,.. and d are constants so if you would fill in the zeroes and ones, you'ld end up with something like:

    cn  cn-1 ... c1  
    s0   0   ... s0  0
    s1  s1   ...  0 s1
   
    ------------------+
     0   1   ...  1  0

Now you can manipulate si out by replacing them with the xor of the rest of the column, the digit and the carry - especially when taking into account the carry expression and the fact that you can swap rows. Guess I should read somewhat. [Abraham D. Flaxman and Bartosz Przydatek, Solving Medium-Density Subset Sum Problems in Expected Polynomial Time.] Right, there's a whole folkflore around this problem, the article was on mod M problems with medium density, its a probabilistic algorithm with an expected running time.

Tinkering... Its not too exciting...

AKS, Pascal, Primality and Subset-sum

Something in the back of my mind nags about the square of Pascal, primality and subset-sum. I read some of Scott Aaronson lectures which got me to think again on irreversibility, XOR-SAT, linear algorithms, BPP=P and BQP.

Why is testing primality on the nth line of Pascal's square seen as exponential? Looks like cubic, but prohibitive, to me. Missing stuff. Having a look at Karatsuba and Strassen again.

Stopped programming for a while and am looking what gives if you simplify SUBSET-SUM by manipulating out unknowns. Guess I need a hobby.

Quantum dump, while programming.

It Doesn't Fit

Meme of today: How much information fits into a digital circuit which is of squared form?

If I can combine two minimal terms to derive a minimal term, then that gives a bottom-up strategy on solving instances of problems. How hard is it to check you're near minimal given the number of operations performed?

It becomes interesting when you look at the encoding of SUBSET-SUM, where SUBSET-SUM I trivialize by assuming the numbers and set have the same dimension n. In the digital encoding you end up with a 'square' term, corresponding to the space-time complexity, with width and breadth cn, and depth therefore 2dn. FACTOR looks similar. (Note that I am looking at propositional formulas encoding instances.)

Now we look at what a variable means, say we have two, a and b, gives 2**(2**2) functions, thus we should get 16 different functions. For a variable, you can assume it encodes a mapping on the state space. For example, a encodes 0011 and b encodes 0101. Similarly, (aa), we only have one operator so I omit it, thus encodes 1100, (ab) encodes 1110. My favorite, (aa)a, see the logo/favicon, encodes a tautology. Enumerating the terms gives all functions eventually.

There is only a squared number of operations performed, the depth is also bounded, so, the maximal information in the term, and the minimal term size, is, as far as I can see, the Shannon density? Guess its standard complexity theory, its been a while.

012610: Thought it over, I defined a tautology here. If you define the 'Shannon density' as the minimal term for a proposition, then of course everything sticks. For factor, the encoding of a product is quadratic in time-space, but the minimal term size -of a concrete instance- is upper bounded by the number of divisors (up to the square root) after manipulating the term and algebraically removing one unknown.

012610: Perfect, I found the bound again on the number of divisors: The divisor bound asserts that, as n gets large,







or the more precise bound







012610: Of course, its rather easy to describe an exponential number of bit strings with a term recognizing bit vectors. So the answer is: Quadratic information even though a term may describe an exponential number of symbols.

012710: Oh, right, a variable encodes an exponential number of bit vectors. A term encodes an exponential number of paths to a variable. Variables can occur on even and odd length paths. Can we hope to compress along those paths? I think I tried that, its And-Or tree compression, and close to a variable picking heuristic from SAT solving.

(Great, in a day I went from logarithmic (which I remembered), to linear, to an exponential bound on the Shannon density of divisors. Messy. Ah well, been five years since I looked at this.)

Oi, Shannon, you home?