text:
## IACR News

Here you can see all recent updates to the IACR webpage. These updates are also available:

#### 27 November 2019

###### Megha Byali, Harsh Chaudhari, Arpita Patra, Ajith Suresh
ePrint Report
Privacy-preserving machine learning (PPML) via Secure Multi-party Computation (MPC) has gained momentum in the recent past. Assuming a minimal network of pair-wise private channels, we propose an efficient four-party PPML framework over rings, FLASH, the first of its kind in the regime of PPML framework, that achieves the strongest security notion of Guaranteed Output Delivery (all parties obtain the output irrespective of adversary's behaviour). The state of the art ML frameworks such as ABY3 by {\em Mohassel et.al} (ACM CCS'18) and SecureNN by {\em Wagh et.al} (PETS'19) operate in the setting of $3$ parties with one malicious corruption but achieve the {\em weaker} security guarantee of {\em abort}. We demonstrate PPML with real-time efficiency, using the following custom-made tools that overcome the limitations of the aforementioned state-of-the-art-- (a) {\em dot product}, which is independent of the vector size unlike the state-of-the-art ABY3, SecureNN and ASTRA by {\em Chaudhari et.al} (ACM CCSW'19), all of which have linear dependence on the vector size. (b) {\em Truncation} and {\em MSB Extraction}, which are constant round and free of circuits like Parallel Prefix Adder (PPA) and Ripple Carry Adder (RCA), unlike ABY3 which uses these circuits and has round complexity of the order of depth of these circuits. We then exhibit the application of our FLASH framework in the secure server-aided prediction of vital algorithms-- Linear Regression, Logistic Regression, Deep Neural Networks, and Binarized Neural Networks. We substantiate our theoretical claims through improvement in benchmarks of the aforementioned algorithms when compared with the current best framework ABY3. All the protocols are implemented over a 64-bit ring in LAN and WAN. Our experiments demonstrate that, for MNIST dataset, the improvement (in terms of throughput) ranges from $24\times$ to $1390\times$ over LAN and WAN together.
###### Cagdas Calik, Meltem Sonmez Turan, Rene Peralta
ePrint Report
Multiplicative complexity (MC) is defined as the minimum number of AND gates required to implement a function with a circuit over the basis (AND, XOR, NOT). Boolean functions with MC 1 and 2 have been characterized in Fischer and Peralta ( 2002) and Find et al. (2017), respectively. In this work, we identify the affine equivalence classes for functions with MC 3 and 4. In order to achieve this, we utilize the notion of the dimension $dim(f)$ of a Boolean function in relation to its linearity dimension, and provide a new lower bound suggesting that multiplicative complexity of $f$ is at least $\ceil{dim(f)/2}$. For MC 3, this implies that there are no equivalence classes other than those $24$ identified in Calik et al (2018). Using the techniques from Calik et al. (2018) and the new relation between dimension and MC, we identify the 1277 equivalence classes having MC 4. We also provide a closed formula for the number of $n$-variable functions with MC 3 and 4. The techniques allow us to construct MC-optimal circuits for Boolean functions that have MC 4 or less, independent of the number of variables they are defined on.
###### Sébastien Campion, Julien Devigne, Céline Duguey, Pierre-Alain Fouque
ePrint Report
Nowadays, we spend our life juggling with many devices such as smartphones, tablets or laptops, and we expect to easily and efficiently switch between them without losing time or security. However, most applications have been designed for single device usage. This is the case for secure instant messaging (SIM) services based on the Signal protocol, that implements the Double Ratchet key exchange algorithm. While some adaptations, like the Sesame protocol released by the developers of Signal, have been proposed to fix this usability issue, they have not been designed as specific multi-device solutions and no security model has been formally defined either. In addition, even though the group key exchange problematic appears related to the multi-device case, group solutions are too generic and do not take into account some properties of the multi-device setting.Indeed, the fact that all devices belong to a single user can be exploited to build more efficient solutions. In this paper, we propose a Multi-Device Instant Messaging protocol based on Signal, ensuring all the security properties of the original Signal.
###### Colin Boyd, Kai Gellert
ePrint Report
Forward security ensures that compromise of entities today does not impact the security of cryptographic primtitives employed in the past. Such a form of security is regarded as increasingly important in the modern world due to the existence of adversaries with mass storage capabilites and powerful infiltration abilities. Although the idea of forward security has been known for over 30 years, current understanding of what it really should mean is limited due to the prevalence of new techniques and inconsistent terminology. We survey existing methods for achieving forward security for different cryptographic primitives and propose new definitions and terminology aimed at a unified treatment of the notion.
###### Kaushik Nath, Palash Sarkar
ePrint Report
In this paper we introduce new Montgomery and Edwards form elliptic curve targeted at the 256-bit security level. To this end, we work with three primes, namely $p_1:=2^{506}-45$, $p_2=2^{510}-75$ and $p_3:=2^{521}-1$. While $p_3$ has been considered earlier in the literature, $p_1$ and $p_2$ are new. We define a pair of birationally equivalent Montgomery and Edwards form curves over all the three primes. Efficient 64-bit assembly implementations targeted at Skylake and later generation Intel processors have been made for the shared secret computation phase of the Diffie-Hellman key agreement protocol for the new Montgomery curves. Curve448 of the Transport Layer Security, Version 1.3 is a Montgomery curve which provides security at the 224-bit security level. Compared to the best publicly available 64-bit implementation of Curve448, the new Montgomery curve over $p_1$ leads to a $3\%$-$4\%$ slowdown and the new Montgomery curve over $p_2$ leads to a $4.5\%$-$5\%$ slowdown; on the other hand, 29 and 30.5 extra bits of security respectively are gained. For designers aiming for the 256-bit security level, the new curves over $p_1$ and $p_2$ provide an acceptable trade-off between security and efficiency.
###### Daniele Cozzo, Nigel P. smart
ePrint Report
We present the first actively secure variant of a distributed signature scheme based on isogenies. The protocol produces signatures from the recent CSI-FiSh signature scheme. Our scheme works for any access structure, as we use a replicated secret sharing scheme to define the underlying secret sharing; as such it is only practical when the number of maximally unqualified sets is relatively small. This, however, includes the important case of full threshold, and $(n,t)$-threshold schemes when $n$ is small.
###### Yanbin Li, Gaëtan Leurent, Meiqin Wang, Wei Wang, Guoyan Zhang , Yu Liu
ePrint Report
Authenticated encryption (AE) schemes are widely used to secure communications because they can guarantee both confidentiality and authenticity of a message. In addition to the standard AE security notion, some recent schemes offer extra robustness, i.e. they maintain security in some misuse scenarios. In particular, Ashur, Dunkelman and Luykx proposed a generic AE construction at CRYPTO'17 that is secure even when releasing unverified plaintext (the RUP setting), and a concrete instantiation, GCM-RUP. The designers proved that GCM-RUP is secure up to the birthday bound in the nonce-respecting model.

In this paper, we perform a birthday-bound universal forgery attack against GCM-RUP, matching the bound of the proof. While there are simple distinguishing attacks with birthday complexity on GCM-RUP, our attack is much stronger: we have a partial key recovery leading to universal forgeries. For reference, the best known universal forgery attack against GCM requires $2^{2n/3}$ operations, and many schemes do not have any known universal forgery attacks faster than $2^n$. This suggests that GCM-RUP offers a different security trade-off than GCM: stronger protection in the RUP setting, but more fragile when the data complexity reaches the birthday bound. In order to avoid this attack, we suggest a minor modification of GCM-RUP that seems to offer better robustness at the birthday bound.
###### Xuan Thanh Do, Duong Hieu Phan, David Pointcheval
ePrint Report
Functional Encryption (FE) has been widely studied in the last decade, as it provides a very useful tool for restricted access to sensitive data: from a ciphertext, it allows specific users to learn a function of the underlying plaintext. In practice, many users may be interested in the same function on the data, say the mean value of the inputs, for example. The conventional definition of FE associates each function to a secret decryption functional key and therefore all the users get the same secret key for the same function. This induces an important problem: if one of these users (called a traitor) leaks or sells the decryption functional key to be included in a pirate decryption tool, then there is no way to trace back its identity. Our objective is to solve this issue by introducing a new primitive, called Traceable Functional Encryption: the functional decryption key will not only be specific to a function, but to a user too, in such a way that if some users collude to produce a pirate decoder that successfully evaluates a function on the plaintext, from the ciphertext only, one can trace back at least one of them.

We propose a concrete solution for Inner Product Functional Encryption (IPFE). We first remark that the ElGamal-based IPFE from Abdalla et. al. in PKC '15 shares many similarities with the Boneh-Franklin traitor tracing from CRYPTO '99. Then, we can combine these two schemes in a very efficient way, with the help of pairings, to obtain a Traceable IPFE with black-box confirmation.
###### Ward Beullens, Tim Beyne, Aleksei Udovenko, Giuseppe Vitto
ePrint Report
The Legendre PRF relies on the conjectured pseudorandomness properties of the Legendre symbol with a hidden shift. Originally proposed as a PRG by Damgård at CRYPTO 1988, it was recently suggested as an efficient PRF for multiparty computation purposes by Grassi et al. at CCS 2016. Moreover, the Legendre PRF is being considered for usage in the Ethereum 2.0 blockchain.

This paper improves previous attacks on the Legendre PRF and its higher-degree variant due to Khovratovich by reducing the time complexity from $\mathcal{O}(p\log{p}/M)$ to $\mathcal{O}(p\log^2{p}/M^2)$ Legendre symbol evaluations when $M \le \sqrt[4]{p}$ queries are available. The practical relevance of our improved attack is demonstrated by breaking two concrete instances of the PRF proposed by the Ethereum foundation. Furthermore, we generalize our attack in a nontrivial way to the higher-degree variant of the Legendre PRF and we point out a large class of weak keys for this construction.

Lastly, we provide the first security analysis of two additional generalizations of the Legendre PRF originally proposed by Damgård in the PRG setting, namely the Jacobi PRF and the power residue PRF.
###### Jacqueline Brendel, Marc Fischlin, Felix Günther, Christian Janson, Douglas Stebila
ePrint Report
Modern key exchange protocols are usually based on the Diffie–Hellman (DH) primitive. The beauty of this primitive, among other things, is its potential reusage of key shares: DH shares can be either used once as an ephemeral key or used in multiple runs as a (semi-)static key. Since DH-based protocols are insecure against quantum adversaries, alternative solutions have to be found when moving to the post-quantum setting. However, most post-quantum candidates, including schemes based on lattices and even supersingular isogeny DH, are not known to be secure under key reuse. In particular, this means that they cannot be necessarily deployed as an immediate DH substitute in protocols.

In this paper, we introduce the notion of a split key encapsulation mechanism (split KEM) to translate the desired properties of a DH-based protocol, namely contributiveness and key-reusability, to a KEM-based protocol flow. We provide the relevant security notions of split KEMs and show that the formalism lends itself to lift Signal’s X3DH to the post-quantum KEM setting. While the proposed framework conceptually solves the raised issues, we did not succeed in providing a strongly-secure, post- quantum instantiation of a split KEM yet. The intention of this paper hence is to raise further awareness of the challenges arising when moving to KEM-based key exchange protocols with contributiveness and key-resusability, and to enable others to start investigating potential solutions.
###### Daniel Smith-Tone, Cristina Tone
ePrint Report
We introduce a new technique for building multivariate encryption schemes based on random linear codes. The construction is versatile, naturally admitting multiple modifications. Among these modifications is an interesting embedding modifier--- any efficiently invertible multivariate system can be embedded and used as part of the inversion process. In particular, even small scale secure multivariate signature schemes can be embedded producing reasonably efficient encryption schemes. Thus this technique offers a bridge between multivariate signatures, many of which have remained stable and functional for many years, and multivariate encryption, a historically more troubling area.
###### Zhangshuang Guan, Zhiguo Wan, Yang Yang, Yan Zhou, Butian Huang
ePrint Report
The disruptive blockchain technology is expected to have broad applications in many areas due to its advantages of transparency, fault tolerance, and decentralization, but the open nature of blockchain also introduces severe privacy issues. Since anyone can deduce private information about relevant accounts, different privacy-preserving techniques have been proposed for cryptocurrencies under the UTXO model, e.g., Zerocash and Monero. However, it is more challenging to protect privacy for account-model blockchains (e.g., Ethereum) since it is much easier to link accounts in the account-model blockchain. In this paper, we propose BlockMaze, an efficient privacy-preserving account-model blockchain based on zk-SNARKs. Along with dual-balance model, BlockMaze achieves strong privacy guaran- tees by hiding account balances, transaction amounts, and linkage between senders and recipients. Moreover, we provide formal security definitions and prove the security of BlockMaze. Finally, we implement a prototype of BlockMaze based on Libsnark and Go-Ethereum, and conduct extensive experiments to evaluate its performance. The experiment results demonstrate BlockMaze has high efficiency in computation and transaction throughput.
###### Nico Döttling, Sanjam Garg, Vipul Goyal, Giulio Malavolta
ePrint Report
In a Conditional Disclosure of Secrets (CDS) a verifier V wants to reveal a message m to a prover P conditioned on the fact that x is an accepting instance of some NP-language L. An honest prover (holding the corresponding witness w) always obtains the message m at the end of the interaction. On the other hand, if x is not in L we require that no PPT P* can learn the message m. We introduce laconic CDS, a two round CDS protocol with optimal computational cost for the verifier V and optimal communication cost. More specifically, the verifier's computation and overall communication grows with poly(|x|,\lambda,log(T)), where \lambda is the security parameter and T is the verification time for checking that x is in L (given w). We obtain constructions of laconic CDS under standard assumptions, such as CDH or LWE. Laconic CDS serves as a powerful tool for "maliciousifying" semi-honest protocols while preserving their computational and communication complexities. To substantiate this claim, we consider the setting of non-interactive secure computation: Alice wants to publish a short digest corresponding to a private large input x on her web page such that (possibly many) Bob, with a private input y, can send a short message to Alice allowing her to learn C(x,y) (where C is a public circuit). The protocol must be reusable in the sense that Bob can engage in arbitrarily many executions on the same digest. In this context we obtain the following new implications.

(1) UC Secure Bob-optimized 2PC: We obtain a UC secure protocol where Bob's computational cost and the communication cost of the protocol grows with poly(|x|,|y|,\lambda, d), where d is the depth of the computed circuit C.

(2) Malicious Laconic Function Evaluation: Next, we move on to the setting where Alice's input x is large. For this case, UC secure protocols must have communication cost growing with x. Thus, with the goal of achieving better efficiency, we consider a weaker notion of malicious security. For this setting, we obtain a protocol for which Bob's computational cost and the communication cost of the protocol grows with poly(|y|,\lambda, d), where d is the depth of the computed circuit C.
###### Jing Yang, Thomas Johansson, Alexander Maximov
ePrint Report
In this paper we develop a number of generic techniques and algorithms in spectral analysis of large linear approximations for use in cryptanalysis. We apply the developed tools for cryptanalysis of ZUC-256 and give a distinguishing attack with complexity around $2^{236}$. Although the attack is only $2^{20}$ times faster than exhaustive key search, the result indicates that ZUC-256 does not provide a source with full 256-bit entropy in the generated keystream, which would be expected from a 256-bit key. To the best of our knowledge, this is the first known academic attack on full ZUC-256 with a computational complexity that is below exhaustive key search.
###### Diana Maimut, Alexandru Stefan Mega
ePrint Report
Particular instantiations of the Offset Merkle Damgaard authenticated encryption scheme (OMD) represent highly secure alternatives for AES-GCM. It is already a fact that OMD can be efficiently implemented in software. Given this, in our paper we focus on speeding-up OMD in hardware, more precisely on FPGA platforms. Thus, we propose a new OMD instantiation based on the compression function of BLAKE2b. Moreover, to the best of our knowledge, we present the first FPGA implementation results for the SHA-512 instantiation of OMD as well as the first architecture of an online authenticated encryption system based on OMD.
###### Patrick Leu, Mridula Singh, Marc Roeschlin, Kenneth G. Paterson, Srdjan Capkun
ePrint Report
Secure distance measurement and therefore secure Time-of-Arrival (ToA) measurement is critical for applications such as contactless payments, passive-keyless entry and start systems, and navigation systems. This paper initiates the study of Message Time of Arrival Codes (MTACs) and their security. MTACs represent a core primitive in the construction of systems for secure ToA measurement. By surfacing MTACs in this way, we are able for the first time to formally define the security requirements of physical-layer measures that protect ToA measurement systems against attacks. Our viewpoint also enables us to provide a unified presentation of existing MTACs (such as those proposed in distance-bounding protocols and in a secure distance measurement standard) and to propose basic principles for protecting ToA measurement systems against attacks that remain unaddressed by existing mechanisms. We also use our perspective to systematically explore the tradeoffs between security and performance that apply to all signal modulation techniques enabling ToA measurements.
###### Mridula Singh, Patrick Leu, AbdelRahman Abdou, Srdjan Capkun
ePrint Report
Mobile autonomous systems, robots, and cyber-physical systems rely on accurate positioning information. To conduct distance-measurement, two devices exchange signals and, knowing these signals propagate at the speed of light, the time of arrival is used for distance estimations. Existing distance- measurement techniques are incapable of protecting against adversarial distance enlargement—a highly devastating tactic in which the adversary reissues a delayed version of the signals transmitted between devices, after distorting the authentic signal to prevent the receiver from identifying it. The adversary need not break crypto, nor compromise any upper- layer security protocols for mounting this attack. No known solution currently exists to protect against distance enlargement. We present Ultra-Wideband Enlargement Detection (UWB-ED), a new modulation technique to detect distance enlargement attacks, and securely verify distances between two mutually trusted devices. We analyze UWB-ED under an adversary that injects signals to block/modify authentic signals. We show how UWB-ED is a good candidate for 802.15.4z Low Rate Pulse and the 5G standard.

#### 25 November 2019

###### Gandhinagar, India, 3 December - 7 December 2019
Event Calendar
Event date: 3 December to 7 December 2019


text:
# DATA ACQUISITION SYSTEM FOR DIODE LASER KINETIC SPECTROSCOPY AND APPLICATIONS TO HOCO AND ETHYL RADICALS

Please use this identifier to cite or link to this item: http://hdl.handle.net/1811/12465

Files Size Format View
1991-RF-04.jpg 105.4Kb JPEG image

 Title: DATA ACQUISITION SYSTEM FOR DIODE LASER KINETIC SPECTROSCOPY AND APPLICATIONS TO HOCO AND ETHYL RADICALS Creators: Johnson, Philip M.; Fawzy, Wafaa M.; Sears, Trevor J. Issue Date: 1991 Publisher: Ohio State University Abstract: We have developed a new data acqisition system for diode laser spectrometers used to measure spectra of transient molecules formed photolytically using a pulsed laser. The new system employs a novel segmented refective chopper wheel whose rotation is synchronized to the photolysis laser firing. The wheel splits the time between photolysis laser shots into four slices and three spatially scparate beams which measure (i) the transient sample of interest (ii) a reference gas spectrum and (iii) an \’{e}talon spectrum. The three beams are recombined on the element of a single detector, amplified and passed to a CAMAC programmable transient recorder controlled by a PC. We are able to measure the sample, reference and \’{e}talon spectra and the $I_{0}$ level on every laser shot thereby improving both the speed and accuracy of the mesurements. We illustrate the results by reference to new spectra of the HOCO and ethyl radicals. Description: Author Institution: Department of Chemistry, State University of New York; Department of Chemistry, Brookhaven National Laboratory URI: http://hdl.handle.net/1811/12465 Other Identifiers: 1991-RF-4

format: plain


text:
# regtools

## Novel tools tools for linear, nonlinear and nonparametric regression.

These tools are associated with my book, From Linear Models to Machine Learning: Statistical Regression and Classification, N. Matloff, CRC, 2017 (recipient of the Technometrics Eric Ziegel Award for Best Book Reviewed in 2017).

The tools are useful in general, independently of the book.

NOTE: See also our qeML package – Quick and Easy Machine Learning.

## FEATURES:

• Innovative graphical tools for assessing fit in linear and nonlinear parametric models, via nonparametric methods. Model evaluation, examination of quadratic effects, investigation of nonhomogeneity of variance.

• Tools for multiclass classification, parametric and nonparametric, for any number of classes. One vs. All and All vs. All paradigms. Novel adjustment for artificially balanced (or undesirably imbalanced) data.

• Nonparametric regression for general dimensions in predictor and response variables, using k-Nearest Neighbors (k-NN). Local-linear option to deal with edge aliasing. Allows for user-specified smoothing method. Allows for accelerated exploration of multiple values of k at once. Tool to aid in choosing k.

• Extension to nonlinear parametric regression of Eicker-White technique to handle heteroscedasticity.

• Utilities for conversion of time series data to rectangular form, enabling lagged prediction by lm() or other regression model.

• Linear regression, PCA and log-linear model estimation in missing-data setting, via the Available Cases method. (For Prediction contexts, see our toweranNA package.)

• Utilities for conversion between factor and dummy variable forms, useful since among various regression packages, some use factors while some others use dummies. (The lars package is an example of the latter case.)

• Misc. tools, e.g. to reverse the effects of an earlier call to scale().

• Nicer implementation of ridge regression, with more meaningful scaling and better plotting.

• Interesting datasets.

## EXAMPLE: PARAMETRIC MODEL FIT ASSESSMENT

The fit assessment techniques in regtools gauge the fit of parametric models by comparing to nonparametric ones. Since the latter are free of model bias, they are very useful in assessing the parametric models.

Let’s take a look at the included dataset prgeng, some Census data for California engineers and programmers in the year 2000. The response variable in this example is wage income, and the predictors are age, gender, number of weeks worked, and dummy variables for MS and PhD degrees. You can read the details of the data by typing

> ?prgeng

One of the package’s graphical functions for model fit assessment plots the parametric (e.g. lm()) values against the nonparametric fit via k-NN. Let’s try this on the Census data.

The package includes three versions of the dataset: The original; a version with categorical variables in dummy form; and a version with categorical variables in R factor form. Since the k-NN routines require dummies, we’ll use that first version, peDumms.

We need to generate the parametric and nonparametric fits, then call parvsnonparplot():

data(peDumms)
pe1 <- peDumms[c('age','educ.14','educ.16','sex.1','wageinc','wkswrkd')]
lmout <- lm(wageinc ~ .,data=pe1)
xd <- preprocessx(pe1[,-5],10)  # prep for k-NN, k <= 10
knnout <- knnest(pe1$wageinc,xd,10) parvsnonparplot(lmout,knnout) We see above how the k-NN code is used. We first call preprocessx() to determine the nearest neighbors of each data point. Here k is 10, so we can later compute various k-NN fits for k anywhere from 1 to 10. The actual fit is done by knnest(). Then parvsnonparplot() plots the linear model fit against the nonparametric one.. Again, since the latter is model-free, it serves as a good assessment of the fit of the linear model. There is quite a bit suggested in this picture: • There seems to be some overfitting near the low end, and quite substantial underfitting at the high end. • There are intriguing “streaks” or “tails” of points, suggesting the possible existence of small but important subpopulations. Moreover, the plot suggests two separate large subpopulations, for wages less than or greater than about$40,000, possibly related to full- vs. part-time employment.

• There appear to be a number of people with 0 wage income. Depending on the goals of our analysis, we might consider removing them.

Let’s now check the classical assumption of homoscedasticity, meaning that the conditional variance of Y given X is constant. The function nonparvarplot() plots the estimated conditional variance against the estimated conditional mean, both computed nonparametrically:

Though we ran the plot thinking of the homoscedasticity assumption, this is much more remarkable, confirming that there are interesting subpopulations within this data. These may correspond to different occupations, something to be investigated.

The package includes various other graphical diagnostic functions.

By the way, violation of the homoscedasticity assumption won’t invalidate the estimates in our linear model. They still will be statistically consistent. But the standard errors we compute, and thus the statistical inference we perform, will be affected. This is correctible using the Eicker-White procedure, which for linear models is available in the car and sandwich packagers. Our package here also extends this to nonlinear parametric models, in our function nlshc() (the validity of this extension is shown in the book).

## EXAMPLE; OVA VS. AVA IN MULTICLASS PROBLEMS

A very popular prediction method in 2-class problems is to use logistic (logit) regression. In analyzing click-through patterns of Web users, for instance, we have 2 classes, Click and Nonclick. We might fit a logistic model for Click, given user Web history, demographics and so on. Note that logit actually models probabilities, e.g. the probability of Click given the predictor variables.

But the situation is much less simple in multiclass settings. Suppose our application is recognition of hand-written digits (a famous machine learning example). The predictor variables are pixel patterns in images. There are two schools of thought on this:

• One vs. All (OVA): We would run 10 logistic regression models, one for predicting ‘0’ vs. non-‘0’, one for ‘1’ vs. non-‘1’, and so on. For a particular new image to be classified, we would thus obtain 10 estimated conditional probabilities. We would then guess the digit for this image to be the digit with the highest estimated conditional probability.

• All vs. All (AVA): Here we would run C(10,2) = 45 logit analyses, one for each pair of digits. There would be one for ‘0’ vs. ‘1’, one for ‘0’ vs. ‘2’, etc., all the way up through ‘8’ vs. ‘9’. In each case there is a “winner” for our new image to be predicted, and in the end we predict the new image to be whichever digit has the most winners.

Many in the machine learning literature recommend AVA over OVA, on the grounds that there might be linear separability (in the statistical sense) in pairs but not otherwise. My book counters by noting that such a situation could be remedied under OVA by adding quadratic terms to the logit models.

At any rate, the regtools package gives you a choice, OVA or AVA, for both parametric and nonparametric methods. For example, avalogtrn() and avalogpred() do training and prediction operations for logit with AVA.

Let’s look at an example, again using the Census data from above. We’ll predict occupation from age, sex, education (MS, PhD, other) wage income and weeks worked.

data(peFactors)
pef <- peFactors
pef1 <- pef[,c('age','educ','sex','wageinc','wkswrkd','occ')]
# "Y" must be in last column, class ID 0,1,2,...; convert from factor
pef1$occ <- as.numeric(pef1$occ)
pef1$occ <- pef1$occ - 1
pef2 <- pef1
# create the education, gender dummy varibles
pef2$ms <- as.integer(pef2$educ == 14)
pef2$phd <- as.integer(pef2$educ == 16)
pef2$educ <- NULL pef2$sex <- as.integer(pef2$sex == 1) pef2 <- pef2[,c(1,2,3,4,6,7,5)] ovaout <- ovalogtrn(6,pef2) # estimated coefficients, one set ofr each of the 6 classes ovaout # prints 0 1 2 (Intercept) -9.411834e-01 -6.381329e-01 -2.579483e-01 xage 9.090437e-03 -3.302790e-03 -2.205695e-02 xsex -5.187912e-01 -1.122531e-02 -9.802006e-03 xwageinc -6.741141e-06 -4.609168e-06 5.132813e-06 xwkswrkd 5.058947e-03 -2.247113e-03 2.623924e-04 xms -5.201286e-01 -4.272846e-01 5.280520e-01 xphd -3.302821e-01 -8.035287e-01 3.531951e-01 3 4 5 (Intercept) -3.370758e+00 -3.322356e+00 -4.456788e+00 xage -2.193359e-03 -1.206640e-02 3.323948e-02 xsex -7.856923e-01 5.173516e-01 1.175657e+00 xwageinc -4.076872e-06 2.033175e-06 1.831774e-06 xwkswrkd 1.311084e-02 5.517912e-04 2.794453e-03 xms -1.797544e-01 9.947253e-02 2.705293e-01 xphd -3.883463e-01 4.967115e-01 4.633907e-01 # predict the occupation of a woman, age 35, no MS/PhD, inc 60000, 52 # weeks worked ovalogpred(ovaout,matrix(c(35,0,60000,52,0,0),nrow=1)) # outputs class 2, Census occupation code 102 [1] 2 With the optional argument probs=TRUE, the call to ovalogpred() will also return the conditional probabilities of the classes, given the predictor values, in the R attribute ‘probs’. Here is the AVA version: avaout <- avalogtrn(6,pef2) avaout # prints 1,2 1,3 1,4 1,5 (Intercept) -1.914000e-01 -4.457460e-01 2.086223e+00 2.182711e+00 xijage 8.551176e-03 2.199740e-02 1.017490e-02 1.772913e-02 xijsex -3.643608e-01 -3.758687e-01 3.804932e-01 -8.982992e-01 xijwageinc -1.207755e-06 -9.679473e-06 -6.967489e-07 -4.273828e-06 xijwkswrkd 4.517229e-03 4.395890e-03 -9.535784e-03 -1.543710e-03 xijms -9.460392e-02 -7.509925e-01 -2.702961e-01 -5.466462e-01 xijphd 3.983077e-01 -5.389224e-01 7.503942e-02 -7.424787e-01 1,6 2,3 2,4 2,5 (Intercept) 3.115845e+00 -2.834012e-01 2.276943e+00 2.280739e+00 xijage -2.139193e-02 1.466992e-02 1.950032e-03 1.084527e-02 xijsex -1.458056e+00 3.720012e-03 7.569766e-01 -5.130827e-01 xijwageinc -5.424842e-06 -9.709168e-06 -1.838009e-07 -4.908563e-06 xijwkswrkd -2.526987e-03 9.884673e-04 -1.382032e-02 -3.290367e-03 xijms -6.399600e-01 -6.710261e-01 -1.448368e-01 -4.818512e-01 xijphd -6.404008e-01 -9.576587e-01 -2.988396e-01 -1.174245e+00 2,6 3,4 3,5 3,6 (Intercept) 3.172786e+00 2.619465e+00 2.516647e+00 3.486811e+00 xijage -2.908482e-02 -1.312368e-02 -3.051624e-03 -4.236516e-02 xijsex -1.052226e+00 7.455830e-01 -5.051875e-01 -1.010688e+00 xijwageinc -5.336828e-06 1.157401e-05 1.131685e-06 1.329288e-06 xijwkswrkd -3.792371e-03 -1.804920e-02 5.606399e-04 -3.217069e-03 xijms -5.987265e-01 4.873494e-01 2.227347e-01 5.247488e-02 xijphd -1.140915e+00 6.522510e-01 -2.470988e-01 -1.971213e-01 4,5 4,6 5,6 (Intercept) -9.998252e-02 6.822355e-01 9.537969e-01 xijage 1.055143e-02 -2.273444e-02 -3.906653e-02 xijsex -1.248663e+00 -1.702186e+00 -4.195561e-01 xijwageinc -4.986472e-06 -7.237963e-06 6.807733e-07 xijwkswrkd 1.070949e-02 8.097722e-03 -5.808361e-03 xijms -1.911361e-01 -3.957808e-01 -1.919405e-01 xijphd -8.398231e-01 -8.940497e-01 -2.745368e-02 # predict the occupation of a woman, age 35, no MS/PhD, inc 60000, 52 # weeks worked avalogpred(6,ovaout,matrix(c(35,0,60000,52,0,0),nrow=1)) # outputs class 2, Census occupation code 102 ## EXAMPLE: ADJUSTMENT OF CLASS PROBABILITIES IN CLASSIFICATION PROBLEMS The LetterRecognition dataset in the mlbench package lists various geometric measurements of capital English letters, thus another image recognition problem. One problem is that the frequencies of the letters in the dataset are not similar to those in actual English texts. The correct frequencies are given in the ltrfreqs dataset included here in the regtools package. In order to adjust the analysis accordingly, the ovalogtrn() function has an optional truepriors argument. For the letters example, we could set this argument to ltrfreqs. (The term priors here does refer to a subjective Bayesian analysis. It is merely a standard term for the class probabilities.) ## MULTICLASS CLASSIFICATION WITH k-NN In addition to use in linear regression graphical diagnostics, k-NN can be very effective as a nonparametric regression/machine learning tool. I would recommend it in cases in which the number of predictors is moderate and there are nonmonotonic relations. (See also our polyreg package.) Let’s continue the above example on predicting occupation, using k-NN. The three components of k-NN analysis in regtools are: 1. preprocessx(): This finds the sets of nearest neighbors in the training set, for all values of k up to a user-specified maximum. This facilitates the user’s trying various values of k. 2. knnest(): This fits the regression model. 3. knnpred(): This does prediction on the user’s desired set of points of new cases. Since k-NN involves finding distances between points, our data must be numeric, not factors. This means that in pef2, we’ll need to replace the occ column by a matrix of dummy variables. Utilities in the regtools package make this convenient: occDumms <- factorToDummies(as.factor(pef2$occ),'occ',omitLast=FALSE)
pef3 <- cbind(pef2[,-7],occDumms)

Note that in cases in which “Y” is multivariate, knnest() requires it in multivariate form. Here “Y” is 6-variate, so we’ve set the last 6 columns of pef3 to the corresponding dummies.

Many popular regression packages, e.g. lars for the LASSO, require data in numeric form, so the regtools’ conversion utilities are quite handy.

Now fit the regression model:

kout <- knnest(pef3[, -(1:6)],xd,10)

One of the components of kout is the matrix of fitted values:

> head(kout\$regest)
occ.0 occ.1 occ.2 occ.3 occ.4 occ.5
[1,]   0.2   0.4   0.2     0   0.0   0.2
[2,]   0.2   0.5   0.2     0   0.0   0.1
[3,]   0.5   0.1   0.3     0   0.1   0.0
[4,]   0.3   0.4   0.1     0   0.0   0.2
[5,]   1.0   0.0   0.0     0   0.0   0.0
[6,]   0.2   0.4   0.2     0   0.0   0.2

So for example the conditional probability of Occupation 4 for the third observation is 0.1.

Now let’s do the same prediction as above:

> predict(kout,matrix(c(35,0,60000,52,0,0),nrow=1),TRUE)
occ.0 occ.1 occ.2 occ.3 occ.4 occ.5
0.1   0.4   0.5   0.0   0.0   0.0

These are conditional probabilities. The most likely one is Occupation 2.

The TRUE argument was to specify that we need to scale the new cases in the same way the original data were scaled.

By default, our k-NN routines find the mean Y in the neighborhood. Another option is to do local linear smoothing. Among other things, this may remedy aliasing at the edges of the data. This should be done with a value of k much larger than the number of predictor variables.

## EXAMPLE: RECTANGULARIZATION OF TIME SERIES

This allows use of ordinary tools like lm() for prediction in time series data. Since the goal here is prediction rather than inference, an informal model can be quite effective, as well as convenient.

The basic idea is that x[i] is predicted by x[i-lg], x[i-lg+1], x[i-lg+2], i… x[i-1], where lg is the lag.

xy <- TStoX(Nile,5)
#      [,1] [,2] [,3] [,4] [,5] [,6]
# [1,] 1120 1160  963 1210 1160 1160
# [2,] 1160  963 1210 1160 1160  813
# [3,]  963 1210 1160 1160  813 1230
# [4,] 1210 1160 1160  813 1230 1370
# [5,] 1160 1160  813 1230 1370 1140
# [6,] 1160  813 1230 1370 1140  995
#  [1] 1120 1160  963 1210 1160 1160  813 1230 1370 1140  995  935 1110  994 1020
# [16]  960 1180  799  958 1140 1100 1210 1150 1250 1260 1220 1030 1100  774  840
# [31]  874  694  940  833  701  916

Try lm():

lmout <- lm(xy[,6] ~ xy[,1:5])
lmout
...
Coefficients:
Coefficients:
(Intercept)   xy[, 1:5]1   xy[, 1:5]2   xy[, 1:5]3   xy[, 1:5]4   xy[, 1:5]5
307.84354      0.08833     -0.02009      0.08385      0.13171      0.37160

Predict the 101st observation:

cfs <- coef(lmout)
cfs %*% c(1,Nile[96:100])
#          [,1]
# [1,] 784.4925


text:
Run Multi-Threading Examples and Speed Tests

Purpose
Runs the CppAD multi-threading examples and timing tests:

build
We use build for the directory where you run the cmake command.

If the cmake command output indicates that bthread, pthread, or openmp is available, you can run the program below with threading equal to bthread, pthread, or openmp respectively.

program
We use the notation program for        example_multi_thread_threading
Running Tests
You can build this program and run the default version of its test parameters by executing the following commands:       cd build      make check_program  After this operation, in the directory       build/example/multi_thread/threading  you can execute the following commands: . ./program a11c ./program simple_ad ./program team_example ./program harmonic     test_time max_threads mega_sum ./program multi_newton test_time max_threads \      num_zero num_sub num_sum use_ad
a11c
The examples a11c_openmp.cpp , a11c_bthread.cpp , and a11c_pthread.cpp demonstrate simple multi-threading, without algorithmic differentiation.

team_example
The team_example.cpp routine demonstrates simple multi-threading with algorithmic differentiation and using a team of threads .

harmonic
The harmonic_time routine preforms a timing test for a multi-threading example without algorithmic differentiation using a team of threads.

test_time
Is the minimum amount of wall clock time that the test should take. The number of repeats for the test will be increased until this time is reached. The reported time is the total wall clock time divided by the number of repeats.

If the argument max_threads is a non-negative integer specifying the maximum number of threads to use for the test. The specified test is run with the following number of threads:       num_threads = 0 , ... , max_threads  The value of zero corresponds to not using the multi-threading system.

mega_sum
The command line argument mega_sum is an integer greater than or equal one and has the same meaning as in harmonic_time .

multi_newton
The multi_newton_time routine preforms a timing test for a multi-threading example with algorithmic differentiation using a team of threads.

test_time
Is the minimum amount of wall clock time that the test should take. The number of repeats for the test will be increased until this time is reached. The reported time is the total wall clock time divided by the number of repeats.

If the argument max_threads is a non-negative integer specifying the maximum number of threads to use for the test. The specified test is run with the following number of threads:       num_threads = 0 , ... , max_threads  The value of zero corresponds to not using the multi-threading system.

num_zero
The command line argument num_zero is an integer greater than or equal two and has the same meaning as in multi_newton_time .

num_sub
The command line argument num_sub is an integer greater than or equal one and has the same meaning as in multi_newton_time .

num_sum
The command line argument num_sum is an integer greater than or equal one and has the same meaning as in multi_newton_time .

The command line argument use_ad is either true or false and has the same meaning as in multi_newton_time .
Source  # include <cppad/cppad.hpp> # include <cmath> # include <cstring> # include <ctime> # include "team_thread.hpp" # include "team_example.hpp" # include "harmonic.hpp" # include "multi_atomic.hpp" # include "multi_newton.hpp" extern bool a11c(void); extern bool simple_ad(void); namespace { size_t arg2size_t( const char* arg , int limit , const char* error_msg ) { int i = std::atoi(arg); if( i >= limit ) return size_t(i); std::cerr << "value = " << i << std::endl; std::cerr << error_msg << std::endl; exit(1); } double arg2double( const char* arg , double limit , const char* error_msg ) { double d = std::atof(arg); if( d >= limit ) return d; std::cerr << "value = " << d << std::endl; std::cerr << error_msg << std::endl; exit(1); } } int main(int argc, char *argv[]) { using CppAD::thread_alloc; bool ok = true; using std::cout; using std::endl; // commnd line usage message const char* usage = "./<thread>_test a11c\n" "./<thread>_test simple_ad\n" "./<thread>_test team_example\n" "./<thread>_test harmonic test_time max_threads mega_sum\n" "./<thread>_test multi_atomic test_time max_threads num_solve\n" "./<thread>_test multi_newton test_time max_threads \\\n" " num_zero num_sub num_sum use_ad\\\n" "where <thread> is bthread, openmp, or pthread"; // command line argument values (assign values to avoid compiler warnings) size_t num_zero=0, num_sub=0, num_sum=0; bool use_ad=true; // put the date and time in the output file std::time_t rawtime; std::time( &rawtime ); const char* gmt = std::asctime( std::gmtime( &rawtime ) ); size_t len = size_t( std::strlen(gmt) ); cout << "gmtime = '"; for(size_t i = 0; i < len; i++) if( gmt[i] != '\n' ) cout << gmt[i]; cout << "';" << endl; // CppAD version number cout << "cppad_version = '" << CPPAD_PACKAGE_STRING << "';" << endl; // put the team name in the output file cout << "team_name = '" << team_name() << "';" << endl; // print command line as valid matlab/octave cout << "command = '" << argv[0]; for(int i = 1; i < argc; i++) cout << " " << argv[i]; cout << "';" << endl; ok = false; const char* test_name = ""; if( argc > 1 ) test_name = *++argv; bool run_a11c = std::strcmp(test_name, "a11c") == 0; bool run_simple_ad = std::strcmp(test_name, "simple_ad") == 0; bool run_team_example = std::strcmp(test_name, "team_example") == 0; bool run_harmonic = std::strcmp(test_name, "harmonic") == 0; bool run_multi_atomic = std::strcmp(test_name, "multi_atomic") == 0; bool run_multi_newton = std::strcmp(test_name, "multi_newton") == 0; if( run_a11c || run_simple_ad || run_team_example ) ok = (argc == 2); else if( run_harmonic || run_multi_atomic ) ok = (argc == 5); else if( run_multi_newton ) ok = (argc == 8); if( ! ok ) { std::cerr << "test_name = " << test_name << endl; std::cerr << "argc = " << argc << endl; std::cerr << usage << endl; exit(1); } if( run_a11c || run_simple_ad || run_team_example ) { if( run_a11c ) ok = a11c(); else if( run_simple_ad ) ok = simple_ad(); else ok = team_example(); if( thread_alloc::free_all() ) cout << "free_all = true;" << endl; else { ok = false; cout << "free_all = false;" << endl; } if( ok ) cout << "OK = true;" << endl; else cout << "OK = false;" << endl; return ! ok; } // test_time double test_time = arg2double( *++argv, 0., "run: test_time is less than zero" ); // max_threads size_t max_threads = arg2size_t( *++argv, 0, "run: max_threads is less than zero" ); size_t mega_sum = 0; // assignment to avoid compiler warning size_t num_solve = 0; if( run_harmonic ) { // mega_sum mega_sum = arg2size_t( *++argv, 1, "run: mega_sum is less than one" ); } else if( run_multi_atomic ) { // num_solve num_solve = arg2size_t( *++argv, 1, "run: num_solve is less than one" ); } else { ok &= run_multi_newton; // num_zero num_zero = arg2size_t( *++argv, 2, "run: num_zero is less than two" ); // num_sub num_sub = arg2size_t( *++argv, 1, "run: num_sub is less than one" ); // num_sum num_sum = arg2size_t( *++argv, 1, "run: num_sum is less than one" ); // use_ad ++argv; if( std::strcmp(*argv, "true") == 0 ) use_ad = true; else if( std::strcmp(*argv, "false") == 0 ) use_ad = false; else { std::cerr << "run: use_ad = '" << *argv; std::cerr << "' is not true or false" << endl; exit(1); } } // run the test for each number of threads cout << "time_all = [" << endl; for(size_t num_threads = 0; num_threads <= max_threads; num_threads++) { double time_out; // run the requested test if( run_harmonic ) ok &= harmonic_time(time_out, test_time, num_threads, mega_sum); else if( run_multi_atomic ) ok &= multi_atomic_time(time_out, test_time, num_threads, num_solve); else { ok &= run_multi_newton; ok &= multi_newton_time( time_out , test_time , num_threads , num_zero , num_sub , num_sum , use_ad ); } // time_out cout << "\t" << time_out << " % "; // num_threads if( num_threads == 0 ) cout << "no threading" << endl; else cout << num_threads << " threads" << endl; } cout << "];" << endl; // if( thread_alloc::free_all() ) cout << "free_all = true;" << endl; else { ok = false; cout << "free_all = false;" << endl; } if( ok ) cout << "OK = true;" << endl; else cout << "OK = false;" << endl; return ! ok; }


text:
# Lucky numbers

Discrete Mathematics Level 4

A seven digit number $\overline{ABCDEFG}$ is called lucky number if $$\overline{ABC} = \overline{DEF}$$ and/or $$\overline{ABC} = \overline{EFG}$$. Find the number of all lucky numbers.

×


text:
# GitHub

This is just a quick announcement that we have migrated all our projects like PGSolver, MLSolver, FADecider and so on to GitHub. This allows you to get the newest versions of our software easily and to contribute your own code to our codebase.

Assuming that you might be an avid user of Subversion, you might want to read this tutorial which explains Git from a Subversion-point-of-view.

# Once upon a time in Japan, one year ago

The following is an old blog post from last year that I’ve posted on a different blog that I’ve now closed. In restrospective not much has changed since then in my views. I have to admit, however, that some thoughts are fairly pathetic – I guess I was still overwhelmed by everything when I wrote it.

I’ve spent the first couple of days in Tokyo and went then to Kyoto. Tokyo is an incredibly large city packed with skyscrapers. If you go up one of the high buildings around the center to get a good view, it seems like the city is never ending, like the whole world is covered with skyscrapers. Like the Death Star (without being dramatic here). It’s almost surreal. Let there be no doubt, the skyline of New York is one of the most impressive sceneries, but compared to Tokyo, Manhattan is just a very small district in this gigantic city. It has multilayered streets all over the place. It is also the first city I’ve seen that has cars but no parking spots.

I’ve spent the rest of my time in Kyoto. It is the old royal city south of Tokyo, much smaller and greener than Tokyo. The best way to get around there is to get yourself a bike. My colleague was so friendly to give me one of his bikes which made it perfectly easy for me to visit all the places I was looking for. Japan in general and Kyoto in particular are beautiful. The people devote quite some attention to small little details. Every tree has been brought into perfect shape and each plant’s color is intense. Lime green. Crimson red. It’s just a form of art. It’s like stepping into a science fiction movie. Which sounds cliche and overgeneralizing but to me it was.

As you may know, one of the most important occasions for Japanese people is the so-called cherry blossom season, which is a two weeks long period in which the cherry blossom trees bloom. It usually takes place by the end of March, but this year the trees started to bloom a little later, so I was lucky enough to enjoy the trees at full peak. People are sitting under the trees and have picnics. It is a national celebration called “Hanami”, and most Japanese people get a warm tone in their voice when talking about their cherry blossom trees. You don’t really get it at first, but you start to understand after some time that the Hanami means a lot to them. It also shows you how much of a national tragedy Fukushima was, as they didn’t celebrate the Hanami last year.

When you go by the river in Kyoto, you see many people sitting around just looking at the river or the trees besides the river. They just enjoy the beauty of the moment. We have somehow forgotten how this works; we are always obsessed by using our time as efficiently as possible, even our free time.

For me, life has always been about choosing between hedonism and delayed gratification, and I think that is pretty typical for Western cultures. Hedonism, I always thought, might give you an instant gratification, a good fun, without giving your life any meaning. You’re missing the big picture and you might as well lose yourself in perpetuating meaningless stuff over and over again. Delayed gratification, on the other hand, seems to give you the big picture. It allows you to focus on doing something you might not enjoy too much, but you are promised to be rewarded later on for doing it.

I’ve always interpreted the carpe diems along these lines. Steve Job’s quote “Remembering that I’ll be dead soon is the most important tool I’ve ever encountered to help me make the big choices in life” seems to support this interpretation. You should always have the big picture in mind.

But what I now begin to understand is that delayed gratification tends to build up endless chains of in-order-to-thinking, postponing the gratification possibly infinitely long. “I’ll be dead soon” also means that you might as well be dead without being ever gratified for whatever it is you’re doing. Your big picture might not even work out as you planed it, and then you’re screwed.

Looking at the Japanese culture, I now realize that it is neither necessary nor desirable to choose between hedonism and delayed gratification. You should focus on the big picture, but you should also try to enjoy life every day. There is so much beauty in this world. We just need to relearn how to see and enjoy it. Today might by your last day, so don’t waste it doing stuff that you hate. Don’t waste it following other people’s dreams. I might be completely off the point to identify this as being a Japenese thing. (Edit: I am now pretty sure I was off the point.) Maybe it was just me thinking along these lines when I was there.

Religion in Japan obviously is quite different from ours. The original Japanese religion is Shinto and now coexists with Buddhism. There are many temples for both religions and some of them are even mixed. The Shinto religion is a polytheistic nature religion, where you basically have gods for everything. But instead of going there to just praise a lord, you pray for health or fertility or good luck in an exam. Your relationship with the god is much more demanding from your site. What I found particularly sympathetic were trees that they’ve put in front of the temples on which everybody can attach small papers that you want the god to take care of. If you think of fortune cookies, you basically take the good wishes with you and let the restaurant deal with all the bad stuff. It’s an optimistic and non-fatalistic way to deal with the future.

I probably don’t have to tell you much about the food: it’s incredibly good and fresh, and the Japanese dishes that we get in the Western world are only just ten percent of the different kinds of dishes that you get here. Many of them were exotic but also very tasteful. Be careful when trying Japanese sea cucumber though, which tastes pretty terrible, at least from my point of view. And even some Japanese people admitted that only a small fraction of them actually likes sea cucumber, so I think you’ll be on the safe side if you don’t like it.

In comparison to Japanese dishes, our food looks like it’s prepared by some uncivilized barbaric tribe. Instead of using elegant chop sticks, we get a set of tools to work on the food in order to get the stuff into manageable pieces. Even when you consider Western food like steaks or whatever, it’s a good question to ask why it’s not already cut. It would be much nicer to eat.

Everything, every ritual is carried out with the uttermost perfection. If people hand you stuff, they always turn it around in front of you before giving it you so that you can see the item in the right order. And they always give it you with both hands. This gesture somehow turns a simple action like giving you some stuff into an almost transcendental celebration.

People seem to have a fundamentally different understanding of how people should behave in society. Let me give you two examples. The public places and streets in Kyoto have no trash bins, but there is also no trash lying around. Not a single thing. I first thought that you’re probably going to be punished quite badly when being caught throwing stuff on the ground, but that’s not the thing. People see public places like their own gardens. The public is themselves. So why should they throw garbage on the ground? That just doesn’t make sense. Of course, our society has a completely different take on this. Throwing garbage on the ground in public places? As long as no one sees me, who cares?

Also small-scale stealing seems to be out of the picture. People let their bikes just stand around, leaving bags of stuff that they just bought in the baskets, and go into a shop to buy some other items. They just leave their bags and bikes without attendance. That’s amazing and it seems to just work like that.

People also seem to be generally friendly and kind. Although many do not speak English, people always try to help you, even if it takes them quite some time to accompany you to your desired destination. As a practical advice, you should take any directions that people give you with caution, as people sometimes rather give you a wrong direction than telling you that they don’t know where you should go. From what I’ve understood it’s about not giving you negative feedback. It’s about not losing your face, and that goes for both parties.

So go with the flow and try to be polite and sensitive yourself. I’ll definitely come back soon.

# Metapost Library for drawing Graphs

We use a custom-built library to create all the game graphs that you see in our papers and animations that allows you to specify nodes, edges, annotations among a couple of other things. We have made the library public so people can play around with it as well.

# New paper on Cunningham’s Rule & a new Wiki for TCS

David Avis and myself have just finished a paper on Cunningham’s Rule for solving linear programs, featuring an exponential lower bound. Have a look at the preprint here and let us know what you think.

# Scientific Sermon: Computing Winning Sets From Winning Strategies

[latexpage]
In our last post of the series, we have seen how to obtain winning strategies in polytime if all you can do is compute winning sets (without strategies) in polynomial time. In this post, we’ll try to solve a related problem: given a pair of strategies for both players that are guaranteed to be winning on the winning sets of the game, can we extract these winning sets in polynomial time? The answer is, as we will see, yes.

In order to simplify the problem, let $G$ be a parity game and $\sigma$ be a player 0 strategy. We can define everything accordingly for player 1.
Define the player 0 $\sigma$-winning set as follows:
$W_0(G,\sigma) = \{v \in V \mid \text{all \sigma-conforming plays starting in v are won by pl~0}\}$

It is easy to see that $W_0(G,\sigma) \subseteq W_0(G)$, and $W_0(G,\sigma) = W_0(G)$ iff $\sigma$ is a winning strategy on $W_0(G)$.

Hence, in order to solve our problem, it suffices to compute $W_0(G,\sigma)$.

Now we simplify our problem even more by considering the so-called strategy subgame. Given a game $G=(V,V_0,V_1,E,\Omega)$ and a player 0 strategy $\sigma$, the strategy subgame $G|_\sigma = (V,V_0,V_1,E’,\Omega)$ restricts the set of edges as follows:
$E’ = \{(v,w) \in E \mid v \in V_0 \Rightarrow \sigma(v) = w\}$
In other words all edges of player 1 remain in the game while all player 0 edges chosen by $\sigma$ are removed from the game.

It is not hard to see that $W_0(G,\sigma) = W_0(G|_\sigma)$, because the game on the right-hand side still includes the strategy $\sigma$. So we have a reduced our original problem to computing $W_0(G|_\sigma)$.

Why is that of any help? If you look closely, you’ll see that $W_0(G|_\sigma)$ is a so-called one-player game, i.e. a game in which at most one of the two players (in this case at most player 1) has more than one strategy. So our remaining task can be phrased as follows: How do we solve one-player parity games in polynomial time?

There are a bunch of algorithms that solve one-player parity games in polytime, but let us consider an algorithm very similar to the recursive algorithm that we have described earlier. You can also take a look at the Wikipedia page for an outline of the algorithm.

Our algorithm is recursive in the number of different priorities. If we only have one priority, we can immediately see who wins the whole game. If we have more than one priority, let $p$ be the largest one.

1. Case $p$ is odd: Let $P$ be the set of all nodes with priority $p$. We compute the $1$-attractor $U$ of $P$. It is not too hard to see that $U \subseteq W_1$ with the attractor strategy of player 1 on $U$ as winning strategy. We remove $U$ from the game and continue with the rest.
2. Case $p$ is even: Let $P$ be the set of all nodes with priority $p$. We compute the $0$-attractor $U$ of $P$ and remove it from the game, resulting in a game $G’$. We solve the game $G’$ by recursion and obtain winning sets $W_0’$ and $W_1’$. We compute the $1$-attractor $A$ in $G$ of $W_1’$ and remove it from the game as it is clearly won by player 1. This leaves us with $U \setminus A$ and $W_0′ \setminus A$.
We now claim that $W_0′ \setminus A$ is won by player 0. Assume it’s not. Then, there must be a player 1 escape going through $A \setminus W_0′ \cup U$ reaching $W_1’$. But since $A$ is an attractor and the game is a one-player game, this is impossible. Let $X$ be the player 0 attractor of $W_0′ \setminus A$. Hence, we can remove $X$ as a save win for player 0 from the game.
We are left with $U \setminus (A \cup X)$ with which we continue.

As an exercise, you can check that the algorithm runs in polytime.

In the next post of the series, we consider an assumption that you are allowed to make if you’re trying to find a polytime algorithm for solving parity games: you can assume that one of the two players, say player 0, wins the whole game. All you need to do, is to compute her winning strategy.

# Java Keystore Creation from SSL Certificate

For Java-based servers that use SSL, you are usually required to convert your SSL certificate to a Java Keystore. It took me some time to figure out the right parameters and tools to create it, so here is the shortcut to creating the file.

Requirements:

• Your domain name, i.e. “facebook” (without the top-level domain), which we will denote by [NAME] (we assume top-level domain “com” for the time being)
• A password for the keystore which you will need for the Java server, which we will denote by [PASSWORD]
• A program called keytool which should be part of your Java SDK
• The SSL certificate files “[NAME].com.crt”, “ca.key” and “gd_bundle.crt”

You can then go a head and execute the following to commands which will create the keystore file “[NAME].keystore” for you.

openssl pkcs12 -export -in [NAME].com.crt -inkey ca.key -out [NAME].p12 -name [NAME] -CAfile gd_bundle.crt -caname root -chain

# Applied Engineering: Exhaustive Search

In the last post of the series, we’ve introduced modules, functors and maps. We had ended with realization of the value assignment function that maps a given table assignment to a (ranking) value.

In this post, we will conclude the series and solve the optimal table assignment problem using OCaml. We will implement a function that searches through the space of potential table assignments to find (the) one with best possible value. We will use a very simple exhaustive search algorithm here.

First, we introduce a new module similar to the Map module we’ve already used previously. It models a set of objects and allows to add, remove, and find elements and to iterate over them efficiently. For our purposes, a set will be the right data structure for walking through the search space.

module IntSet = Set.Make(
struct
type t = int
let compare = compare
end
)

let int_list_to_set int_list =
List.fold_left (fun set_acc list_el -> IntSet.add list_el set_acc)
IntSet.empty int_list

As before, we have to specify a compare function, and we use the default one once again. We also add a function int_list_to_set that converts a list of integers to a set of integers by folding the list and adding one element at a time using IntSet.add while starting with the empty set IntSet.empty.

If we want to get the sets of people and seats, we could use the mapping function as follows:

let people_set = int_list_to_set (List.map (fun (x,_) -> x) people)
let seats_set = int_list_to_set (List.map (fun (x,_,_) -> x) table)

Before we can turn to the exhaustive search algorithm, we consider one last type that is particularly useful in functional programs: the option type. It is a box that can contain at most one instance of some other type – in other words, it’s either an empty box or a singleton. It is already defined by OCaml, but it can easily be redefined:

type 'a option = None | Some of 'a

You can use the type as follows:

let x = None
let y = Some 5
match option_variable with
None -> do_something
| Some i -> do_something_else

Back to our initial problem: finding an optimal table assignment. Just for fun, we will also try to find a worst table assignment, so the search algorithm should be given a comparison routine that allows the algorithm to select the more “appropriate” table assignment when comparing two.

We will therefore consider the following two comparison functions:

let better_selector assignment assignment' =
if assignment_value assignment > assignment_value assignment'
then assignment
else assignment'

let worse_selector assignment assignment' =
if assignment_value assignment > assignment_value assignment'
then assignment'
else assignment

Our exhaustive search algorithm will be called find_assignment, and it will be given one of the comparison routines as only parameter. We will then be able to create the following two convenience function searching for either a best or a worst assignment:

let best_assignment = find_assignment better_selector
let worst_assignment = find_assignment worse_selector

The basic idea of our exhaustive search algorithm is as follows. At any point in the algorithm we have four objects:

1. the currently “best” assignment (initially will be None),
2. a partial assignment (initially will be the empty map),
3. the set of empty seats  (initially will be the set of all seats), and
4. the set of persons without a seat (initially will be the set of all persons)

The algorithm will then proceed as follows. If there are no more people without a seat, the partial assignment (which is a full assignment at that point) will be compared with the currently best assignment, and the better one will be returned. If otherwise there are no more seats left, the algorithm will fail, because there are not enough seats for all persons. If there are still seats and persons left, the algorithm will pick the first person unseated and the first unoccupied seat, seat the person there, and recursively find the best assignment. Then, the algorithm will free the seat again, and seat the second person on the same seat and recursively find the best assignment again. This will be done for all persons unseated, so in the end, we’ll find a best assignment.

Here is the code:

let find_assignment selector =
let people_left = int_list_to_set (List.map (fun (x,_) -> x) people) in
let seats_left = int_list_to_set (List.map (fun (x,_,_) -> x) table) in
let rec find reference assignment people_left' seats_left' =
if IntSet.is_empty people_left' then
match reference with
None -> Some assignment
|   Some other_assignment -> Some (selector other_assignment assignment)
else if IntSet.is_empty seats_left' then
failwith "There are not enough seats!"
else
IntSet.fold (fun person reference' ->
let people_left'' = IntSet.remove person people_left' in
let seat = IntSet.choose seats_left' in
let seats_left'' = IntSet.remove seat seats_left' in
let assignment' = IntMap.add person seat assignment in
find reference' assignment' people_left'' seats_left''
) people_left' reference
in
match find None IntMap.empty people_left seats_left with
None -> failwith "There must be one assignment."
|   Some assignment -> assignment

So what do we get in the end? A best seating assignment gets a score of 7.5 and the assignment is:

Hank sits on seat #5
Karen sits on seat #4
Becka sits on seat #1
Mia sits on seat #2
Julian sits on seat #0
Trixi sits on seat #3

A worst seating assignment gets a score of -0.625 and the assignment is:

Hank sits on seat #0
Karen sits on seat #3
Becka sits on seat #1
Mia sits on seat #5
Julian sits on seat #4
Trixi sits on seat #2

Finally, the spammer got back to me again. I already thought I lost him, but there we go again. If you want to recap what happened, here are part 1 and part 2.

Guten Tag,

Wie geht es Ihnen?

Bis jetzt habe ich von Ihnen keine E-Mail bekommen.

bitte erwarte ich eine E-Mail von Sie.
Hoffe,dass alles gut lauft mit der Aanwalt.
Bitte sagen Sie mir mehr über der ablauf.

Mit freundlichen Grüssen
Ferdinand Arendt

Sehr geehrte Herr Arendt,

es geht mir gut, vielen Dank der Nachfrage. Wie geht es Ihnen?

Es verstört mich zu hören, dass Sie von mir keine E-Mail erhalten haben. Ich schrieb Ihnen am 22.01. und anschließend Ihrer Kollegin Frau Smith am 28.01. – offenbar sind einige der E-Mails nicht bei Ihnen eingetroffen. Diese neumodischen Kommunikationsformen sind aber auch unzuverlässig! Früher war alles besser. Selbst wir waren früher besser, nicht wahr? Aber ich schweife ab.

Ich hätte gehofft, dass Sie mir mehr über den Ablauf verraten könnten. Bis jetzt habe ich von Ihnen ja noch keine weiteren Unterlagen in der Angelegenheit erhalten. Wie sollen wir weiter verfahren?

P.S. Bestellen Sie Frau Smith meine besten Grüße.

Hochachtungsvoll,
Ihr Alexander Habicht

Sehr geehrter Herr Habicht,

Ich weiß nicht wie weit Herr Arendt Sie bereits in dem Fall in Kenntnis gesetzt hat und über welche Informationen Sie derzeit verfügen.
Wie bereits erwähnt wird das Erbe vom Nachlassgericht verwaltet. Da niemand Anspruch auf das Erbe erhoben hat, wurde vom Gericht ein Erbenermittler beauftragt einen Erben ausfindig zu machen. Leider haben seine Nachforschungen zu keinem eindeutigen Ergebnis geführt. Daher hat sich der Erbenermittler an Herrn Arendt gewandt.
Laut dem Ermittler gibt es zwischen Ihnen und dem Verstorbenen einen Zusammenhang, jedoch ist dieser nicht so eindeutig, dass er sich mit dem Ergebnis direkt an das Gericht wenden kann. Wie der Zusammenhang zustande kommt und welche Kriterien ausschlaggebend für sein Ergebnis sind, kann ich Ihnen zum jetzigen Zeitpunkt nicht sagen.
Er gab jedoch Herrn Arendt Ihre Kontaktdaten und bat ihn sich mit Ihnen in Verbindung zu setzen.
Wenn Sie das Erbe antreten möchten, wird der Erbenermittler eine Erklärung aufsetzen von der herausgeht, dass Sie der alleinige Erbe des Nachlasses sind und diese an das Gericht weiterleiten. Ich werde Sie in diesem Fall vertreten und beraten und beim Gericht einen Antrag auf einen Erbschein stellen. Da Sie als ein entfernter Verwandter des Erblassers eingetragen werden, benötigen Sie einen Erbschein. Dieser ist eine Urkunde, die Sie als Erben ausweist und mit der die Bank verpflichtet ist das Erbe an Sie freizugeben.
Um den Antrag stellen zu können, möchte ich Ihre Kontaktdaten aktualisieren.
Bitte füllen Sie dazu das Formular im Anhang aus und senden mir dieses zusammen mit Ihrer Geburtsurkunde per E-Mail zurück.
Wenn Sie noch Fragen oder Anliegen haben, kontaktieren Sie mich bitte.
Sie erreichen mich täglich von 9.00 Uhr bis 11.00 Uhr und von 12.00 Uhr bis 14.00 Uhr.
Ansonsten schreiben Sie mir eine E-Mail und ich versuche mich schnellstmöglich zu melden.

Mit freundlichen Grüßen
Jenna Smith

Sehr geehrte Frau Smith,

vielen Dank für Ihre E-Mail. Herr Arendt hat mich bis jetzt nur über die ungefähre Höhe des Erbes und eine befremdliche Verteilung des Erbes informiert. Unter anderem war Herr Arendts Vorschlag, 60% des Erbes an sich selbst zu überweisen. Das erscheint mir, vorsichtig gesprochen, doch eine etwas übertriebene und unübliche Vergütungspraxis zu sein.

Es freut mich zu hören, dass das Erbe bereits von einem Nachlassgericht verwaltet wird. Wären Sie so freundlich, mir die Adresse des Gerichts sowie den mit dem Fall betrauten Sachbearbeiter zu nennen? Ich würde mich dann direkt schriftlich mit dem Gericht ins Benehmen setzen und weitere Unterlagen einfordern.

Ich kann es kaum erwarten mehr über den nicht so eindeutigen – aber offenbar dennoch klar sichtbaren – Zusammenhang zwischen mir und dem Verstorbenen zu erfahren.

Selbstverständlich möchte ich das Erbe antreten, insbesondere natürlich besonders gerne als Alleinerbe. Vielen Dank schon mal dafür, dass der Erbenermittler eine dementsprechende Erklärung aufzusetzen bereit ist.

Leider kann ich kein Formular im Anhang entdecken. Bitte schicken Sie mir ASAP ein neues Formular.

Hochachtungsvoll
Ihr Alexander Habicht

# Setting up a Rails project with Heroku, Eclipse and Domains

I always forget the single steps to create a new rails application that has a staging & production environment, can be deployed to Heroku and has the nameservers properly configured. So here’s the outline (so you and I never forget it):

1) Create Application

rails new $APP cd$APP

2) Create Eclipse ./.project file

<?xml version="1.0" encoding="UTF-8"?>
<projectDescription>
<name>$APP</name> <buildSpec> <buildCommand> <name>com.aptana.ide.core.unifiedBuilder</name> </buildCommand> </buildSpec> <natures> <nature>org.radrails.rails.core.railsnature</nature> <nature>com.aptana.ruby.core.rubynature</nature> </natures> </projectDescription> 3) Update Gemfile source 'https://rubygems.org' gem 'rails' gem 'jquery-rails' gem "jquery-ui-rails" gem "anjlab-bootstrap-rails", "~> 2.0.4.4", :require => "bootstrap-rails" group :assets do gem 'sass-rails' gem 'coffee-rails' gem 'uglifier' end group :development do gem 'sqlite3' end group :production, :staging do gem "pg" gem "therubyracer" end gem "devise", ">= 2.1.2" gem "cancan", ">= 1.6.8" gem "rolify", ">= 3.1.0" 4) Install Bundle bundle install --without production staging 5) Clean Up rm ./README.rdoc rm ./public/index.html rm ./public/favicon.ico rm ./doc/README_FOR_APP rm ./app/assets/images/rails.png 6) Create Root Controller rails generate controller root index 7) Update Routes root :to => 'root#index' 8) Create Git Repository & Init git init git remote add origin$URL

9) Overwrite ./.gitignore

.bundle
db/*.sqlite3*
log/*.log
*.log
/tmp/
doc/
*.swp
*~
.DS_Store

10) Commit

git add .
git commit -a -m "Initial Commit"
git push origin master

11) Create Heroku Endpoints & Push to Heroku

heroku create $APP-staging --remote staging heroku create$APP --remote production
git push staging master
git push production master

12) Prepare Heroku Domain

heroku domains:add --app $APP www.$APP.com

• Domain Forward to http://$APP.herokuapp.com • NameServer Settings: www.$APP.com CNAME \$APP.herokuapp.com


text:
Write the vector equations of the following lines and hence determine the distance between them:  (x - 1)/2 = (y - 2)/

### Question Asked by a Student from EXXAMM.com Team

Q 2652534434.     Write the vector equations of the following lines and hence determine the distance between them:
(x - 1)/2 = (y - 2)/3 = (z + 4)/6 : (x - 3)/4 = ( y - 3)/6 = (z + 5)/(12)`

CBSE-12th 2010

#### HINT

(Provided By a Student and Checked/Corrected by EXXAMM.com Team)

#### Access free resources including

• 100% free video lectures with detailed notes and examples
• Previous Year Papers
• Mock Tests
• Practices question categorized in topics and 4 levels with detailed solutions
• Syllabus & Pattern Analysis


text:
# Existence of perfect Morse functions on Fermat surfaces $x^n+y^n+z^n+w^n=0$

It seems that whether a simply connected 4 manifold needs 1-handles and 3-handles is still an open question, see Existence of Morse functions on simply connected manifolds.

I am wondering if it is true that every Fermat surface $$x^n+y^n+z^n+w^n=0$$ admits a handle decomposition with only, 0,2,4 handles.

Yes, this is true for any nonsingular hypersurface in $${\mathbb C}P^3$$. See Harer, On handlebody structures for hypersurfaces in C3 and CP3. Math. Ann. 238 (1978), no. 1, 51–58.