Accepted papers
From CSR 2013
(Difference between revisions)
(Created page with "== CSR 2013 Accepted Papers == # Barnaby Martin and Stefan Dantchev. Parameterized Resolution with bounded conjunction # Nicolas Boria, Cécile Murat and Vangelis Paschos. The...") |
|||
(3 intermediate revisions by one user not shown) | |||
Line 1: | Line 1: | ||
− | == CSR 2013 Accepted Papers == | + | == CSR 2013 Accepted Papers (in random order) == |
− | # Barnaby Martin and Stefan Dantchev. Parameterized | + | # Barnaby Martin and Stefan Dantchev. ''Parameterized resolution with bounded conjunction'' |
− | # Nicolas Boria, Cécile Murat and Vangelis Paschos. The | + | # Nicolas Boria, Cécile Murat and Vangelis Paschos. ''The probabilistic dominating set problem'' |
− | # Marek Tesař and Jiri Fiala. Dichotomy of the H- | + | # Marek Tesař and Jiri Fiala. ''Dichotomy of the H-quasi-cover problem'' |
− | # Mikhail Vyalyi. Universality of regular realizability | + | # Mikhail Vyalyi. ''Universality of regular realizability problems'' |
− | # Anton Makhlin. On the | + | # Anton Makhlin. ''On the encoding invariance of polynomial time computable distribution ensembles'' |
− | # David Janin. Overlapping tile automata | + | # David Janin. ''Overlapping tile automata'' |
− | # Vladimir | + | # Vladimir Nikishkin. ''Amortized communication complexity of an equality predicate'' |
− | # Viliam Geffert, Zuzana Bednarova, Carlo Mereghetti and Beatrice Palano. Boolean | + | # Viliam Geffert, Zuzana Bednarova, Carlo Mereghetti and Beatrice Palano. ''Boolean language operations on nondeterministic automata with a pushdown of constant height'' |
− | # Andreas Fröhlich, Gergely Kovásznai and Armin Biere. More on the | + | # Andreas Fröhlich, Gergely Kovásznai and Armin Biere. ''More on the complexity of quantifier-free fixed-size bit-vector logics with binary encoding'' |
− | # Amaldev Manuel, Anca Muscholl and Gabriele Puppis. Walking on | + | # Amaldev Manuel, Anca Muscholl and Gabriele Puppis. ''Walking on data words'' |
− | # | + | # Pavel Martyugin. ''Careful synchronization of partial automata with restricted alphabets'' |
− | # Timofey Stepanov. Random selection in few rounds | + | # Timofey Stepanov. ''Random selection in few rounds'' |
− | # Kshitij Bansal and Stéphane Demri. Model- | + | # Kshitij Bansal and Stéphane Demri. ''Model-checking bounded multi-pushdown systems'' |
− | # Klaus Jansen and Stefan Kraft. An | + | # Klaus Jansen and Stefan Kraft. ''An improved knapsack solver for column generation'' |
− | # Dmitry Itsykson and Vsevolod Oparin. Graph expansion, Tseitin formulas and resolution proofs for CSP | + | # Dmitry Itsykson and Vsevolod Oparin. ''Graph expansion, Tseitin formulas and resolution proofs for CSP'' |
− | # Nikolay Vereshchagin. An improving on Gutfreund, Shaltiel, and Ta-Shma's paper | + | # Nikolay Vereshchagin. ''An improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances"'' |
− | # Alexey Sorokin. Lower and upper bounds for the length of joins in Lambek calculus | + | # Alexey Sorokin. ''Lower and upper bounds for the length of joins in Lambek calculus'' |
− | # Romeo Rizzi and Stéphane Vialette. On recognizing words that are squares for the shuffle product | + | # Romeo Rizzi and Stéphane Vialette. ''On recognizing words that are squares for the shuffle product'' |
− | # Barnaby Martin and Florent Madelaine. QCSP on partially reflexive cycles - the wavy line of tractability | + | # Barnaby Martin and Florent Madelaine. ''QCSP on partially reflexive cycles - the wavy line of tractability'' |
− | # Jozef Jirasek and Galina Jiraskova. Cyclic | + | # Jozef Jirasek and Galina Jiraskova. Cyclic shift on prefix-free languages |
− | # Abuzer Yakaryilmaz. One-counter verifiers for decidable languages | + | # Abuzer Yakaryilmaz. ''One-counter verifiers for decidable languages'' |
− | # Armin Weiss and Volker Diekert. QuickHeapsort: Modifications and improved analysis | + | # Armin Weiss and Volker Diekert. ''QuickHeapsort: Modifications and improved analysis'' |
− | # Manfred Droste and Vitaly Perevoshchikov. Multi-weighted | + | # Manfred Droste and Vitaly Perevoshchikov. ''Multi-weighted automata and MSO logic'' |
− | # Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein. Information lower bounds via self-reducibility | + | # Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein. ''Information lower bounds via self-reducibility'' |
− | # Sergey Avgustinovich and Svetlana Puzynina. Weak abelian periodicity of infinite words | + | # Sergey Avgustinovich and Svetlana Puzynina. ''Weak abelian periodicity of infinite words'' |
− | # Sven De Felice and Cyril Nicaud. Random | + | # Sven De Felice and Cyril Nicaud. ''Random generation of deterministic acyclic automata using the recursive method'' |
− | # Abuzer Yakaryilmaz. Quantum alternation | + | # Abuzer Yakaryilmaz. ''Quantum alternation'' |
− | # Luke Friedman and Yixin Xu. Exponential | + | # Luke Friedman and Yixin Xu. ''Exponential lower bounds for refuting random formulas using ordered binary decision diagrams'' |
− | # Pawel Gawrychowski. Alphabetic minimax trees in linear time | + | # Pawel Gawrychowski. ''Alphabetic minimax trees in linear time'' |
Latest revision as of 19:23, 16 February 2013
[edit] CSR 2013 Accepted Papers (in random order)
- Barnaby Martin and Stefan Dantchev. Parameterized resolution with bounded conjunction
- Nicolas Boria, Cécile Murat and Vangelis Paschos. The probabilistic dominating set problem
- Marek Tesař and Jiri Fiala. Dichotomy of the H-quasi-cover problem
- Mikhail Vyalyi. Universality of regular realizability problems
- Anton Makhlin. On the encoding invariance of polynomial time computable distribution ensembles
- David Janin. Overlapping tile automata
- Vladimir Nikishkin. Amortized communication complexity of an equality predicate
- Viliam Geffert, Zuzana Bednarova, Carlo Mereghetti and Beatrice Palano. Boolean language operations on nondeterministic automata with a pushdown of constant height
- Andreas Fröhlich, Gergely Kovásznai and Armin Biere. More on the complexity of quantifier-free fixed-size bit-vector logics with binary encoding
- Amaldev Manuel, Anca Muscholl and Gabriele Puppis. Walking on data words
- Pavel Martyugin. Careful synchronization of partial automata with restricted alphabets
- Timofey Stepanov. Random selection in few rounds
- Kshitij Bansal and Stéphane Demri. Model-checking bounded multi-pushdown systems
- Klaus Jansen and Stefan Kraft. An improved knapsack solver for column generation
- Dmitry Itsykson and Vsevolod Oparin. Graph expansion, Tseitin formulas and resolution proofs for CSP
- Nikolay Vereshchagin. An improving on Gutfreund, Shaltiel, and Ta-Shma's paper "If NP Languages are Hard on the Worst-Case, Then it is Easy to Find Their Hard Instances"
- Alexey Sorokin. Lower and upper bounds for the length of joins in Lambek calculus
- Romeo Rizzi and Stéphane Vialette. On recognizing words that are squares for the shuffle product
- Barnaby Martin and Florent Madelaine. QCSP on partially reflexive cycles - the wavy line of tractability
- Jozef Jirasek and Galina Jiraskova. Cyclic shift on prefix-free languages
- Abuzer Yakaryilmaz. One-counter verifiers for decidable languages
- Armin Weiss and Volker Diekert. QuickHeapsort: Modifications and improved analysis
- Manfred Droste and Vitaly Perevoshchikov. Multi-weighted automata and MSO logic
- Mark Braverman, Ankit Garg, Denis Pankratov and Omri Weinstein. Information lower bounds via self-reducibility
- Sergey Avgustinovich and Svetlana Puzynina. Weak abelian periodicity of infinite words
- Sven De Felice and Cyril Nicaud. Random generation of deterministic acyclic automata using the recursive method
- Abuzer Yakaryilmaz. Quantum alternation
- Luke Friedman and Yixin Xu. Exponential lower bounds for refuting random formulas using ordered binary decision diagrams
- Pawel Gawrychowski. Alphabetic minimax trees in linear time