Sökning: "Johan Håstad"
Visar resultat 1 - 5 av 13 avhandlingar innehållade orden Johan Håstad.
1. Beating a Random Assignment : Approximating Constraint Satisfaction Problems
Sammanfattning : 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. LÄS MER
2. On Long Proofs of Simple Truths
Sammanfattning : Propositional proof complexity is the study of certificates of infeasibility. In this thesis we consider several proof systems with limited deductive ability and unconditionally show that they require long refutations of the feasibility of certain Boolean formulas. LÄS MER
3. Conditional Inapproximability and Limited Independence
Sammanfattning : Understanding the theoretical limitations of efficient computation is one of the most fundamental open problems of modern mathematics. This thesis studies the approximability of intractable optimization problems. In particular, we study so-called Max CSP problems. LÄS MER
4. Hardness of Constraint Satisfaction and Hypergraph Coloring : Constructions of Probabilistically Checkable Proofs with Perfect Completeness
Sammanfattning : A Probabilistically Checkable Proof (PCP) of a mathematical statement is a proof written in a special manner that allows for efficient probabilistic verification. The celebrated PCP Theorem states that for every family of statements in NP, there is a probabilistic verification procedure that checks the validity of a PCP proof by reading only 3 bits from it. LÄS MER
5. Aspects of Secure and Efficient Streaming and Collaboration
Sammanfattning : Research within the area of cryptography constitutes the core of this the- sis. In addition to cryptography, we also present results in peer-assisted streaming and web security. We present results on two specific cryptographic problems: broadcast encryption and secure multi-party computation. LÄS MER
