3 results
Filters
Settings
Now showing1 - 3 of 3
- Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Smooth approximations : an algebraic approach to CSPs over finitely bounded homogeneous structuresWe introduce the novel machinery of smooth approximations to provide a systematic algebraic approach to the complexity of CSPs over finitely bounded homogeneous structures. We apply smooth approximations to confirm the CSP dichotomy conjecture for first-order reducts of the random tournament and to give new short proofs of the conjecture for various homogeneous graphs including the random graph (STOC'11, ICALP'16, JACM 2015, SICOMP 2019), and for expansions of the order of the rationals (STOC'08, JACM 2009). Apart from obtaining these dichotomy results, we show how our new proof technique allows one to unify and significantly simplify the previous results from the literature. For all but the last structure, we moreover characterize for the first time those CSPs that are solvable by local consistency methods, again using the same machinery.Publicationtype: Journal Article14 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Discrete temporal constraint satisfaction problems(2018-02); ; A discrete temporal constraint satisfaction problem is a constraint satisfaction problem (CSP) over the set of integers whose constraint language consists of relations that are first-order definable over the order of the integers. We prove that every discrete temporal CSP is in P or NP-complete, unless it can be formulated as a finite domain CSP, in which case the computational complexity is not known in general.Publicationtype: Conference Paper24 - Some of the metrics are blocked by yourconsent settings
Item type:Publication, Access status: without files , Arithmetic cryptographyWe study the possibility of computing cryptographic primitives in a fully black-box arithmetic model over a finite field F. In this model, the input to a cryptographic primitive (e.g., encryption scheme) is given as a sequence of field elements, the honest parties are implemented by arithmetic circuits that make only a black-box use of the underlying field, and the adversary has a full (non-black-box) access to the field. This model captures many standard information-theoretic constructions. We prove several positive and negative results in this model for various cryptographic tasks. On the positive side, we show that, under coding-related intractability assumptions, computational primitives like commitment schemes, public-key encryption, oblivious transfer, and general secure two-party computation can be implemented in this model. On the negative side, we prove that garbled circuits, additively homomorphic encryption, and secure computation with low online complexity cannot be achieved in this model. Our results reveal a qualitative difference between the standard Boolean model and the arithmetic model, and explain, in retrospect, some of the limitations of previous constructions.Publicationtype: Journal Article81