TY - JOUR AB - We have selected problems that may not yet be well known, but have the potential to push the research in interesting directions. In particular, we state problems that do not require specific knowledge outside the standard circle of ideas in discrete geometry. Despite the relatively simple statements, these problems are related to current research and their solutions are likely to require new ideas and approaches. We have chosen problems from different fields to make this short paper attractive to a wide range of specialists. AU - Herbert Edelsbrunner AU - Ivanov, Alexander AU - Karasev, Roman ID - 2911 JF - Automatic Control and Computer Sciences TI - Open problems in discrete and computational geometry VL - in print ER - TY - CONF AB - In this paper we investigate k-submodular functions. This natural family of discrete functions includes submodular and bisubmodular functions as the special cases k = 1 and k = 2 respectively. In particular we generalize the known Min-Max-Theorem for submodular and bisubmodular functions. This theorem asserts that the minimum of the (bi)submodular function can be found by solving a maximization problem over a (bi)submodular polyhedron. We define a k-submodular polyhedron, prove a Min-Max-Theorem for k-submodular functions, and give a greedy algorithm to construct the vertices of the polyhedron. AU - Huber, Anna AU - Kolmogorov, Vladimir ID - 2930 TI - Towards minimizing k-submodular functions VL - 7422 ER - TY - GEN AB - This paper addresses the problem of approximate MAP-MRF inference in general graphical models. Following [36], we consider a family of linear programming relaxations of the problem where each relaxation is specified by a set of nested pairs of factors for which the marginalization constraint needs to be enforced. We develop a generalization of the TRW-S algorithm [9] for this problem, where we use a decomposition into junction chains, monotonic w.r.t. some ordering on the nodes. This generalizes the monotonic chains in [9] in a natural way. We also show how to deal with nested factors in an efficient way. Experiments show an improvement over min-sum diffusion, MPLP and subgradient ascent algorithms on a number of computer vision and natural language processing problems. AU - Kolmogorov, Vladimir AU - Schoenemann, Thomas ID - 2928 T2 - arXiv TI - Generalized sequential tree-reweighted message passing ER - TY - GEN AU - Vladimir Kolmogorov ID - 2929 TI - The power of linear programming for valued CSPs: a constructive characterization ER - TY - CONF AB - Developers building cryptography into security-sensitive applications face a daunting task. Not only must they understand the security guarantees delivered by the constructions they choose, they must also implement and combine them correctly and efficiently. Cryptographic compilers free developers from this task by turning high-level specifications of security goals into efficient implementations. Yet, trusting such tools is hard as they rely on complex mathematical machinery and claim security properties that are subtle and difficult to verify. In this paper we present ZKCrypt, an optimizing cryptographic compiler achieving an unprecedented level of assurance without sacrificing practicality for a comprehensive class of cryptographic protocols, known as Zero-Knowledge Proofs of Knowledge. The pipeline of ZKCrypt integrates purpose-built verified compilers and verifying compilers producing formal proofs in the CertiCrypt framework. By combining the guarantees delivered by each stage, ZKCrypt provides assurance that the output implementation securely realizes the abstract proof goal given as input. We report on the main characteristics of ZKCrypt, highlight new definitions and concepts at its foundations, and illustrate its applicability through a representative example of an anonymous credential system. AU - Almeida, José AU - Barbosa, Manuel AU - Bangerter, Endre AU - Barthe, Gilles AU - Krenn, Stephan AU - Béguelin, Santiago ID - 2937 T2 - Proceedings of the 2012 ACM conference on Computer and communications security TI - Full proof cryptography: Verifiable compilation of efficient zero-knowledge protocols ER -