Usually whenever we think about gradschool we think about the switch from "doing classwork, quals, etc" to "dissertating" is a single-step process, which we call "becoming a PhD candidate" (as opposed to being a PhD student). In practice there are over half a dozen steps. Filing the paperwork declaring your completion of classwork, quals, etc is just the first few. (Okay, easy enough) Then there's the prospectus, for the graduate school. (The what for the who now?) Then the forming of your research committee. (Right, okay) Then the proposal. (Wait, how is this different from the other thing?) Then the proposal defense. (Um, okay, but not every department requires this?) Plus a few other steps I'm surely forgetting.
As of yesterday, I am officially finally totally completely absolutely done with all the paperwork, and can finally get back to actually working on the thesis itself!
Yesterday I started digging into Qt5 and D-Bus. I never found a complete example, so I put one together myself: https://gist.github.com/magthe/2cf7220655bd8bf431259cc7dee99f64.
Finally, I've found one that works - IssueSync. Installing it worked as described. Running it worked as described. I raised tickets for the author and they fixed them. I even sent a pull request and the author discussed and merged it. It downloads all your issues to Markdown files in an issues directory. I then "list" my issues using:head -n1 -q issues/*.md | grep -v CLOSED
It's simple and works nicely.
In a previous post I defined the network reliability problem. Briefly, we are given a directed graph whose edges are labelled with probabilities, which we can think of as giving the likelihood of a message successfully traversing a link in a network. The problem is then to compute the probability that a message will successfully traverse the network from a given source node to a given target node.
Several commenters pointed out the connection to Bayesian networks. I think they are right, and the network reliability problem is a very special case of Bayesian inference. However, so far this hasn’t seemed to help very much, since the things I can find about algorithms for Bayesian inference are either too general (e.g. allowing arbitrary functions at nodes) or too specific (e.g. only working for certain kinds of trees). So I’m going to put aside Bayesian inference for now; perhaps later I can come back to it.
In any case, Derek Elkins also made a comment which pointed to exactly what I wanted to talk about next.Star semirings and path independence
Consider the related problem of computing the reliability of the single most reliable path from to in a network. This is really just a disguised version of the shortest path problem, so one can solve it using Dijkstra’s algorithm. But I want to discuss a more general way to think about solving it, using the theory of star semirings. Recall that a semiring is a set with two associative binary operations, “addition” and “multiplication”, which is a commutative monoid under addition, a monoid under multiplication, and where multiplication distributes over addition and . A star semiring is a semiring with an additional operation satisfying . Intuitively, (though can still be well-defined even when this infinite sum is not; we can at least say that if the infinite sum is defined, they must be equal). If is a star semiring, then the semiring of matrices over is also a star semiring; for details see Dolan (2013), O’Connor (2011), Penaloza (2005), and Lehmann (1977). In particular, there is a very nice functional algorithm for computing , with time complexity (Dolan 2013). (Of course, this is slower than Dijkstra’s algorithm, but unlike Dijkstra’s algorithm it also works for finding shortest paths in the presence of negative edge weights—in which case it is essentially the Floyd-Warshall algorithm.)
Now, given a graph and labelling , define the adjacency matrix to be the matrix of edge probabilities, that is, . Let be the star semiring of probabilities under maximum and multiplication (where , since ). Then we can solve the single most reliable path problem by computing over this semiring, and finding the largest entry. If we want to find the actual most reliable path, and not just its reliability, we can instead work over the semiring , i.e. probabilities paired with paths. You might enjoy working out what the addition, multiplication, and star operations should be, or see O’Connor (2011).
In fact, as shown by O’Connor and Dolan, there are many algorithms that can be recast as computing the star of a matrix, for an appropriate choice of semiring: for example, (reflexive-)transitive closure; all-pairs shortest paths; Gaussian elimination; dataflow analysis; and solving certain knapsack problems. One might hope that there is similarly an appropriate semiring for the network reliability problem. But I have spent some time thinking about this and I do not know of one.
Consider again the simple example given at the start of the previous post:
For this example, we computed the reliability of the network to be , by computing the probability of the upper path, , and the lower path, , and then combining them as , the probability of success on either path less the double-counted probability of simultaneous success on both.
Inspired by this example, one thing we might try would be to define operations and . But when we go to check the semiring laws, we run into a problem: distributivity does not hold! , but . The problem is that the addition operation implicitly assumes that the events with probabilities and are independent: otherwise the probability that they both happen is not actually equal to . The events with probabilities and , however, are not independent. In graph terms, they represent two paths with a shared subpath. In fact, our example computation at the beginning of the post was only correct since the two paths from to were completely independent.Graph reduction
We can at least compute the reliability of series-parallel graphs whose terminals correspond with and :
- If consists of a single edge, return that edge’s probability.
- Otherwise, is a composition of two subgraphs, whose reliabilities we recursively compute. Then:
- If is a sequential composition of graphs, return the product of their reliabilities.
- If is a parallel composition of two graphs with reliabilities and , return .
In the second case, having a parallel composition of graphs ensures that there are no shared edges between them, so and are indeed independent.
Of course, many interesting graphs are not series-parallel. The simplest graph for which the above does not work looks like this:
Suppose all the edges have probability . Can you find the reliability of this network?
More in a future post!References
Dolan, Stephen. 2013. “Fun with Semirings: A Functional Pearl on the Abuse of Linear Algebra.” In ACM SIGPLAN Notices, 48:101–10. 9. ACM.
Lehmann, Daniel J. 1977. “Algebraic Structures for Transitive Closure.” Theoretical Computer Science 4 (1). Elsevier: 59–76.
O’Connor, Russell. 2011. “A Very General Method for Computing Shortest Paths.” http://r6.ca/blog/20110808T035622Z.html.
Penaloza, Rafael. 2005. “Algebraic Structures for Transitive Closure.” http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.71.7650.
I recently read Pinker's The Sense of Style, and urge you to read it too. It is chock full of practical advice on how to make your writing better. Chapter One shows you how to appreciate good writing; I never knew an obituary could be so zippy. Chapter Two explains the approach to writing called 'the classical style', which I have used my whole life without realising it. Chapter Three describes how to keep knowing what you are talking about from getting in the way of communicating clearly. Pinker is an expert on modern grammar, and Chapter Four clarifies how to parse your sentences to avoid ambiguity and employ referents correctly. Chapter Five details the mechanics of how to make a passage cohere. Chapter Six catalogues, from Pinker's position on the usage panel for the American Heritage dictionary, contentious points of diction, with his advice on how to resolve them and what points to consider when resolving them for yourself.
I recommend it highly, and doubly so if you are ever likely to write something that I will have to read.
CFP SBLP 2016: 20th Brazilian Symposium on Programming Languages *** Deadline for Abstracts Approaching***
In a traditional "pointful" definition of a function in Haskell, the names of the function parameters can provide documentation of what the argument is for:
f num_oranges = ...
In point-free style, that opportunity for documentation goes away.
However, if the function has a type signature, then each type element of the signature can be annotated with documentation stating what it is. The feature already exists in Haddock, though it is not too frequently used.
f :: Int -- ^ The 'Int' argument
-> Float -- ^ The 'Float' argument
-> IO () -- ^ The return value
AMY GOODMAN: Let’s go to a clip of Hillary Clinton addressing AIPAC, the American Israel Public Affairs Committee.
HILLARY CLINTON: Many of the young people here today are on the front lines of the battle to oppose the alarming boycott, divestment and sanctions movement known as BDS. ... We must repudiate all efforts to malign, isolate and undermine Israel and the Jewish people.
AMY GOODMAN: That was Hillary Clinton addressing AIPAC. Glenn Greenwald?
GLENN GREENWALD: What she’s doing there is affirming one of the most vile slanders that currently exists. There is a campaign in the United States and in Israel to literally outlaw any advocacy of a boycott movement against Israel, similar to the boycott and divestment and sanctions campaign that brought down Israel and the United States’s closest ally, which was the apartheid regime in South Africa. Now you can certainly raise objections to the tactic of boycotting Israel, and lots of people have, but to render it illegal depends upon this grotesque equating of an advocacy of a boycott of Israel with anti-Semitism and then saying that because anti-Semitism should be banned from universities or from private institutions, that it should be literally outlawed, to ban advocating the boycott of Israel, as well. And people in Europe are actually being arrested for advocating a boycott of Israel. Students in American universities are being sanctioned and punished for doing so.
And what Hillary Clinton did was go before AIPAC and pander, as grotesquely as she typically does, by affirming this line that if you "malign," quote-unquote, the government of Israel and support a boycott of it, in opposition to their decades-long occupation of the Palestinians, it means essentially that you’re guilty of maligning the Jewish people. She is conflating the government of Israel with Jews, which, ironically enough, is itself a long-standing anti-Semitic trope. But it’s just part of her moving to the right in order to position herself for the general election by affirming some of the United States government’s worst and most violent policies.
AMY GOODMAN: Now, Democratic candidate Vermont Senator Bernie Sanders was the only one to skip the AIPAC conference earlier this week. He did address the issue on the campaign trail, though, from Utah, calling for an end to Israel’s occupation of Palestinian territories.
SEN. BERNIE SANDERS: It is absurd for elements within the Netanyahu government to suggest that building more settlements in the West Bank is the appropriate response to the most recent violence. It is also not acceptable that the Netanyahu government decided to withhold hundreds of millions of shekels in tax revenue from the Palestinians, which it is supposed to collect on their behalf.
AMY GOODMAN: That was Bernie Sanders in Utah. Glenn Greenwald, I believe he did offer to address AIPAC by video stream or Skype, as did Romney in 2012, but we heard he was told no.
GLENN GREENWALD: Yeah, I mean, a couple months ago, Donald Trump, on an MSNBC program, said, when asked about Israel and Palestine, that he thought the U.S. should be neutral in order to be a more effective arbiter, which until 20 years ago was a standard mainstream U.S. position, but now has become very shocking. Same with what Bernie Sanders just said. To hear a prominent American politician stand up and actually criticize Israel in such stark and blunt terms, calling them occupiers, essentially, and criticizing how they’re treating the Palestinians, is almost shocking to the ear. Hillary Clinton would never do it, nor would leading Republican politicians. And yet it’s really a very mild way to talk about Israel. And it shows just how far to the right the discourse has shifted in the United States when it comes to Israel, and how much a part of that rightward shift is Hillary Clinton, when you think about how almost shocking it is to hear pretty mild criticisms of Israel coming from Sanders or mild proclamations of neutrality coming from Trump.
Thank you for your email. If you meet the following criteria you are eligible to renew your passport by mail:1. Your passport was valid for 10 years;
2. It was issued within the last 15 years;
3. It is in good condition;
4. Was issued in your current name or you have changed your name and can submit legal documentation (e.g. marriage certificate, Statutory Declaration) to prove this change.
You can mail your renewal application to this office using the address at the foot of this email. The passport must be sent using the Royal Mail special delivery service and the following items must be sent:1. The passport to be renewed;
2. Your original marriage certificate, if you wish to change your name by marriage, or Statutory Declaration, if you wish to change your name by this method;
3. Completed passport renewal form DS82, http://www.state.gov/<wbr></wbr>documents/organization/212241.<wbr></wbr>pdf. Please note: if your current passport was issued within 12 months of this application and you are applying for a new passport in your married name or to correct a data error you should use form DS5504, http://www.state.gov/<wbr></wbr>documents/organization/212249.<wbr></wbr>pdf;
4. Completed credit card payment form for the fee of $110 - no fee is payable if you are able to use form DS5504 to apply for a replacement passport, http://photos.state.gov/<wbr></wbr>libraries/unitedkingdom/<wbr></wbr>164203/cons-acs/card_payment_<wbr></wbr>ppt_by_mail.pdf;
5. A U.S. passport photograph, https://uk.usembassy.gov/u-s-<wbr></wbr>citizen-services/u-s-<wbr></wbr>passports/how-to-renew-a-<wbr></wbr>passport/photographs/;
6. A pre-paid, self-addressed Royal Mail special delivery envelope for the safe return of the passports.
Our turnaround time for applications by mail is approximately 2 weeks.
If you prefer to apply in person you can do so during our counter service hours, 9am-11:30am Tuesdays and Wednesdays. No appointment is necessary. Our turnaround time for passports submitted in person is approximately 7-10 days from submission of the application.
If you do not meet the above criteria you will have to book an appointment online, selecting the option for residents of Scotland, to apply in person at the Consulate General, https://uk.usembassy.gov/u-s-<wbr></wbr>citizen-services/u-s-<wbr></wbr>passports/.
Kind regardsU.S. Consulate General3 Regent TerraceEdinburghEH7 5BWTel: (44) 131 556 8315Fax (44) 131 557 6023
Follow us on Twitter - @USAinScotland