Antoine Amarilli's blog

A cute allocation problem

— updated

In the spirit of something I already did, I'm going to discuss a cute problem that suggested itself spontaneously over dinner, except this time I will study its complexity from a theoretical angle.

The problem is as follows. You applied to a number of companies, and each company's board issued a list of the candidates ranked by their order of preference. You know, for each company, how many people they will hire, and you know that they will take the highest ranked people who accept the job. Your hope is to get a job at any of the companies. Maybe you are ranked sufficiently high at some company to be sure to get a job there, in which case you've won; but maybe you aren't, and you hope that some of the people ranked higher than you will not accept their offer(s) so that you can be selected instead.

Of course, you always have some hope that everyone will desist and that you will get what you want. A harder question is: can you be sure that you will get a position, even though you are not ranked well enough to be sure to have any position? If you think about it, the answer is clearly yes in some situations, assuming that other candidates can only accept at most one position. If some super-strong guy is ranked first at all positions, then he'll take only one of them at most, so if there are two positions where you're the first candidate below the bar, then you're sure to get one of them no matter what happens.

The problem is now to decide this algorithmically. Given as input the list of candidates that beat you at each company, given the number of people recruited by each company, can you decide efficiently whether you are sure to get a job at any of the companies?

It might seem that this problem is NP-hard (computationally intractable) because it looks a lot like the set cover problem or the Boolean satisfiability problem, but actually you can determine in polynomial time whether you are sure to get some job.

The method is to encode the problem as a flow problem. Build a graph that has a source vertex s, a target vertex t, one vertex ci for each candidate i, one vertex lj for each list j, and consider the graph with one edge from s to every ci (with capacity 1), one edge from each ci to the lists lj where candidate i appears before you (with capacity 1), and one edge from each lj to t whose capacity is the number of positions offered by company j (in other words, the number of candidates that need to accept a position at this company for you not to get the job).

Now, we ask whether the maximal flow of this graph saturates all the edges to t. If it does, and if the flow is integral, then observe that the flow gives you a way to allocate candidates to lists so that you do not get any job (the one saturated edge leaving ci tells you which job candidate i accepts). Conversely, if there is such an allocation, then there is a maximal flow saturating all edges to t. But now, the integral flow theorem ensures that there is always a maximal flow that is integral. It remains to observe that the maximum flow problem can be solved in polynomial time to conclude that the same is true of our problem.

This implies the tractability of the following (equivalent) rephrasing of this problem in terms of satisfiability. You have a set of variables (xi) which can each be assigned a value from a domain Di (so, multivalued variables). You have a conjunction of clauses which are sets of equalities between such variables and a constant from their domain. For each clause Cj you have a number nj and you say that the clause is true if at least nj of its litterals are true. This is of course much worse than the usual NP-hard Boolean satisfiability problem, except that you require that the same equality (between a variable and a constant) can never occur in two different clauses. Now, by the above, this restriction makes the satisfiability problem tractable.

New GPG key

— updated

It's a bit of a pain, but it turns out that my old OpenPGP key was using suboptimal settings, and so I've regenerated a new one.

I did this after reading this fine best practices tutorial (for which I incidentally wrote a French translation). The gist of it is (1.) that you should set up GPG correctly to fetch keys from key servers (there's the parcimonie-related paranoia, but there's the very embarrassing fact that by default it seems that GPG never manages to talk to a key server; and (2.) that you should check that your key is secure by issuing the following and checking for things in red:

sudo apt-get install hopenpgp-tools
# FINGERPRINT is the actual fingerprint, not a key ID
hkt export-pubkeys "FINGERPRINT" | hokey lint

Generating a new key isn't especially hard but here is a reminder of what you have to do. You then have to re-sign the keys that you had signed with the old key, using the new one...

The formal transition statement signed by both keys is here, so that you can sign the new key if you had signed the old one.

SVG rendering in Gecko and Webkit

— updated

Did you know that Gecko and Webkit's implementation of SVG disagree on fairly basic points of the spec? For instance, this SVG image should be rendered differently depending on which engine you are using.

The trick is that one of both texts is hidden using a gradient calculated relative to the bounding box of a path with control points going outside of the path, which is computed differently by Webkit and Gecko. See the source of the image for a bit more detail.

It seems that Inkscape is also working like Gecko, and its way of computing bounding boxes makes more sense, so this is probably a Webkit bug, however a quick search didn't turn up the relevant bug (though this is probably well-known).

I devised this SVG with the help of Marc Jeanmougin who has had a good reason to investigate SVG implementations in browsers lately.

Review of the Lenovo IdeaPad Yoga 13 (59384174)

— updated

To replace my dead laptop, I just bought a Lenovo IdeaPad Yoga 13, often identified with the code 59384174 although the official model number seems to be 2191; the EAN13 code is 0887942530297. Here are my impressions about the device. I am using Debian Testing amd64, kernel version is 3.13.1-amd64 as of this writing.

I wanted a laptop with at least 13 inches (feels too cramped otherwise), with an SSD (and no SSD/HDD hybrid, I dislike mechanical drives for laptops and would not trust the controller's caching policy), with a screen resolution better than the default WXGA 1366 by 768 resolution of cheap 13 inch laptop screens, and I wanted the device to be light and slim (the Yoga 13 is 17 mm thick and weighs 1.5 kgs). Oh, and I wanted reasonable battery life.
Windows refund
The machine came with a preinstalled Windows 8. I contacted Lenovo France to get it refunded. However, the only option that their customer service offer to get a Windows refund is to refund the entire laptop... this is really sad.
I managed to buy the device for 590 euros: it was priced at 700 euros by Cdiscount (may not apply anymore as of this writing), 10 euros could be recouped if paying via Buyster, and 100 euros could be recouped from Lenovo France as of this writing through a special offer. From all the devices that I reviewed, this was the cheapest one to satisfy all my criteria, by a fairly large margin. This price not include a putative Windows 8 refund.
The charger is pleasantly slim and outputs 20V. The plug for the power slot in the device is a rectangular but reversible plug.
Power button
Note that if you need to power down the device during the Windows setup phase (because, say, you inadvertently entered it), long-pressing the power button will suspend the computer, not power it off. You need to continue pressing the button after that to turn the computer down.
The screen looks very nice, though a bit glossy. The 1600 by 900 resolution is pleasant. The viewing angle is very wide (no noticeable hue shift except when you start looking at it diagonally). Screen backlighting can be controlled (even disabled outright) through /sys/devices/pci0000:00/0000:00:02.0/drm/card0/card0-LVDS-1/intel_backlight/brightness. By default there is some tearing during video playback, I tried to fix it with this method, not sure how much it helps.
The main selling point of the Yoga series is that the screen folds 360 degrees to a tablet-like configuration. I only wanted to buy a laptop and have little plans to use this functionality (also for the reason that I wouldn't know which operating system to use to work as a tablet yet give me a suitable environment for a regular laptop), so that's just a bonus. Trying out the mechanism out of curiosity, it makes a fairly heavy and strange tablet, and having the keyboard behind is fairly bizarre. The rotation is achieved by a double-hinge mechanism: a standard hinge system works up to 180 degrees, and then those hinges rotate in a second hinge to go all the way to 360. The mechanism doesn't look especially solid and I wouldn't trust it not to break if used regularly, however for less than 180 degrees the standard hinge mechanism seems OK... A related complaint is that some magnets are used to make the 0 degrees (closed lid) and 360 degrees (tablet configuration) stable, and for 0 degrees those magnets are a bit too strong, so that it is a bit hard to open the laptop.
Orientation sensor
From the existence of a hardware button to lock screen rotation (see below), I imagine that the device must include an accelerometer, but it doesn't seem to be supported by the Linux kernel. Nothing relevant shows up in /proc/bus/input/devices or in /dev/input.
Interestingly, speakers are on the rear and the integrated microphone is on the side, probably because they must be usable both in laptop and tablet configuration. Sound quality is not especially good but not especially bad either, given the form factor.
The device features one minijack port (combined microphone and headphones), one eSATA-USB hybrid port, one USB port, one HDMI port, the power supply connector, one USB port, one SDcard-MMC reader, and that's it. Of course, no Ethernet port because the device is too thin. I bought a cheap USB-Ethernet adapter which was detected out of the box by Linux and seems to work.
The keyboard is pleasant enough, the keys are fairly high and have a reasonable size. The Left control is at the bottom left of the keyboard with the Fn button is at its right, which is how it should be (some laptops have the reverse). There is only a Super_L modifier (Windows key), not Super_R, but that's OK. Keys are positioned reasonably except that PageUp and PageDown are not quite at the position where I would have expected them (I would have expected them to be one row higher). By default, the F1-F12 keys can only be reached with Fn and the special (Volume, etc) fonctionalities being the default, but fortunately this can be changed in BIOS. The F1-F12 keys have the following additional features:
  1. Mute, generating XF86AudioMute.
  2. Volume down, generating XF86AudioLowerVolume.
  3. Volume up, generating XF86AudioRaiseVolume.
  4. Cross key, generating an Alt-F4 sequence (Windows keyboard shortcut to close a window).
  5. Refresh key, generating F5 (so doubles with the default behavior of the key.
  6. Disable touchpad key, exposes no events in xev but reports the following in dmesg: atkbd serio0: Unknown key pressed (translated set 2, code 0xbe on isa0060/serio0). Use 'setkeycodes e03e <keycode>' to make it known.
  7. Plane mode key, generating XF86WLAN, and from the dmesg it seems like the Wifi driver is seeing this also and disassociates, but nothing seems to be seen in rfkill.
  8. Three rectangles key, generating a Ctrl_L-Alt_L-Tab sequence (probably a Windows keyboard shortcut to switch application or something).
  9. Screen off key, toggles backlighting on and off (preempts the status in intel_backlight, no xev or dmesg event.
  10. Screen whatever key, generates a Super_L press? (Nothing more shows up, maybe things would be different if I had an external screen plugged in, but I have none to test this hypothesis).
  11. Brightness down key, generates XF86MonBrightnessDown (my i3 config uses xbacklight to handle this)
  12. Brightness up key, generates XF86MonBrightnessUp (ditto)
Additional keys
The laptop comes with a bunch of strange additional buttons, in addition to the keyboard. There is a button with a Windows logo (annoying, that) below the screen, which must be intended to be used in tablet mode with Windows; from xev it seems to simulate a press on Super_L (the windows key on keyboards), but only when released (it generates both the KeyPress and KeyRelease events when released). On the left side are two volume keys generating XF86AudioLowerVolume and XF86AudioRaiseVolume. On the right side is a button to lock screen rotation, which seems to emit the sequence Super_L+o (the Windows hotkey to do this, it seems). Last comes the power button and a small button on the left that can only be pressed with a pen or such; the documentation refers to it as the Novo button. It generates XF86Launch2.
Secure boot
Secure boot can be disabled in BIOS, whatever that is. BIOS offers both UEFI and legacy BIOS boot, legacy boot is not too fast. Interestingly trying to boot a Debian install USB key with UEFI will work except that the screen display will be garbled, this is fixed using legacy boot.
To get Bluetooth to work, install the driver and load the module. Now, here is how I get my Bose Mini SoundLink speakers to work. First, reset those speakers and put them in discoverable mode. Install the bluetooth daemon (Debian package blueetoth) and pulseaudio-module-bluetooth, try to issue pactl load-module module-bluetooth-discover. Ensure in rfkill that the hci0 device exists and isn't blocked. Then, retrieve their address by issuing sudo hcitool scan. Issue bluez-simple-agent hci0 ADDRESS and then bluez-test-audio connect ADDRESS. The speakers should indicate that pairing succeded. Now, check in pacmd list-sinks that a sink exists for the speakers, and use pavuctl to connect your music player to the right sink.
SD card reader
The reader appears as /dev/sdb, not /dev/mmcblk*, and inserting a card will not do anything until you try accessing it with fdisk -l /dev/sdb, at which point the partition files /dev/sdb* should be created. I haven't tried if booting off the SD card reader was possible.
The touchpad has an anti-feature: the button press zones are tactile, meaning that, by default, your pointer will move when trying to just click, this is extremely annoying. You can use synclient to set AreaBottomEdge when using the synaptics driver, but this has another downside: it means you cannot click and drag because clicking locks the pointer. I got much better results by installing xserver-xorg-input-mtrack and enabling it in xorg.conf: clicking at the bottom locks the mouse pointer except past a certain move threshold, which is the right thing to do. It is fairly annoying, however, that I couldn't get mtrack's ButtonZonesEnable feature to work, so to do a right click I have to click with one other finger touching the pad (and when left-clicking I mustn't leave another finger on the pad). I tend to touch the pad while typing, the IgnorePalm option seems to help a bit to ignore that.
Webcam works.
Ambient light sensor
The device has an ambient light sensor on the screen that can be made to work with the Zenbook driver (clone, make, insmod als.ko, requires linux-headers etc.; the value ranges from 0 in total darkness to 40000 in maximum light, with a value in the 1500-2000 range in normal indoor lighting conditions. I didn't try to write a script to adjust screen brightness automatically based on ambient light.
CPU and memory
/proc/meminfo reports 3938992 kB RAM.I haven't checked but there should be one RAM slot with non-soldered RAM, upgradeable by replacing by an 8 GB DDR3 module in SO-DIMM 204 pins packaging (costing about 75 euros as of this writing). /proc/cpuinfo reports the CPU as a Intel(R) Core(TM) i3-3227U CPU @ 1.90GHz. CPU frequency scaling is available, but cpufreq-info reports that it uses the intel_pstate driver, and that only the performance and powersave governors are available, with powersave being used by default. Loading the performance driver doesn't seem to make much of a difference. From cpufreq-aperf it looks like the CPU frequency increases up to the maximum 1.9 Ghz under load, even with the powersave governor (so it isn't locking the frequency to the lowest possible value).
Battery status can be read with ACPI as expected. From a quick test, during reasonable usage (browsing, investigating hotkeys, partitioning, etc.), and with phone plugged in (to tether and work around a Wifi glitch), battery life was around 4:30.
The entire case is closed with Torx-looking screws, and it seems that nothing is intended to be user-serviceable. In particular, you are probably not expected to replace the battery yourself. Of course, people have succeeded in opening their device, and a cursory search suggests that replacement batteries may still be available.
Fan and temperature
Two fans evacuate heat at the back of the unit. Four temperature sensors are detected by libsensors, one under acpitz-virtual-0 and two under coretemp-isa-0000. Temperatures are about 40 degrees in standard usage, with the fans spinning. Annoyingly I found no way to retrieve the fan RPM or to control the fans, and I find it sad that the fans seem to be always spinning even when temperature is low; they are not too noisy but total silence would be perfect, and that's just wasteful in terms of battery life. Temperatures reach 50 degrees and the fans speed up a bit under heavy load.
SSD is a Samsung MZMTD256, 238.47 GiB. Surprisingly it seems that if you are willing to open up your unit you can install a second mSATA SSD in a vacant slot. The default partition layout is surreal, with a whopping 7 partitions: WINRE_DRV, a 1000 MiB NTFS partition, SYSTEM_DRRRV, a 260 MiB bootable FAT32 partition, LRS_ESP, a 1000 MiB FAT32 partition, a 128 MiB msftres unknown partition, the main Windows partition (which is the only one that isn't hidden), and from memory a 4 GB partition and a 12 GB partition for obscure recovery purposes. I didn't touch the first four ones because they don't take up that much space and I'm afraid of making the device unbootable (that's probably an unrealistic fear, but who knows...), but I removed the Windows partition and the two last recovery partitions to install Debian instead. No problems in using GRUB (though I haven't tried booting anything except Debian).
Wifi does not work out of the box, and the absence of an Ethernet port means that Debian installation may be painful. A possible workaround is to use an USB-Ethernet adapter (not tested), or to tether a mobile phone's Wifi connection (Debian install knows how to use such connections) The Wifi chip has USB ID 0bda:1724, and to make it work, for now, you should compile and install the rtl8723au driver. It is painless and works. However, it doesn't seem like changing the MAC address is supported; sudo ifconfig wlan0 hw ether whatever doesn't fail but doesn't change anything, even if the interface is down and even if it is rfkilled. I haven't tried very hard yet or investigated whether the driver had a specific option for this. It does not look like activating monitor mode for airodump-ng works either. It looks like the driver was merged in Linux 3.15, so whenever this kernel version starts shipping with Debian, Wifi should work out of the box.
pm-suspend seems to work, taking about 1 second to suspend and resume. pm-hibernate works but I had to configure the hibernate swap partition manually. Hibernating takes around 10 seconds, booting and resuming from hibernate takes about 16 seconds.

All in all, I am pretty satisfied with the device so far.

Propositions for EU copyright legislation

— updated

The European Commission has opened a public consultation on the review of the EU copyright rules, open to all stakeholders. Their questionnaire is a bit lengthy, but fortunately, according to the Quadrature du Net (a French advocacy group for Internet freedom), you can also answer with a free-form text. So I did just that, taking it as an opportunity to write down some things I would like to see change in the EU copyright legislation. My answer is now published among the 4213 (!) user replies.

What I propose here is my moderate program for copyright reform. My actual views are a bit more extreme, and, within an idealized model of society, I am not entirely sure that copyright is a good thing altogether, in the longer term. Yet this is not a program for an idealized world, but concrete action steps which I feel should be taken as soon as possible to cut down on current copyright legislation's most blatant excesses, so as to reestablish a minimum amount of equilibrum between the interest of right holders and those of the general public.

Yet, I have obviously no hope that this letter will have any impact, because my view are so distant from current EU copyright policies. I would nevertheless like to invite you, dear reader, to submit your opinion to the consultation, while there is time (the deadline is Wednesday, March 5th), even though it feels a bit like you are writing a letter to Father Christmas. Not telling the European Commission about your views, and not giving them the opportunity to ignore them, will limit your right to complain legitimately about what they are doing on copyright issues.

This being said, here are the concrete changes which I suggested. This Web version includes hyperlinks and corrections to the original text.

I understand copyright as a balance struck between society's desire to use, distribute, adapt upon and perform creative works, and the necessity to incentivize creators by granting them a temporary monopoly over some rights on their work.

Current European legislation protects the rights of authors until seventy years after their death. This is disproportionate: such a long duration is certainly not required to encourage or sustain any reasonable form of creation, whereas society is substantially missing out on the opportunity to benefit from many works of art over this long period.

The only explanation I can see to the current state of affairs is that it was achieved through organized lobbying by right holders, which faced little resistance: because the general public does not know about the public domain or realize its importance, and because the organizations which attempt to protect it have a comparatively small economic weight.

I would therefore be in favor of restricting the duration of copyright in European member states, in all circumstances, to no more than 25 years after publication, performance or broadcast.

Since the Berne convention, there are no formalities required to assert copyright over your work; so that, for works with no known or reachable right holder, one must assume by default that the work is protected. Hence, the public's use of the work is limited to protect the monopoly of an absentee right holder: one cannot republish, digitize, adapt upon the work, for fear that the right holder may later resurface and sue for damages.

I am not in favor of introducing mandatory registration formalities for copyright, as I fear they would penalize the less-organized forms of creation (street art, amateur artists, etc.) who would probably not follow them.

However, I believe that, once the creator of a work has ceased to distribute it (out of print books, unmaintained software, etc.), and it has been impossible to contact them for some period of time, copyright protections on the work should lapse. The rationale would be analogous to that of acquisitive prescription: the right holder has shown insufficient motivation to exercise their exclusive rights.

In particular, reappropriation of unavailable works in a for-profit fashion, such as the French ReLIRE, do not serve the public interest.

If a work has been created by employees of European Union member states or European institutions during the course of their duties, it should not enjoy any copyright protection. The reason for this is that there is no need to incentivize or finance such creation, and as this is the best regime to allow the public to benefit from such works created using public money.

This would have many positive effects. As a first example, this would encourage the dissemination of publicly financed research, and ensure that copyright cannot be leveraged by academic publishers to restrict the transmission of scientific knowledge to the general public who indirectly paid for it. Hence, this would contribute to the decline of closed-access scientific venues, which would help decrease the proportion of public research money spent on subscription fees.

As a second example, this would ensure that open data efforts from public organisms must remain really open. This would not not prohibit the sale of extended datasets so that the cost of publishing open data is covered by those who make use of it, but it would ensure that copyright cannot be used as a weapon to limit the further redistribution of such datasets, as could be attempted by short-sighted organisms in a foolish attempt to reap easy profits at the public's ultimate expense.

Digital rights management (DRM) are a set of technologies to limit the copying of digital content in an effort to enforce copyright. Works burdened with DRM usually require specific software, operating system, hardware (sometimes from a specific manufacturer), in order to be consumed. Further, some such technologies require the user to remain in contact with the right holder's server to authorize every use of content, so that the works become unusable once technical intermediaries discontinue the service or remain out of business.

DRM is present on a variety of digital contents, such as e-books (Amazon), video games (Steam), movies (most DVDs), etc. While I respect the right of manufacturers and right holders to offer such content under such conditions, it seems paramount to me that customers be aware of the nature of what they are buying. Right now, the public is not well-informed about the nature and existence of DRM, and the presence of DRM is seldom clearly advertised.

I would argue that any creative work on sale should indicate prominently to the purchaser which equipment is required to read it: software, hardware from a specific manufacturer, and more generally any technology that it is an open standard which can be re-implemented by anyone (i.e., not requiring the payment of any royalties).

Further, if a creative work is offered in a scrambled form designed to be unusable without additional keys provided every time the content is consumed, it should be mandatory to label such offers as "rental" rather than "sale", as continued enjoyment of the work by the customer depends on the provider's will to further allow it.

Current European directives, such as Directive 2001/29/EC, have overreaching provisions which prohibit circumventing DRM, providing technical means to enable it, etc. This often prohibits legitimate cases of DRM circumvention, such as those required for interoperability. Prohibiting copyright infringement is sufficient ; no additional protection should be granted to DRM technologies.

The "freedom of panorama" exemption restricts the copyright protection of works of art permanently located in a public place. This exemption exists in some member countries but not others. European legislation should be harmonized by providing freedom of panorama in all member states, in its strongest form: there should not be any copyright protection of works of art permanently located in public space, as such copyright protection substantially interferes with the public's right to photograph and film in public space.

A huge amount of creativity nowadays is expressed by producing works of art that current copyright legislation consider to be derivative: remixes of well-known songs, fan fictions, videos incorporating sequences of protected video games, etc. The legal status of such works is entirely unclear, and right holders can leverage this to discourage, or censor, such creative works.

In my opinion, the need to incentivize creation through copyright does not justify such restrictions on derivative art forms. Indeed, such transformation has always been an important factor of creativity (folk tales, reuse of musical themes, etc.). It is regrettable that copyright has crept from restrictions on "fixed-form works" to restrictions on certain derivative uses such as performance and translation, to eventually impose overbearing theoretical restrictions on any form of derivative use, which I believe does not reflect the interest of society.

I believe the scope of copyright protection should be changed so that it does not impede transformative uses that cannot harm the interests of the creator. For instance, fan fictions certainly cannot be read as a substitute to the original book, nor can most remixes replace the original song, nor playthrough videos act as a substitute to a video game.

Not-for-profit sharing of copyrighted works between private individuals is a widespread practice in European member states. It was essentially uncontroversial in the times where works of art were fixed to a physical medium (such as books, CDs, etc.), because this made copying unpractical so that sharing was essentially limited to lending.

For digital works, such practices raise the question of how creators should be financed. However, prohibiting it altogether, as is currently done, does not seem sensible: it is disconnected from current practice and from the public's perception of right and wrong. I am unsure about whether a middle ground could be found with solutions such as the French "licence globale" proposals which propose to finance artistic creation through taxation and redistribution to creators: indeed, I do not see how to design a scheme of this kind while ensuring that it finances all artists fairly, including independent artists not registered to any copyright collection society.

I am nevertheless confident that new ways to finance creation, such as crowdfunding, will emerge; that the public is aware of the fact that they need to pay the creators of works they enjoy, and that private artistic sponsorship will increase as technologies reduces the friction of online payment. Hence, I would be in favor of a copyright exemption covering the not-for-profit exchange of creative works between private individuals, as a solution preferable to the current state of affairs.

Copyright is usually held, not by artists, but by copyright collectives of which they are members. Some of these, such as the French SACEM, require that their members automatically assign copyright to them on all their future creative works; terminating one's contract with SACEM is a lengthy and complicated process. [Author's note: There seems to be no up-to-date and reliable information available online about this...]

Such agreements are nothing short of creative servitude; the signer agrees to the transfer of all the fruits of their creativity, with little limits, uncertain compensation, for an indeterminate amount of time. Contracts of this kind should be deemed unfair and considered null and void.

Transferring preemptively one's copyright on one's future creations should be impossible except within employment contracts, in which case this arrangement should be restricted to the hours worked by the employee; additionally, resignation should always be possible, and all relevant labour protection laws should apply.