<p>In this thesis we present new results in two areas – cryptographic protocols and lattice problems. </p><p>• We present a new protocol for electronic cash which is designed to function on hardware with limited computing power. The scheme has provable security properties and low computational requirements, but it still gives a fair amount of privacy. Another feature of the system is that there is no master secret that could be used for counterfeiting money if stolen. </p><p>• We introduce the notion of hierarchical group signatures. This is a proper generalization of group signatures, which allows multiple group managers organized in a tree with the signers as leaves. For a signer that is a leaf of the subtree of a group manager, the group manager learns which of its children that (perhaps indirectly) manages the signer. We provide definitions for the new notion and construct a scheme that is provably secure given the existence of a family of trapdoor permutations. We also present a construction which is relatively practical, and prove its security in the random oracle model under the strong RSA assumption and the DDH assumption.</p><p>• We show a weakness in the specification for offline capable EMV payment cards. The weakness, which applies to cards without RSA capability, enables an attacker to duplicate a card and make transactions that cannot be tied to the original card.</p><p>• We give a method for approximating any n-dimensional lattice with a lattice Λ whose factor group Z<i>n</i>/Λ has <i>n</i> - 1 cycles of equal length with arbitrary precision. We also show that a direct consequence of this is that the Shortest Vector Problem and the Closest Vector Problem cannot be easier for this type of lattices than for general lattices.</p>

<p>An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. In the maximization version, Max CSP, each constraint has a weight and the objective is to find an assignment such that the weight of satisfied constraints is maximized. By specifying which types of constraints that are allowed we create subproblems to Max CSP. For example, an instance of Max kCSP only contains constraints that act over at most k different variables. Another problem is Max CSP(P), where P is a predicate, i.e., a Boolean function. In such an instance P is used to determine if a constraint is satisfied or not.</p><p>Both Max kCSP and Max CSP(P) are NP-hard to solve optimally for k ≥ 2 and predicates P that depend on at least two input values. Therefore, we consider efficient approximation algorithms for these two problems. A trivial algorithm is to assign all variables a random value. Somewhat surprisingly, Håstad showed that using this random assignment approach is essentially optimal for approximating Max CSP(P), for some predicates P. We call such predicates approximation resistant. Goemans and Williamson introduced an approximation method that relaxes problems into semidefinite programs. Using this method they show that for predicates P of arity two, it is possible to outperform a random assignment in approximating Max CSP(P). By extending this technique Zwick characterized all predicates of arity three as either approximation resistant or not.</p><p>In this thesis we consider predicates of arity larger than three. We extend the work of Håstad and the work of Samorodnitsky and Trevisan in order to show predicates to be approximation resistant. We also use semidefinite relaxation algorithms in order to show that predicates are not approximation resistant. In particular we show that predicates with few non-accepting inputs are approximation resistant and that predicates with few accepting inputs are not approximation resistant. We study predicates of arity four more closely and characterize 354 out of 400 predicate types.</p><p>Max kCSP is 2^-k-approximated by a random assignment and previously no algorithms were known to outperform such an algorithm with more than a small constant factor. In this thesis a probabilistic </p><p>Ω (2^{k+log k-log log k})-approximation for Max kCSP is presented.</p>

<p>Dissertation in Computer Science to be publicly examined in Häggsalen, Ångströmlaboratoriet, Uppsala University, on Friday, November 1, 2002 at 1:00 pm for the degree of doctor of philosophy. The examination will be conducted in English. </p><p>This thesis proposes and experimentally evaluates techniques for efficient implementation of languages designed for high availability concurrent systems. This experimental evaluation has been done while developing the High Performance Erlang (HiPE) system, a native code compiler for SPARC and x86. The two main goals of the HiPE system are to provide efficient execution of Erlang programs, and to provide a research vehicle for evaluating implementation techniques for concurrent functional programming languages.</p><p>The focus of the thesis is the evaluation of two techniques that enable inter-process optimization through dynamic compilation. The first technique is a fast register allocator called linear scan, and the second is a memory architecture where processes share memory.</p><p>The main contributions of the thesis are:</p><p>An evaluation of linear scan register allocation in a different language setting. In addition the performance of linear scan on the register poor x86 architecture is evaluated for the first time.</p><p>A description of three different heap architectures (private heaps, shared heap, and a hybrid of the two), with a systematic investigation of implementation aspects and an extensive discussion on the associated performance trade-offs of the heap architectures. The description is accompanied by an experimental evaluation of the private vs. the shared heap setting.</p><p>A novel approach to optimizing a concurrent program, by merging code from a sender with code from a receiver, is presented together with other methods for reducing the overhead of context switching.</p><p>A description of the implementation aspects of a complete and robust native code Erlang system, which makes it possible to test compiler optimizations on real world programs.</p>

Recognizing objects through vision is an important part of our lives: we recognize people when we talk to them, we recognize our cup on the breakfast table, our car in a parking lot, and so on. While this task is performed with great accuracy and apparently little effort by humans, it is still unclear how this performance is achieved. Creating computer methods for automatic object recognition gives rise to challenging theoretical problems such as how to model the visual appearance of the objects or categories we want to recognize, so that the resulting algorithm will perform robustly in realistic scenarios; to this end, how to use effectively multiple cues (such as shape, color, textural properties and many others), so that the algorithm uses uses the best subset of cues in the most effective manner; how to use specific features and/or specific strategies for different classes. The present work is devoted to the above issues. We propose to model the visual appearance of objects and visual categories via probability density functions. The model is developed on the basis of concepts and results obtained in three different research areas: computer vision, machine learning and statistical physics of spin glasses. It consists of a fully connected Markov random field with energy function derived from results of statistical physics of spin glasses. Markov random fields and spin glass energy functions are combined together via nonlinear kernel functions; we call the model Spin Glass-Markov Random Fields. Full connectivity enables to take into account the global appearance of the object, and its specific local characteristics at the same time, resulting in robustness to noise, occlusions and cluttered background. Because of properties of some classes of spin glasslike energy functions, our model allows to use easily and effectively multiple cues, and to employ class specific strategies. We show with theoretical analysis and experiments that this new model is competitive with state-of-the-art algorithms for object recognition.

Natural language processing (NLP) means the computer-aided processing of language produced by a human. But human language is inherently irregular and the most reliable results are obtained when a human is involved in at least some part of the processing. However, manual workis time-consuming and expensive. This thesis focuses on what can be accomplished in NLP when manual workis kept to a minimum. We describe the construction of two tools that greatly simplify the implementation of automatic evaluation. They are used to implement several supervised, semi-supervised and unsupervised evaluations by introducing artificial spelling errors. We also describe the design of a rule-based shallow parser for Swedish called GTA and a detection algorithm for context-sensitive spelling errors based on semi-supervised learning, called ProbCheck. In the second part of the thesis, we first implement a supervised evaluation scheme that uses an error-free treebankto determine the robustness of a parser when faced with noisy input such as spelling errors. We evaluate the GTA parser and determine the robustness of the individual components of the parser as well as the robustness for different phrase types. Second, we create an unsupervised evaluation procedure for parser robustness. The procedure allows us to evaluate the robustness of parsers using different parser formalisms on the same text and compare their performance. Five parsers and one tagger are evaluated. For four of these, we have access to annotated material and can verify the estimations given by the unsupervised evaluation procedure. The results turned out to be very accurate with few exceptions and thus, we can reliably establish the robustness of an NLP system without any need of manual work. Third, we implement an unsupervised evaluation scheme for spell checkers. Using this, we perform a very detailed analysis of three spell checkers for Swedish. Last, we evaluate the ProbCheck algorithm. Two methods are included for comparison: a full parser and a method using tagger transition probabilities. The algorithm obtains results superior to the comparison methods. The algorithm is also evaluated on authentic data in combination with a grammar and spell checker. / QC 20100901

<p>This thesis concerns stability of plane Couette flow in three space dimensions for the incompressible Navier-Stokes equations. We present new results for the resolvent corresponding to this flow. Previously, analytical bounds of the resolvent have been derived in parts of the unstable half-plane. In the remaining part, only bounds based on numerical computations in an infinite parameter domain are available. Due to the need for truncation of this infinite parameter domain, these results are mathematically insufficient.</p><p>We obtain a new analytical bound of the resolvent at <i>s </i>= 0 in all but a compact subset of the parameter domain. This is done by deriving approximate solutions of the Orr-Sommerfeldt equation and bounding the errors made by the approximations. In the remaining compact set, we use standard numerical techniques to obtain a bound. Hence, this part of the proof is not rigorous in the mathematical sense.</p><p>In the thesis, we present a way of making also the numerical part of the proof rigorous. By using analytical techniques, we reduce the remaining compact subset of the parameter domain to a finite set of parameter values. In this set, we need to compute bounds of the solution of a boundary value problem. By using a validated numerical method, such bounds can be obtained. In the last part of the thesis, we investigate a validated numerical method for enclosing the solutions of boundary value problems.</p>

<p>Recognizing objects through vision is an important part of our lives: we recognize people when we talk to them, we recognize our cup on the breakfast table, our car in a parking lot, and so on. While this task is performed with great accuracy and apparently little effort by humans, it is still unclear how this performance is achieved. Creating computer methods for automatic object recognition gives rise to challenging theoretical problems such as how to model the visual appearance of the objects or categories we want to recognize, so that the resulting algorithm will perform robustly in realistic scenarios; to this end, how to use effectively multiple cues (such as shape, color, textural properties and many others), so that the algorithm uses uses the best subset of cues in the most effective manner; how to use specific features and/or specific strategies for different classes. </p><p>The present work is devoted to the above issues. We propose to model the visual appearance of objects and visual categories via probability density functions. The model is developed on the basis of concepts and results obtained in three different research areas: computer vision, machine learning and statistical physics of spin glasses. It consists of a fully connected Markov random field with energy function derived from results of statistical physics of spin glasses. Markov random fields and spin glass energy functions are combined together via nonlinear kernel functions; we call the model Spin Glass-Markov Random Fields. Full connectivity enables to take into account the global appearance of the object, and its specific local characteristics at the same time, resulting in robustness to noise, occlusions and cluttered background. Because of properties of some classes of spin glasslike energy functions, our model allows to use easily and effectively multiple cues, and to employ class specific strategies. We show with theoretical analysis and experiments that this new model is competitive with state-of-the-art algorithms for object recognition.</p>

<p>Elever på gymnasiet har ibland problem att förstå abstrakta fysikaliska fenomen. Visuella hjälpmedel skulle underlätta förståelsen. Det finns också ett behov av interaktiva webbplatser eller program som testar elevernas kunskap. Jag har gjort en webbplats <belfrage.info.se> som en utvald testgrupp, representativ för målgruppen, fått testa. Gruppen har också fått föreslå förbättringar. Syftet med examensarbetet har varit att ta reda på vad intresserade gymnasieelever tycker är svårt med fysik. Dessutom har en plattform skapats där dessa elever kan tillgodogöra sig kunskaper och därefter testa dem interaktivt.</p> / <p>High school students often have problems understanding abstract physical phenomena. Visual aids could facilitate their learning process and help them understand. There also appears to be a need for interactive websites, or programs, that tests the students' knowledge. I have developed a website, <belfrage.info.se>. It is a platform where student can acquire knowledge and test it interactively. A representative segment from the target group has been given the opportunity to evaluate it. The group has given feedback in the form of opinions and suggested improvements. The purpose of this paper was to find out what interested students find difficult in science (physics).</p>

<p>E-postmeddelanden är något som de flesta av oss använder. Hur vi använder oss av e-post skiljer sig från person till person. Vi har identifierat flera olika användningssätt, till exempel att skicka en text, bifoga filer eller skicka en rolig bild. I den här rapporten studeras ett par olika sätt att med hjälp av komprimering av hela e-postmeddelanden minska datavolymen och därmed den tid det tar transportera meddelanden. Caslon Analythics spår att det 2005 kommer att skickas 236 miljarder e-postmeddelanden. En minskning av meddelandens storlek kommer ha en positiv effekt på belastningen av nätverk. Ett plugin som används av Qualcomm Eudora har skapats för att visa se vilket resultat som kan uppnås. Det använder sig av ett komprimerings-biblioteket vid namn zlib och Eudoras API för plugins. Om man utgår från okomprimerade texter och/eller filer så kan man med hjälp av detta plugin och diverse tester konstatera att man kan minska den plats som ett e-postmeddelande upptar på lagringsutrymmet med upp till 70 procent. Stor vinst kan alltså göras i både tid och plats.</p> / <p>E-mails are something that most of us use. How we use it is different from one person to another. We have identified several different ways of usage, for example sending text, attach a file or send a funny picture. In this report different ways of using compression to decrease the volume of an e-mail and also the time it takes to deliver it is being studied. Caslon Analythics predict that 2005 around 236 billion e-mails will be sent. A reduction of messages sizes will have a positive effect on the network load. A plugin that uses Qualcomm Eudora have been created to show what can be done to reduce size and time. It uses a compression library called zlib and Eudora API for plugins. With the plugin and some tests it is shown that it can decrease the amount of storage needed by up to 70 percent when text and/or uncompressed files are attached. Large gain can therefore be made in both time and space.</p>

An instance of a Boolean constraint satisfaction problem, CSP, consists of a set of constraints acting over a set of Boolean variables. The objective is to find an assignment to the variables that satisfies all the constraints. In the maximization version, Max CSP, each constraint has a weight and the objective is to find an assignment such that the weight of satisfied constraints is maximized. By specifying which types of constraints that are allowed we create subproblems to Max CSP. For example, an instance of Max kCSP only contains constraints that act over at most k different variables. Another problem is Max CSP(P), where P is a predicate, i.e., a Boolean function. In such an instance P is used to determine if a constraint is satisfied or not. Both Max kCSP and Max CSP(P) are NP-hard to solve optimally for k ≥ 2 and predicates P that depend on at least two input values. Therefore, we consider efficient approximation algorithms for these two problems. A trivial algorithm is to assign all variables a random value. Somewhat surprisingly, Håstad showed that using this random assignment approach is essentially optimal for approximating Max CSP(P), for some predicates P. We call such predicates approximation resistant. Goemans and Williamson introduced an approximation method that relaxes problems into semidefinite programs. Using this method they show that for predicates P of arity two, it is possible to outperform a random assignment in approximating Max CSP(P). By extending this technique Zwick characterized all predicates of arity three as either approximation resistant or not. In this thesis we consider predicates of arity larger than three. We extend the work of Håstad and the work of Samorodnitsky and Trevisan in order to show predicates to be approximation resistant. We also use semidefinite relaxation algorithms in order to show that predicates are not approximation resistant. In particular we show that predicates with few non-accepting inputs are approximation resistant and that predicates with few accepting inputs are not approximation resistant. We study predicates of arity four more closely and characterize 354 out of 400 predicate types. Max kCSP is 2-k-approximated by a random assignment and previously no algorithms were known to outperform such an algorithm with more than a small constant factor. In this thesis a probabilistic Ω (2k+log k-log log k)-approximation for Max kCSP is presented. / QC 20101020