Semidefinite programming and combinatorial optimization.
Semidefinite Programming Based Algorithms for the Sparsest Cut Problem
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...
Semidefinite Programming Based Algorithms for the Sparsest Cut Problem
In this paper we analyze a known relaxation for the Sparsest Cut problem based on positive semidefinite constraints, and we present a branch and bound algorithm and heuristics based on this relaxation. The relaxed formulation and the algorithms were tested on small and moderate sized instances. It leads to values very close to the optimum solution values. The exact algorithm could obtain solutions for small and moderate sized instances, and the best heuristics obtained optimum or near optimum...
Semigroups defined by automaton extension mapping
We study semigroups generated by the restrictions of automaton extension (see, e.g., [3]) and give a characterization of automaton extensions that generate finite semigroups.
Semisimplicity of the algebra associated to a biprefix code.
Semi-topological classification of line patterns in the plane
Sender-equivocable encryption schemes secure against chosen-ciphertext attacks revisited
Fehr et al. (2010) proposed the first sender-equivocable encryption scheme secure against chosen-ciphertext attacks (NCCCA) and proved that NC-CCA security implies security against selective opening chosen-ciphertext attacks (SO-CCA). The NC-CCA security proof of the scheme relies on security against substitution attacks of a new primitive, the “crossauthentication code”. However, the security of the cross-authentication code cannot be guaranteed when all the keys used in the code are exposed. Our...
Separating complexity classes related to certain input oblivious logarithmic space-bounded Turing machines
Separating from co-, and for oblivious Turing machines of linear access
Separating Two Simple Polygons by a Sequence of Translations.
Separating words with machines and groups
Sequences of low arithmetical complexity
Arithmetical complexity of a sequence is the number of words of length n that can be extracted from it according to arithmetic progressions. We study uniformly recurrent words of low arithmetical complexity and describe the family of such words having lowest complexity.
Sequent Calculus, Derivability, Provability. Gödel's Completeness Theorem
Fifth of a series of articles laying down the bases for classical first order model theory. This paper presents multiple themes: first it introduces sequents, rules and sets of rules for a first order language L as L-dependent types. Then defines derivability and provability according to a set of rules, and gives several technical lemmas binding all those concepts. Following that, it introduces a fixed set D of derivation rules, and proceeds to convert them to Mizar functorial cluster registrations...
Sequential machines with several input and output tapes
Sequential mappings of -languages
Sequential monotonicity for restarting automata
As already 2-monotone R-automata accept NP-complete languages, we introduce a restricted variant of j-monotonicity for restarting automata, called sequential j-monotonicity. For restarting automata without auxiliary symbols, this restricted variant still yields infinite hierarchies. However, for restarting automata with auxiliary symbols, all degrees of sequential monotonicity collapse to the first level, implying that RLWW-automata that are sequentially monotone of degree j for any j ≥ 1 only...
Seriation with applications in philology
Séries algébriques solutions d'équations linéaires avec opérateurs
Séries formelles
La classification chomskienne des langages formels conduit à l'étude d'objets mathématiques nouveaux: les séries rationnelles et algébriques en variables non commutatives.
Séries formelles rationnelles et reconnaissables