:facetid:toc:\"db/conf/stacs/stacs2018.bht\"OK:facetid:toc:db/conf/stacs/stacs2018.bhtHiroshi Hirai 0001Yuni IwamasaKazuo MurotaStanislav ZivnýBeyond JWP: A Tractable Class of Binary VCSPs via M-Convex Intersection.STACS39:1-39:142018Conference and Workshop Papersopenconf/stacs/0001IMZ1810.4230/LIPICS.STACS.2018.39https://doi.org/10.4230/LIPIcs.STACS.2018.39https://dblp.org/rec/conf/stacs/0001IMZ18URL#2668009Marco Bressan 0002Enoch PesericoLuca PrettoOn Approximating the Stationary Distribution of Time-reversible Markov Chains.STACS18:1-18:142018Conference and Workshop Papersopenconf/stacs/0002PP1810.4230/LIPICS.STACS.2018.18https://doi.org/10.4230/LIPIcs.STACS.2018.18https://dblp.org/rec/conf/stacs/0002PP18URL#2668010Anna AdamaszekAntonios Antoniadis 0001Amit Kumar 0001Tobias MömkeApproximating Airports and Railways.STACS5:1-5:132018Conference and Workshop Papersopenconf/stacs/AdamaszekA0M1810.4230/LIPICS.STACS.2018.5https://doi.org/10.4230/LIPIcs.STACS.2018.5https://dblp.org/rec/conf/stacs/AdamaszekA0M18URL#2668011Isolde AdlerFrederik HarwathProperty Testing for Bounded Degree Databases.STACS6:1-6:142018Conference and Workshop Papersopenconf/stacs/AdlerH1810.4230/LIPICS.STACS.2018.6https://doi.org/10.4230/LIPIcs.STACS.2018.6https://dblp.org/rec/conf/stacs/AdlerH18URL#2668012Akanksha Agrawal 0001Daniel LokshtanovPranabendu MisraSaket Saurabh 0001Meirav ZehaviErdös-Pósa Property of Obstructions to Interval Graphs.STACS7:1-7:152018Conference and Workshop Papersopenconf/stacs/AgrawalLM0Z1810.4230/LIPICS.STACS.2018.7https://doi.org/10.4230/LIPIcs.STACS.2018.7https://dblp.org/rec/conf/stacs/AgrawalLM0Z18URL#2668013Andris AmbainisMartins KokainisKrisjanis PrusisJevgenijs VihrovsAll Classical Adversary Methods are Equivalent for Total Functions.STACS8:1-8:142018Conference and Workshop Papersopenconf/stacs/AmbainisKPV1810.4230/LIPICS.STACS.2018.8https://doi.org/10.4230/LIPIcs.STACS.2018.8https://dblp.org/rec/conf/stacs/AmbainisKPV18URL#2668014Max BannachTill TantauComputing Hitting Set Kernels By AC0-Circuits.STACS9:1-9:142018Conference and Workshop Papersopenconf/stacs/BannachT1810.4230/LIPICS.STACS.2018.9https://doi.org/10.4230/LIPIcs.STACS.2018.9https://dblp.org/rec/conf/stacs/BannachT18URL#2668015Rémy BelmonteMichael LampisValia MitsouParameterized (Approximate) Defective Coloring.STACS10:1-10:152018Conference and Workshop Papersopenconf/stacs/BelmonteLM1810.4230/LIPICS.STACS.2018.10https://doi.org/10.4230/LIPIcs.STACS.2018.10https://dblp.org/rec/conf/stacs/BelmonteLM18URL#2668016Christoph BerkholzThe Relation between Polynomial Calculus, Sherali-Adams, and Sum-of-Squares Proofs.STACS11:1-11:142018Conference and Workshop Papersopenconf/stacs/Berkholz1810.4230/LIPICS.STACS.2018.11https://doi.org/10.4230/LIPIcs.STACS.2018.11https://dblp.org/rec/conf/stacs/Berkholz18URL#2668017Olaf BeyersdorffJoshua BlinkhornGenuine Lower Bounds for QBF Expansion.STACS12:1-12:152018Conference and Workshop Papersopenconf/stacs/BeyersdorffB1810.4230/LIPICS.STACS.2018.12https://doi.org/10.4230/LIPIcs.STACS.2018.12https://dblp.org/rec/conf/stacs/BeyersdorffB18URL#2668018Laurent BienvenuRodney G. DowneyOn Low for Speed Oracles.STACS15:1-15:132018Conference and Workshop Papersopenconf/stacs/BienvenuD1810.4230/LIPICS.STACS.2018.15https://doi.org/10.4230/LIPIcs.STACS.2018.15https://dblp.org/rec/conf/stacs/BienvenuD18URL#2668019Davide BilòKeerti ChoudharyLuciano GualàStefano Leucci 0001Merav ParterGuido ProiettiEfficient Oracles and Routing Schemes for Replacement Paths.STACS13:1-13:152018Conference and Workshop Papersopenconf/stacs/BiloCG0PP1810.4230/LIPICS.STACS.2018.13https://doi.org/10.4230/LIPIcs.STACS.2018.13https://dblp.org/rec/conf/stacs/BiloCG0PP18URL#2668020Davide BilòPascal LenznerOn the Tree Conjecture for the Network Creation Game.STACS14:1-14:152018Conference and Workshop Papersopenconf/stacs/BiloL1810.4230/LIPICS.STACS.2018.14https://doi.org/10.4230/LIPIcs.STACS.2018.14https://dblp.org/rec/conf/stacs/BiloL18URL#2668021Michael BlondinJavier EsparzaStefan JaaxLarge Flocks of Small Birds: on the Minimal Size of Population Protocols.STACS16:1-16:142018Conference and Workshop Papersopenconf/stacs/BlondinEJ1810.4230/LIPICS.STACS.2018.16https://doi.org/10.4230/LIPIcs.STACS.2018.16https://dblp.org/rec/conf/stacs/BlondinEJ18URL#2668022Benedikt BolligMarie FortinPaul GastinCommunicating Finite-State Machines and Two-Variable Logic.STACS17:1-17:142018Conference and Workshop Papersopenconf/stacs/BolligFG1810.4230/LIPICS.STACS.2018.17https://doi.org/10.4230/LIPIcs.STACS.2018.17https://dblp.org/rec/conf/stacs/BolligFG18URL#2668023Clément CarbonnelDavid A. CohenMartin C. CooperStanislav ZivnýOn Singleton Arc Consistency for CSPs Defined by Monotone Patterns.STACS19:1-19:152018Conference and Workshop Papersopenconf/stacs/CarbonnelCCZ1810.4230/LIPICS.STACS.2018.19https://doi.org/10.4230/LIPIcs.STACS.2018.19https://dblp.org/rec/conf/stacs/CarbonnelCCZ18URL#2668024Bernadette Charron-BostShlomo MoranThe Firing Squad Problem Revisited.STACS20:1-20:142018Conference and Workshop Papersopenconf/stacs/Charron-BostM1810.4230/LIPICS.STACS.2018.20https://doi.org/10.4230/LIPIcs.STACS.2018.20https://dblp.org/rec/conf/stacs/Charron-BostM18URL#2668025Suryajith ChillaraNutan LimayeSrikanth Srinivasan 0001Small-depth Multilinear Formula Lower Bounds for Iterated Matrix Multiplication, with Applications.STACS21:1-21:152018Conference and Workshop Papersopenconf/stacs/ChillaraL01810.4230/LIPICS.STACS.2018.21https://doi.org/10.4230/LIPIcs.STACS.2018.21https://dblp.org/rec/conf/stacs/ChillaraL018URL#2668026Raphaël CliffordAllan GrønlundKasper Green LarsenTatiana StarikovskayaUpper and Lower Bounds for Dynamic Data Structures on Strings.STACS22:1-22:142018Conference and Workshop Papersopenconf/stacs/CliffordGLS1810.4230/LIPICS.STACS.2018.22https://doi.org/10.4230/LIPIcs.STACS.2018.22https://dblp.org/rec/conf/stacs/CliffordGLS18URL#2668027Debarati Das 0001Michal Koucký 0001Michael E. SaksLower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication.STACS23:1-23:142018Conference and Workshop Papersopenconf/stacs/DasKS1810.4230/LIPICS.STACS.2018.23https://doi.org/10.4230/LIPIcs.STACS.2018.23https://dblp.org/rec/conf/stacs/DasKS18URL#2668028Erik D. DemaineSarah EisenstatMikhail RudoySolving the Rubik's Cube Optimally is NP-complete.STACS24:1-24:132018Conference and Workshop Papersopenconf/stacs/DemaineER1810.4230/LIPICS.STACS.2018.24https://doi.org/10.4230/LIPIcs.STACS.2018.24https://dblp.org/rec/conf/stacs/DemaineER18URL#2668029Gökalp DemirciHenry HoffmannDavid H. K. KimApproximation Algorithms for Scheduling with Resource and Precedence Constraints.STACS25:1-25:142018Conference and Workshop Papersopenconf/stacs/DemirciHK1810.4230/LIPICS.STACS.2018.25https://doi.org/10.4230/LIPIcs.STACS.2018.25https://dblp.org/rec/conf/stacs/DemirciHK18URL#2668030Pavel DvorákAndreas Emil FeldmannDusan KnopTomás MasaríkTomas ToufarPavel Veselý 0001Parameterized Approximation Schemes for Steiner Trees with Small Number of Steiner Vertices.STACS26:1-26:152018Conference and Workshop Papersopenconf/stacs/DvorakFKMTV1810.4230/LIPICS.STACS.2018.26https://doi.org/10.4230/LIPIcs.STACS.2018.26https://dblp.org/rec/conf/stacs/DvorakFKMTV18URL#2668031László EgriDániel MarxPawel RzazewskiFinding List Homomorphisms from Bounded-treewidth Graphs to Reflexive Graphs: a Complete Complexity Characterization.STACS27:1-27:152018Conference and Workshop Papersopenconf/stacs/EgriMR1810.4230/LIPICS.STACS.2018.27https://doi.org/10.4230/LIPIcs.STACS.2018.27https://dblp.org/rec/conf/stacs/EgriMR18URL#2668032Eduard EibenRobert GanianSebastian OrdyniakSmall Resolution Proofs for QBF using Dependency Treewidth.STACS28:1-28:152018Conference and Workshop Papersopenconf/stacs/EibenGO1810.4230/LIPICS.STACS.2018.28https://doi.org/10.4230/LIPIcs.STACS.2018.28https://dblp.org/rec/conf/stacs/EibenGO18URL#2668033Eduard EibenMithilesh Kumar 0001Amer E. MouawadFahad PanolanSebastian SiebertzLossy Kernels for Connected Dominating Set on Sparse Graphs.STACS29:1-29:152018Conference and Workshop Papersopenconf/stacs/EibenKMPS1810.4230/LIPICS.STACS.2018.29https://doi.org/10.4230/LIPIcs.STACS.2018.29https://dblp.org/rec/conf/stacs/EibenKMPS18URL#2668034Lukas FleischerManfred KufleitnerThe Intersection Problem for Finite Monoids.STACS30:1-30:142018Conference and Workshop Papersopenconf/stacs/FleischerK1810.4230/LIPICS.STACS.2018.30https://doi.org/10.4230/LIPIcs.STACS.2018.30https://dblp.org/rec/conf/stacs/FleischerK18URL#2668035Moses GanardiDanny HuckeDaniel KönigMarkus LohreyKonstantinos MamourasAutomata Theory on Sliding Windows.STACS31:1-31:142018Conference and Workshop Papersopenconf/stacs/GanardiHKLM1810.4230/LIPICS.STACS.2018.31https://doi.org/10.4230/LIPIcs.STACS.2018.31https://dblp.org/rec/conf/stacs/GanardiHKLM18URL#2668036Moses GanardiDaniel KönigMarkus LohreyGeorg ZetzscheKnapsack Problems for Wreath Products.STACS32:1-32:132018Conference and Workshop Papersopenconf/stacs/GanardiKLZ1810.4230/LIPICS.STACS.2018.32https://doi.org/10.4230/LIPIcs.STACS.2018.32https://dblp.org/rec/conf/stacs/GanardiKLZ18URL#2668037Robert GanianFabian KluteSebastian OrdyniakOn Structural Parameterizations of the Bounded-Degree Vertex Deletion Problem.STACS33:1-33:142018Conference and Workshop Papersopenconf/stacs/GanianKO1810.4230/LIPICS.STACS.2018.33https://doi.org/10.4230/LIPIcs.STACS.2018.33https://dblp.org/rec/conf/stacs/GanianKO18URL#2668038