In this work, we study two problems: first is one of the central problem in learning theory of learning sparse parities and the other k-Vector-SUM is an extension of the not oriousk-SUM problem. We first consider the problem of learning k-parities in the on-line mistake-bound model: given a hidden vector ∈ {0,1}nwith|x|=kand a sequence of “questions” a ,a ,12··· ∈{0,1}n, where the algorithm must reply to each question with〈a ,xi〉(mod 2), what is the best trade off between the number of mistakes made by the algorithm and its time complexity? We improve the previous best result of Buhrman et. al. By an exp (k) factor in the timecomplexity. Next, we consider the problem of learning k-parities in the presence of classification noise of rate η∈(0,12). A polynomial time algorithm for this problem (whenη >0 andk=ω(1))is a longstanding challenge in learning theory. Grigorescu et al. Showed an algorithm running in time(no/2)1+4η2+o(1). Note that this algorithm inherently requires time(nk/2)even when the noise rateη is polynomially small. We observe that for sufficiently small noise rate, it ispossible to break the(nk/2)barrier. In particular, if for some function f(n) =ω(logn) andα∈[12,1),k=n/f(n) andη=o(f(n)−α/logn), then there is an algorithm for the problem with running time poly(n)·( )nk1−α·e−k/4.01.Moving on to the k-Vector-SUM problem, where given n vectors〈v ,v ,...,v12n〉over the vector space Fdq, a target vector tand an integer k>1, determine whether there exists k vectors whose sum list, where sum is over the field Fq. We show a parameterized reduction fromk-Clique problem to k-Vector-SUM problem, thus showing the hardness of k-Vector-SUM. In parameterized complexity theory, our reduction shows that the k-Vector-SUM problem is hard for the class W[1], although, Downey and Fellows have shown the W[1]-hardness result for k-Vector-SUM using other techniques. In our next attempt, we try to show connections between k-Vector-SUM and k-LPN. First we prove that, a variant of k-Vector-SUM problem, called k-Noisy-SUM is at least as hard as the k-LPN problem. This implies that any improvements ink-Noisy-SUM would result into improved algorithms fork-LPN. In our next result, we show a reverse reduction from k-Vector-SUM to k-LPN with high noise rate. Providing lower bounds fork-LPN problem is an open challenge and many algorithms in cryptography have been developed assuming its1 2hardness. Our reduction shows that k-LPN with noise rate η=12−12·nk·2−n(k−1k)cannot be solved in time no(k)assuming Exponential Time Hypothesis and, thus providing lower bound for a weaker version of k-LPN

Nested by linear cointegration first provided in Granger (1981), the definition of nonlinear cointegration is presented in this paper. Sequentially, a nonlinear cointegrated economic system is introduced. What we mainly study is testing no nonlinear cointegration against nonlinear cointegration by residual-based test, which is ready for detecting stochastic trend in nonlinear autoregression models. We construct cointegrating regression along with smooth transition components from smooth transition autoregression model. Some properties are analyzed and discussed during the estimation procedure for cointegrating regression, including description of transition variable. Autoregression of order one is considered as the model of estimated residuals for residual-based test, from which the teststatistic is obtained. Critical values and asymptotic distribution of the test statistic that we request for different cointegrating regressions with different sample sizes are derived based on Monte Carlo simulation. The proposed theoretical methods and models are illustrated by an empirical example, comparing the results with linear cointegration application in Hamilton (1994). It is concluded that there exists nonlinear cointegration in our system in the final results.

Made available in DSpace on 2010-04-20T21:00:43Z (GMT). No. of bitstreams: 3 johnliuturma2004.pdf.jpg: 12342 bytes, checksum: 2bea1c4035c89c2307b4cb760d9f566a (MD5) johnliuturma2004.pdf: 369564 bytes, checksum: 7c620a827a2cc6f2c516bed27c870382 (MD5) johnliuturma2004.pdf.txt: 49576 bytes, checksum: b159d560c6000e2d4736afaacdc682b6 (MD5) Previous issue date: 2007-02-05T00:00:00Z / This thesis examines the relationship between interest rates and exchange rate movements using the Uncovered Interest Rate Parity (UIP). Assuming rational expectations, we evaluated Brazilian data from Plano Real (July 1986) until August 2006. We found evidences that lead to reject UIP in the long run. Furthermore, we investigated the presence of UIP without the assumption of rational expectations. We used market surveys of future exchange, published at the Boletim Focus. We also found evidences that give no support to UIP hypothesis. / Esta dissertação procura examinar a relação entre taxas de juros e os movimentos da taxa de câmbio, a partir da paridade descoberta de juros (PDJ). Foi utilizado o procedimento pressupondo expectativas racionais e foi testada a validade da PDJ com dados da economia brasileira desde o Plano Real (julho de 1994) até agosto de 2006. Encontramos evidências que levam à rejeição da PDJ no longo prazo. Além disso, foi examinada a validade da PDJ sem a necessidade de utilizar a hipótese de expectativas racionais, foram utilizadas as previsões de câmbio dos analistas financeiros, publicadas no Boletim Focus de novembro de 2001 a novembro de 2006. Também encontramos evidências que levam à rejeição da PDJ no Brasil.

In this thesis, we show results for some well-studied problems from learning theory and combinatorial optimization. Learning Parities under the Uniform Distribution: We study the learnability of parities in the agnostic learning framework of Haussler and Kearns et al. We show that under the uniform distribution, agnostically learning parities reduces to learning parities with random classification noise, commonly referred to as the noisy parity problem. Together with the parity learning algorithm of Blum et al, this gives the first nontrivial algorithm for agnostic learning of parities. We use similar techniques to reduce learning of two other fundamental concept classes under the uniform distribution to learning of noisy parities. Namely, we show that learning of DNF expressions reduces to learning noisy parities of just logarithmic number of variables and learning of k-juntas reduces to learning noisy parities of k variables. Agnostic Learning of Halfspaces: We give an essentially optimal hardness result for agnostic learning of halfspaces over rationals. We show that for any constant ε finding a halfspace that agrees with an unknown function on 1/2+ε fraction of examples is NP-hard even when there exists a halfspace that agrees with the unknown function on 1-ε fraction of examples. This significantly improves on a number of previous hardness results for this problem. We extend the result to ε = 2[superscript-Ω(sqrt{log n})] assuming NP is not contained in DTIME(2[superscript(log n)O(1)]). Majorities of Halfspaces: We show that majorities of halfspaces are hard to PAC-learn using any representation, based on the cryptographic assumption underlying the Ajtai-Dwork cryptosystem. This also implies a hardness result for learning halfspaces with a high rate of adversarial noise even if the learning algorithm can output any efficiently computable hypothesis. Max-Clique, Chromatic Number and Min-3Lin-Deletion: We prove an improved hardness of approximation result for two problems, namely, the problem of finding the size of the largest clique in a graph (also referred to as the Max-Clique problem) and the problem of finding the chromatic number of a graph. We show that for any constant γ > 0, there is no polynomial time algorithm that approximates these problems within factor n/2[superscript(log n)3/4+γ] in an n vertex graph, assuming NP is not contained in BPTIME(2[superscript(log n)O(1)]). This improves the hardness factor of n/2[superscript (log n)1-γ'] for some small (unspecified) constant γ' > 0 shown by Khot. Our main idea is to show an improved hardness result for the Min-3Lin-Deletion problem. An instance of Min-3Lin-Deletion is a system of linear equations modulo 2, where each equation is over three variables. The objective is to find the minimum number of equations that need to be deleted so that the remaining system of equations has a satisfying assignment. We show a hardness factor of 2[superscript sqrt{log n}] for this problem, improving upon the hardness factor of (log n)[superscriptβ] shown by Hastad, for some small (unspecified) constant β > 0. The hardness results for Max-Clique and chromatic number are then obtained using the reduction from Min-3Lin-Deletion as given by Khot. Monotone Multilinear Boolean Circuits for Bipartite Perfect Matching: A monotone Boolean circuit is said to be multilinear if for any AND gate in the circuit, the minimal representation of the two input functions to the gate do not have any variable in common. We show that monotone multilinear Boolean circuits for computing bipartite perfect matching require exponential size. In fact we prove a stronger result by characterizing the structure of the smallest monotone multilinear Boolean circuits for the problem.