?

Log in

0xDE
18 October 2015 @ 10:01 pm
Two years ago, and again this year, Irvine hosted the Solar Decathlon, a contest in which groups of university students design and build a small, inexpensive, and self-sufficient solar house and get judged on ten categories for how good their house is. The houses (and various related vendor exhibits) were on show to the public at a public park in Irvine, with students from each team on hand to explain their designs. So yesterday I went to see them, and took a few photos.



Unfortunately I didn't keep any shots from my favorite of the houses, an effort by Clemson involving a modular open-source design made out of aluminum composite panels, with amazingly lightweight but strong and attractive snap-together wooden furniture. It was also the only one to pack three bedrooms into the 1000 square foot limit for the enclosed part of the house.

Instead, here are some of the other houses, with annotations.
 
 
 
0xDE
14 October 2015 @ 10:24 pm
I have another new paper on the arXiv, "Treetopes and their graphs", arXiv:1510.03152. It's mostly about a class of 4-dimensional polytopes, and their connections to clustered planarity, but it's hard to visualize 4d, especially on a 2d screen. So to explain what's in the paper, let's start by analogy, several dimensions lower.

Read more...Collapse )
 
 
0xDE
03 October 2015 @ 04:16 pm

An ongoing concern in graph drawing research has been curve complexity. If you draw a graph using a certain style, how complicated are you going to have to make the edges? More complicated curves are harder for readers to follow, and therefore they make the graph less readable. But simpler curves (such as line segments) may have their own problems: not fitting the style (which may constrain the edges to certain directions), running through vertices, forming sharp angles with each other, etc. To balance these concerns, a lot of work in graph drawing has allowed edges to be polygonal paths but has tried to prove hard upper bounds on how many bends you need to use. I'm not fond of polylines and bends myself — I prefer smooth curves such as circular arcs meeting at inflection points — but in this case one can measure the curve complexity in terms of the number of arcs you need per edge, and the theory ends up being much the same.

Read more...Collapse )
 
 
 
0xDE
25 September 2015 @ 08:36 am
I'm in Los Angeles for Graph Drawing, went looking for good espresso near the conference site, and found it at Spring for Coffee, on the corner of 6th Street and Spring. This street art was on a different corner of the same intersection:



It's also the first photo-op for my new cell phone, a Samsung Note 4 that I got a month or so ago after my old faithful Droid 2 Global finally gave up. I miss having an actual physical keyboard but the big screen and up-to-date software are both big improvements.
 
 
0xDE
19 September 2015 @ 03:17 pm
I've been working the past few days on adding to Wikipedia a new article on the logic of graphs. And by chance I also happened to review today this stackexchange question relating to graph toughness. That combination of events caused me to wonder: how difficult is it to express toughness as a logical sentence?

Read more...Collapse )
 
 
0xDE
17 September 2015 @ 12:52 pm
A Carmichael number is a number that is a Fermat pseudoprime modulo all coprime bases. Equivalently, by Korselt's criterion, it is a squarefree number that is congruent to one modulo p − 1 for each prime factor p. Chernick (1939) seems to have been the first to observe that Korselt's criterion can be generalized to integer polynomials. Chernick considered polynomials that are congruent to one modulo all the polynomials formed by subtracting one from an irreducible factor. When an argument to the polynomial makes all its irreducible factors evaluate to prime numbers, the polynomial itself evaluates to a Carmichael number. For this reason Chernick called these polynomials universal forms.

One of Chernick's universal forms is the polynomial (6x + 1)(12x + 1)(18x + 1). This produces Carmichael numbers when x is 1, 6, 35, 45, 51, 55, 56, 100, ... (OEIS:A046025). By Dickson's conjecture there are infinitely many values of x that make all three factors prime and therefore infinitely many Carmichael numbers of this form. Not all of Chernick's universal forms are like this, but in this one all the irreducible factors are a monomial plus one. This property makes it particularly easy to test that the whole polynomial is one modulo each irreducible factor minus one: we need only test whether each of the leading monomials 6x, 12x, and 18x in the factors of the polynomial divides each of the non-constant monomials in the polynomial itself.

So what's special about (6,12,18) here? Do other triples of numbers work? Why or why not? Obviously, integer multiples of the same three numbers also work, but what about other triples that are not in the proportions (1,2,3)?

Read more...Collapse )
 
 
0xDE
16 September 2015 @ 02:01 pm
I'm sure I can't be the only one who still sometimes pays for things with cash, and chooses the amount of cash I give in a way that will cause the change to be a round number. But there can't be very many of us, because every time I do I totally bewilder the cashier I'm dealing with. It doesn't help that they're very seldom capable of making change in their heads.

Today's example: my lunch bill was $10.67. I knew that I had not very many coins, but I had more $1 bills than I wanted, and didn't have any $5 or $10 bills. So, I handed over $21. This confused the cashier so badly that she rang it up as if I had given her $11, realized her mistake, asked me if I knew that I had given her $21, and was unable to figure out what to give me in change (even with the difference between $11 and $10.67 visible on the register screen) without totally redoing the whole transaction from scratch.

But this led me to think about the following variations on the classical change-making problem. They might make good dynamic programming exercises, in part because it's less obvious how to use a greedy algorithm to solve them than it is to use a greedy algorithm for change-making.

Simplest change: given a payment amount, a set of coins (or bills) that can be used for the payment, and a (possibly different) set of coins/bills that can be used to make change, choose how much to pay in order to minimize the number of coins/bills you will get back in change.

Simplest transaction: with the same input data, choose how much to pay in order to minimize the total number of coins/bills that change hands in both directions. (Previously.)

Thinnest wallet: with the same input data, choose how much to pay in order to minimize the total number of coins/bills that you end up with after the transaction, including both your change and the coins and bills that you didn't use to pay the charge.

In all cases, let's assume that the cashier either knows how to give you the optimal change or can be guided by the register into doing so. I'd add another problem here, about choosing how to pay in order to minimize the transaction time and least annoy the math-phobic cashiers, but I'm sure using a credit card or debit card is the answer for that.
 
 
 
0xDE
09 September 2015 @ 02:50 pm
The latest episode of Hugo voting-system fever is that the Hugo administrators were hoping to be able to release anonymized nomination data for this year's Hugo Awards, in order to test the new "E Pluribus Hugo" (single-divisible-vote last-place-elimination) slate-resistant nomination scheme. But now they have realized that anonymization is difficult: one of them made a first cut at anonymizing the data and another was able to match ballots to individual people even after the anonymization. As a result they're delaying (perhaps indefinitely) any release of the anonymized data.

So this naturally raises some questions: is anonymization really possible? What can we do to scramble the data, and what useful information would we lose by doing it?

Read more...Collapse )
Tags:
 
 
0xDE
07 September 2015 @ 11:51 pm

It's been a while since we had a set of portraits of the kids done. So I took some this weekend, just before my daughter dyed the tips of her hair red and flew back to the other coast. Here they are:

 
 
0xDE
If you've ever written a computer program you probably learned a little bit about context-free grammars, a formal method of describing the syntax of most programming languages that can be turned automatically into code for parsing those languages through the magic of compiler-compilers such as yacc. They're used for most other kinds of formal language, too: see for instance the JSON home page, which includes a grammar describing the syntax of data-description language JSON.

Read more...Collapse )
 
 
0xDE
Publishing conference proceedings and other kinds of edited collections as special issues of journals has a long history. But lately (partly as a reaction to perceived shortcomings of the more traditional CS system of publishing a preliminary version of a paper in a conference and then a full version in a journal) there's been increasing pressure to do this for more conferences. Which raises the question: how are we supposed to format these things in our bibliographies and bibtex files?

Read more...Collapse )
 
 
0xDE
31 August 2015 @ 09:33 pm
 
 
 
0xDE
10 August 2015 @ 11:13 pm

I took a few photos on my recent trip to WADS, of the people at the conference and the scenery on the conference excursion. Below are the ones of individual people:

( The rest of the photos )

 
 
0xDE
08 August 2015 @ 08:52 pm
I just returned from Victoria, BC, where the University of Victoria (under the capable local organization of Ulrike Stege) was the host for WADS, the Symposium on Algorithms and Data Structures. (The acronym made more sense when it was calling itself a workshop.)

Read more...Collapse )
 
 
0xDE
04 August 2015 @ 11:11 pm
If you've been paying any attention to my blog posts and other online activity, you probably know that I'm a huge fan of Wikipedia. I think it's a great way to communicate theoretical research to a wider audience, a great way to practice writing in a setting that encourages writing for readability, and a great place to publish survey-like material. Since I began editing Wikipedia in 2006, I have made over 90000 edits and created over 700 new articles (not counting redirects etc), most of them on mathematical subjects. I've also regularly been using collections of Wikipedia readings as textbooks in some of my classes for which there is no published text that matches the material I want to cover. I've encouraged others to contribute their expertise and will take the opportunity to do so again: Edit Wikipedia! Contribute your knowledge to the broader world!

But if you've read many Wikipedia article on mathematical subjects, you'll know that they can have a few issues. The content may sometimes be amateurish and topics may be missing, but those can be fixed with some effort. (Edit Wikipedia! Contribute your knowledge!) Another, more stubborn issue concerns the formatting of its mathematical equations.

Read more...Collapse )
 
 
0xDE
02 August 2015 @ 10:39 pm
Street art? In Irvine? Apparently, now, the answer is yes. Local clothing manufacturer Tillys somehow persuaded the planning commission to allow them to commission Zio Ziegler (new Wikipedia article) to decorate one of their warehouses, right next to interstate 405, where approximately 240,000 daily drivers will see it.

You can't exactly stop on the freeway to take photos, but I found enough other more accessible vantage points to get a few shots:



( The rest of the photos )