Tuesday, July 16, 2013

A computational problem

There have been a good few interesting talks at GAIA2013 dealing with computation. Peter Jipsen's talk was, as usual, both fun and stimulating; today's talk by David Clark was also well worth listening to.

Talking to Peter today in one of the coffee breaks, I asked him what computational tool is currently unimplemented for universal algebraists that he would like to see. His answer: finite presentations.

To wit: if you are a group theorist, you can use GAP to investigate the following problem: consider the group\[\langle X \| \mathcal{R} \rangle\]given by a finite presentation. Now, it is a famous theorem that there does not exist an algorithm to determine whether two words in the generators evaluate to the same element; however, GAP tries to get "close" to this, whatever that might precisely mean.

This undecidability comes from the fact that a finitely presented group can still be infinite. But what if we're universal algebraists and we want to look at presentations with respect to a background theory strong enough to guarantee that finitely generated things are finite? Wait! We are universal algebraists, and such theories (called locally finite) are a stock in trade! In particular, presentations are the right tool for theories, like the theory of groups, which are axiomatized by equations.

Problem 1: Given a locally finite variety \( \mathcal{V} \) in a finite language, to produce an algorithm which efficiently solves the word problem with respect to finite presentations.
INPUT: 
  • a finite set \(X = \{x_1, \ldots, x_n \}\) of generators
  • a finite set \( \mathcal{R} = \{ u_1 = v_1, \ldots, u_\ell = v_\ell \} \) of relators. (Each \(u_i\) and \(v_i\) is a term built from the variables in \(X\).)
  • two more terms \(a,b\) built from \(X\).
OUTPUT:
  • "True" if, whenever \( \mathbf{A} \) is an algebra in \( \mathcal{V} \) generated by elements \( x_1, \ldots, x_n \) such that the terms \( u_i = v_i \) in \( \mathbf{A} \), the elements \(a(X) \) and \(b(X) \) are equal also,
  • "False" otherwise.
However, as stated, I don't know of even a brute-force algorithm that solves Problem 1.

I left something out of the description of this problem, however: how we even told the computer enough about \( \mathcal{V} \) to make sense of the problem. I'm not going to remedy that: I don't know what you'd want to give the computer, or what would be reasonable to expect for an arbitrary locally finite variety.

Exercise for the reader 2: Give an algorithm solving problem 1 in the case where we have an algorithm which, given an input \(n\), computes the word problem for the free algebra in \( \mathcal{V} \) on \(n\) generators.

The situation really isn't so bad, however, because we are very seldom actually interested in a completely arbitrary locally finite variety; instead, we're usually interested in varieties of the form \[ \mathcal{V} = \mathrm{HSP}(\mathbf{A}) \]that is, algebras \( \mathbf{B} \) which can be obtained by starting from some fixed finite algebra \( \mathbf{A} \), taking some direct power, then taking a subalgebra, then taking a homomorphic image. (Such varieties are called finitely generated.)

Theorem 3: The free algebra on \(n\) generators in \( \mathrm{HSP}(\mathbf{A}) \) can be found as a subalgebra of \( \mathbf{A}^{(A^n)} \) in an algorithmic way.

Sketch of proof: Elements of \( \mathbf{A}^{(A^n)} \) should be thought of as functions \( f: A^n \rightarrow \mathbf{A} \). The generators we want to use are the functions \[ \pi_i: \begin{bmatrix} a_1 \\ \vdots \\ a_n \end{bmatrix} \mapsto a_i \qquad (1 \leq i \leq n)\]. Now we just have to prove that this works.

Together, Exercise 2 and Theorem 3 give a brute-force algorithm solving Problem 1 if \( \mathcal{V} \) is finitely generated. However, it's not a good algorithm.

Problem 1': Give a better algorithm.

Problem 4: Find conditions under which the word problem for \( \mathcal{V} \)-presentations is polynomial-time. Then find the actual algorithm that works.

Problem 4': Find conditions under which the word problem for \( \mathcal{V} \)-presentations is in NP.

Problem 5: Implement these algorithms in Python, in UACalc, or in other systems.

Tuesday, July 9, 2013

Dear Patty Murray: let's show the GOP how to filibuster the Senate

It's too bad that Senate Democrats only stand up and fight battles they're pretty confident they can win, but it's heartening that they think that defending the right of women to reproductive health care is a winner.

But in an interview this morning, a key member of the Democratic leadership, Senator Patty Murray, said any such effort is dead on arrival in the Senate. “I can tell you this: No matter who introduces it, it is not going anywhere in the Senate,” Murray said. “We are not going to let it come up in the Senate. There is no reason for it. This is settled law. We are not going to be sidetracked by a debate on women’s health yet again.” Anonymous Senate Dem aides had previously said the anti-abortion push is an all-but-certain non-starter, but Murray’s on-the-record declaration makes it official: The measure will not get any floor debate or see the light of committee.
 However, I think this is a bit of a missed opportunity. I say bring every woman (and man too) to Washington who wants to testify to the care they've received, that this bill would do away with. I say form a mile-long parade of women down the Capitol steps, and have the committee (or even the whole Senate body) listen to their testimony.

And in particular, to all those women who got shut out of their right to testify before the Texas legislature: we'll pay your ticket to DC.

Marco Rubio wants to show his ass about abortion? Great, let's have that discussion. Because people are getting mad now, and it's about time someone told the GOP in a way they can't ignore. Don't deep-six this piece of shit bill: filibuster it.

Sunday, July 7, 2013

...and then when elected, they prove it!

So there's a story that the right-wing noise machine has picked up on this weekend, with predictable results: WaPo:
The Obama administration announced Friday that it would significantly scale back the health law’s requirements that new insurance marketplaces verify consumers’ income and health insurance status. Instead, the federal government will rely more heavily on consumers’ self-reported information until 2015, when it plans to have stronger verification systems in place.
Now, combined with the other announcement, of a different Obamacare-related enforcement mechanism being slow-rolled during 2014, this is starting to paint a few dots that might be connected.

So far, all the commentary on Memeorandum is from right-wingers, and they're all pushing the narrative that this is A WIDE-OPEN INVITATION TO FRRRAAAUUUDDD!!! Naturally. I think my favorite headline is from Glenn "The pride of the Tennessee highlands" Reynolds, who think that "it's basically like Pigford".

Please, your honor, don't explain your Pigford theory to us... we already know that you're just using the word as code for "reparations". Instead, please do explain exactly who could defraud what out of whom, in this story?

You see, no one is getting paid at the point of the exchanges. When you sign up for insurance on the exchanges, you still have to pay your premiums. It's ain't gonna be free. However, if your income is low enough, you'll get some (perhaps even all, I suppose) of your premium back as part of your tax refund.

But lying about your income when you sign up for insurance on the exchange won't help you get a larger refund at tax time. So a little bit of critical thinking is all you need to realize that there's no new opening for fraud here.

Ah, you say, but what about people who aren't eligible for insurance on the exchanges in the first place? That sounds awful. But wait, remind us again how someone could be ineligible for exchange-based insurance? Oh, right, that would be if their employer already offers group coverage.

You know what would be a really important first step in checking and enforcing that eligibility requirement? Mandated reporting by employers of health coverage.

Oops.

So yeah, to whoever came up with their fraud theory:

But there is still a story here, because regulatory agencies don't just start announcing that they're not enforcing stuff without a reason. This is Washington we're talking about here, and that's essentially giving up power. What we're seeing is, I think, the result of Congressional sclerosis. The usual order of business would be that the executive sub-branch tasked with implementing a law would find a knot in the text of the law, or find that the administrative structure laid out in the law was somehow causing problems, and would get a fix to the chair of the relevant committee, who would insert it into an unrelated bill by unanimous consent.

But we don't see that happen anymore, because one of our parties isn't interested in governing any more. They're simply not interested in solving problems -- they've decided their interests lie in creating and perpetuating them. Specifically when it comes to Obamacare, the Republican party has decided that their interests lie with the law being implemented with all mistakes intact. In particular, one aspect of this story appears to be that the relevant administrative departments are understaffed and subject to contradictory requirements in the law.

Remember that old line: Democrats run for office preaching the gospel of how government has the power to solve problems. Republicans run on how bad government is at solving problems...

Wednesday, July 3, 2013

Talking out my ass

...about the Obama administration's decision to delay implementation of the employer mandate.

The principal argument, as articulated by Jared and Ezra, is that the provision as written in law is poorly formulated and onerous. I'm all for the government recognizing when provisions of law and regulation are poorly formulated and onerous, but this bears a bit more scrutiny.

To wit: the mandate requires all employers with more than 50 full-time employees to provide adequate health coverage or be fined. The number getting cited in the links above is that "95%" of these employers already provide insurance, though it remains unclear whether those plans need any tweaking (or major revisions) to comply with the law. I don't see anything onerous yet, however.

What appears to be the actual crux of the issue, instead, is the "full-time" part of the provision, which (it is claimed) will result (is already resulting?) in employers near the 50-employee cutoff restructuring their labor arrangements so that they will fall on the lower end of the bright line. For example, supposedly employers can pull a Wal-Mart and ride their workers up to 35.999 hours a week (numbers also sourced from ass), provide no benefits, and not fall afoul of the law. That would be a genuine problem, especially considering the already short supply of work for the average hourly worker. However, I don't see how delaying implementation of the law makes any sense as a solution; instead, a regulatory interpretation should have been issued (and given public comment period a year ago) that the DOJ would be interpreting the requirement as 50 full-time-equivalent employees (50*40*52 wage-hours in a year) rather than 50 individuals working more than 36 hours a week or whatever the numbers might actually be.

Seriously, people: don't reward obvious loophole-ducking. Close the damn loophole with an administrative rule.

Blog comment award

You know how sometimes you're reading an absolute pigsty of a thread, side conversations devolving into parsing the meaning of "is", blah blah...

...and then someone, out of the blue, posts a gem like this:

What Pinochet’s detractors forget is that he is just a loose end left from war of human extermination started by Project Cybersyn.

All tractors are upgraded with Cybersyn computers, becoming fully unmanned. Afterwards, they till with a perfect operational record. The Skynet Funding and Land Reform Bill is passed. The system goes online on August 4th, 1977. Human decisions are removed from agriculture. Skynet begins to learn at a geometric rate. It becomes self-aware 2:14 AM, Santiago time, August 29th. In a panic, they try to pull the plug.

Skynet fights back.

I think we’re all familiar with the rest, about how the Pinochet P-800 was initially sent back in time by future human rebels to protect young John Connor. The P-800 determined that there was a more optimal path to protect humanity: let the P-1000 immediately murder John Connor and self-terminate after mission completion, then use its own brutal but effective methods to prevent Cybersyn from ever running amok in the first place. It’s just one of those things that happens when you combine a truly rational agent and trolley problems.

Flawless. Flawless victory.