Leveraging decision diagrams to solve two-stage stochastic programs with binary recourse and logical linking constraints. (English) Zbl 07864401
MSC:
90Bxx
Found 157 Documents (Results 1–100)
Feature necessity & relevancy in ML classifier explanations. (English) Zbl 07777304
Sankaranarayanan, Sriram (ed.) et al., Tools and algorithms for the construction and analysis of systems. 29th international conference, TACAS 2023, held as part of the European joint conferences on theory and practice of software, ETAPS 2023, Paris, France, April 22–27, 2023. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 13993, 167-186 (2023).
MSC:
68T05
Deterministic construction of QFAs based on the quantum fingerprinting technique. (English) Zbl 07688854
Quantum versus classical online streaming algorithms with logarithmic size of memory. (English) Zbl 07688852
Decision diagrams for discrete optimization: a survey of recent advances. (English) Zbl 07587569
MSC:
90Cxx
Second-order finite automata. (English) Zbl 1510.68035
Two-way and one-way quantum and classical automata with advice for online minimization problems. (English) Zbl 1535.68128
Proof complexity of symbolic QBF reasoning. (English) Zbl 07495588
Li, Chu-Min (ed.) et al., Theory and applications of satisfiability testing – SAT 2021. 24th international conference, Barcelona, Spain, July 5–9, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12831, 399-416 (2021).
A polynomial-time construction of a hitting set for read-once branching programs of width 3. (English) Zbl 1522.68176
Circuit complexity of regular languages. (English) Zbl 1510.68037
Pin, Jean-Éric (ed.), Handbook of automata theory. Volume I. Theoretical foundations. Berlin: European Mathematical Society (EMS). 493-523 (2021).
Reviewer: Klaus D. Kiermeier (Berlin)
Exact multiple sequence alignment by synchronized decision diagrams. (English) Zbl 07362343
MSC:
90Cxx
Graph coloring lower bounds from decision diagrams. (English) Zbl 1503.90081
Bienstock, Daniel (ed.) et al., Integer programming and combinatorial optimization. 21st international conference, IPCO 2020, London, UK, June 8–10, 2020, Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12125, 405-418 (2020).
Improving OBDD attacks against stream ciphers. (English) Zbl 1473.94106
MSC:
94A60
On OBDD-based algorithms and proof systems that dynamically change the order of variables. (English) Zbl 1497.68218
Connecting knowledge compilation classes and width parameters. (Connecting knowledge compilation classes width parameters.) (English) Zbl 1446.68149
On Tseitin formulas, read-once branching programs and treewidth. (English) Zbl 1517.68091
van Bevern, René (ed.) et al., Computer science – theory and applications. 14th international computer science symposium in Russia, CSR 2019, Novosibirsk, Russia, July 1–5, 2019. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 11532, 143-155 (2019).
Classical and quantum computations with restricted memory. (English) Zbl 1514.68073
Böckenhauer, Hans-Joachim (ed.) et al., Adventures between lower bounds and higher altitudes. Essays dedicated to Juraj Hromkovič on the occasion of his 60th birthday. Cham: Springer. Lect. Notes Comput. Sci. 11011, 129-155 (2018).
A comparison of BDD-based parity game solvers. (English) Zbl 1528.68235
Orlandini, Andrea (ed.) et al., Proceedings of the ninth international symposium on games, automata, logics, and formal verification, GandALF 2018, Saarbrücken, Germany, September 26–28, 2018. Waterloo: Open Publishing Association (OPA). Electron. Proc. Theor. Comput. Sci. (EPTCS) 277, 103-117 (2018).
Error-free affine, unitary, and probabilistic OBDDs. (English) Zbl 1435.68072
Konstantinidis, Stavros (ed.) et al., Descriptional complexity of formal systems. 20th IFIP WG 1.02 international conference, DCFS 2018, Halifax, NS, Canada, July 25–27, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10952, 175-187 (2018).
New size hierarchies for two way automata. (English) Zbl 1403.68114
MSC:
68Q45
A moderately exponential time algorithm for \(k\)-IBDD satisfiability. (English) Zbl 1391.68101
MSC:
68T20
Size-treewidth tradeoffs for circuits computing the element distinctness function. (English) Zbl 1386.68065
A simpler rate-optimal CPIR protocol. (English) Zbl 1460.94054
Kiayias, Aggelos (ed.), Financial cryptography and data security. 21st international conference, FC 2017, Sliema, Malta, April 3–7, 2017. Revised selected papers. Cham: Springer. Lect. Notes Comput. Sci. 10322, 621-638 (2017).
Satisfiable Tseitin formulas are hard for nondeterministic read-once branching programs. (English) Zbl 1441.68156
Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 26, 12 p. (2017).
On oblivious branching programs with bounded repetition that cannot efficiently compute CNFs of bounded treewidth. (English) Zbl 1378.68035
Reordering method and hierarchies for quantum and classical ordered binary decision diagrams. (English) Zbl 1489.68061
Weil, Pascal (ed.), Computer science – theory and applications. 12th international computer science symposium in Russia, CSR 2017, Kazan, Russia, June 8–12, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10304, 162-175 (2017).
Nondeterministic unitary OBDDs. (English) Zbl 1489.68060
Weil, Pascal (ed.), Computer science – theory and applications. 12th international computer science symposium in Russia, CSR 2017, Kazan, Russia, June 8–12, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10304, 126-140 (2017).
A deterministic algorithm for testing the equivalence of read-once branching programs with small discrepancy. (English) Zbl 1489.68398
Kari, Jarkko (ed.) et al., Unveiling dynamics and complexity. 13th conference on computability in Europe, CiE 2017, Turku, Finland, June 12–16, 2017. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10307, 119-128 (2017).
Chordal networks of polynomial ideals. (English) Zbl 1444.13037
Reviewer: Francesca Cioffi (Napoli)
Theoretical insights and algorithmic tools for decision diagram-based optimization. (English) Zbl 1368.90105
MSC:
90C10
On the hierarchies for deterministic, nondeterministic and probabilistic ordered read-\(k\)-times branching programs. (English) Zbl 1409.68105
Sequence binary decision diagram: minimization, relationship to acyclic automata, and complexities of Boolean set operations. (English) Zbl 1350.68066
On the read-once property of branching programs and CNFs of bounded treewidth. (English) Zbl 1350.68156
Investigating dynamic causalities in reaction systems. (English) Zbl 1336.68065
MSC:
68Q05
68Q10
VeriSIMPL 2: an open-source software for the verification of max-plus-linear systems. (English) Zbl 1332.93255
Comparative complexity of quantum and classical OBDDs for total and partial functions. (English. Russian original) Zbl 1347.68137
Russ. Math. 59, No. 11, 26-35 (2015); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 2015, No. 11, 32-45 (2015).
Randomized OBDD-based graph algorithms. (English) Zbl 1407.68532
Scheideler, Christian (ed.), Structural information and communication complexity. 22nd international colloquium, SIROCCO 2015, Montserrat, Spain, July 14–16, 2015. Post-proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9439, 254-269 (2015).
Forms of representation for simple games: sizes, conversions and equivalences. (English) Zbl 1331.91023
A moderately exponential time algorithm for \(k\)-IBDD satisfiability. (English) Zbl 1392.68390
Dehne, Frank (ed.) et al., Algorithms and data structures. 14th international symposium, WADS 2015, Victoria, BC, Canada, August 5–7, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-21839-7/pbk; 978-3-319-21840-3/ebook). Lecture Notes in Computer Science 9214, 554-565 (2015).
On compiling structured CNFs to OBDDs. (English) Zbl 1378.68027
Beklemishev, Lev D. (ed.) et al., Computer science – theory and applications. 10th international computer science symposium in Russia, CSR 2015, Listvyanka, Russia, July 13–17, 2015. Proceedings. Cham: Springer (ISBN 978-3-319-20296-9/pbk; 978-3-319-20297-6/ebook). Lecture Notes in Computer Science 9139, 80-93 (2015).
Width hierarchy for \(k\)-OBDD of small width. (English) Zbl 1346.68092
MSC:
68Q05
68Q15
Computing Boolean functions via quantum hashing. (English) Zbl 1323.68266
Calude, Cristian S. (ed.) et al., Computing with new resources. Essays dedicated to Jozef Gruska on the occasion of his 80th birthday. Cham: Springer (ISBN 978-3-319-13349-2/pbk; 978-3-319-13350-8/ebook). Lecture Notes in Computer Science 8808, 149-160 (2014).
MSC:
68Q05
81P68
Implicit computation of maximum bipartite matchings by sublinear functional operations. (English) Zbl 1303.68065
A simpler counterexample to a long-standing conjecture on the complexity of Bryant’s apply algorithm. (English) Zbl 1284.68209
Specification-guided controller synthesis for linear systems and safe linear-time temporal logic. (English) Zbl 1362.93059
Proceedings of the 16th ACM international conference on hybrid systems: computation and control, HSCC 2013, Philadelphia, PA, USA, April 8–11, 2013. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-1567-8). 333-342 (2013).
Knowledge compilation meets database theory: compiling queries to decision diagrams. (English) Zbl 1270.68297
Extension of the hierarchy for \(k\)-OBDDs of small width. (English. Russian original) Zbl 1290.68040
Russ. Math. 57, No. 3, 46-50 (2013); translation from Izv. Vyssh. Uchebn. Zaved., Mat. 2013, No. 3, 56-61 (2013).
MSC:
68Q05
68Q15
Relation-algebraic modeling and solution of chessboard independence and domination problems. (English) Zbl 1280.68301
On the use of binary decision diagrams for solving problems on simple games. (English) Zbl 1253.91014
On the contribution of backward jumps to instruction sequence expressiveness. (English) Zbl 1279.68182
Symbolic bounded synthesis. (English) Zbl 1247.68163
Implicit computation of maximum bipartite matchings by sublinear functional operations. (English) Zbl 1354.05128
Agrawal, Manindra (ed.) et al., Theory and applications of models of computation. 9th annual conference, TAMC 2012, Beijing, China, May 16–21, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-29951-3/pbk). Lecture Notes in Computer Science 7287, 473-486 (2012).
A sufficient condition for sets hitting the class of read-once branching programs of width 3 (extended abstract). (English) Zbl 1302.68118
Bieliková, Mária (ed.) et al., SOFSEM 2012: Theory and practice of computer science. 38th conference on current trends in theory and practice of computer science, Špindlerův Mlýn, Czech Republic, January 21–27, 2012. Proceedings. Berlin: Springer (ISBN 978-3-642-27659-0/pbk). Lecture Notes in Computer Science 7147, 406-418 (2012).
MSC:
68Q05
Randomized OBDDs for the most significant bit of multiplication need exponential space. (English) Zbl 1260.68151
Yet harder knapsack problems. (English) Zbl 1233.68145
Generic constant-round oblivious sorting algorithm for MPC. (English) Zbl 1298.94115
Boyen, Xavier (ed.) et al., Provable security. 5th international conference, ProvSec 2011, Xi’an, China, October 16–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-24315-8/pbk). Lecture Notes in Computer Science 6980, 240-256 (2011).
Almost \(k\)-wise independent sets establish hitting sets for width-3 1-branching programs. (English) Zbl 1330.68126
Kulikov, Alexander (ed.) et al., Computer science – theory and applications. 6th international computer science symposium in Russia, CSR 2011, St. Petersburg, Russia, June 14–18, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-20711-2/pbk). Lecture Notes in Computer Science 6651, 120-133 (2011).
Power indices of simple games and vector-weighted majority games by means of binary decision diagrams. (English) Zbl 1210.91012
On the OBDD complexity of the most significant bit of integer multiplication. (English) Zbl 1220.68059
Reviewer: Thomas Jansen (Cork)
A well-mixed function with circuit complexity \(5n\): tightness of the Lachish-Raz-type bounds. (English) Zbl 1217.68103
MSC:
68Q17
94C10
New results on the most significant bit of integer multiplication. (English) Zbl 1209.68270
MSC:
68Q25
94C10
Randomized OBDDs for the most significant bit of multiplication need exponential size. (English) Zbl 1298.68109
Černá, Ivana (ed.) et al., SOFSEM 2011: Theory and practice of computer science. 37th conference on current trends in theory and practice of computer science, Nový Smokovec, Slovakia, January 22–28, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-18380-5/pbk). Lecture Notes in Computer Science 6543, 135-145 (2011).
Partially-shared zero-suppressed multi-terminal BDDs: Concept, algorithms and applications. (English) Zbl 1214.68219
An asymptotically optimal lower bound on the OBDD size of the middle bit of multiplication for the pairwise ascending variable order. (English) Zbl 1206.68152
A direct construction of polynomial-size OBDD proof of pigeon hole problem. (English) Zbl 1217.03044
Branching programs for tree evaluation. (English) Zbl 1250.68106
Královič, Rastislav (ed.) et al., Mathematical foundations of computer science 2009. 34th international symposium, MFCS 2009, Novy Smokovec, High Tatras, Slovakia, August 24–28, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-03815-0/pbk). Lecture Notes in Computer Science 5734, 175-186 (2009).
Filter Results by …
Document Type
- Journal Articles (123)
- Collection Articles (34)
all
top 5
Author
- Bollig, Beate (29)
- Khadiev, Kamil (8)
- Sauerhoff, Martin (8)
- van Hoeve, Willem-Jan (8)
- Wegener, Ingo (8)
- Ablaev, Farid M. (6)
- Yukna, Stasys P. (6)
- Khadieva, Aliya (5)
- Sieling, Detlef (5)
- Woelfel, Philipp (5)
- Yakaryılmaz, Abuzer (5)
- Ciré, André Augusto (4)
- Gille, Marc (4)
- Homeister, Matthias (4)
- Itsykson, Dmitry M. (4)
- Waack, Stephan (4)
- Zak, Stanislav (4)
- Brosenne, Henrik (3)
- Bury, Marc (3)
- Gainutdinova, Aida (3)
- Glinskih, Ludmila (3)
- Hooker, John N. jun. (3)
- Ibrahimov, Rishat (3)
- Mannapov, Ilnaz (3)
- Pröger, Tobias (3)
- Šíma, Jiří (3)
- Slivovsky, Friedrich (3)
- Baier, Christel (2)
- Berghammer, Rudolf (2)
- Bolus, Stefan (2)
- Bova, Simone (2)
- Bryant, Randal E. (2)
- Buttkus, Matthias (2)
- De Oliveira Oliveira, Mateus (2)
- Gronemeier, Andre (2)
- Karpinski, Marek (2)
- Koucký, Michal (2)
- Kravchenko, Dmitry (2)
- Mazo, Manuel jun. (2)
- McKenzie, Pierre (2)
- Meer, Klaus (2)
- Nagao, Atsuki (2)
- Parrilo, Pablo A. (2)
- Prūsis, Krišjānis (2)
- Range, Niko (2)
- Razgon, Igor (2)
- Rivosh, Alexander (2)
- Savický, Petr (2)
- Schnitger, Georg (2)
- Seto, Kazuhisa (2)
- Tabuada, Paulo (2)
- Teruyama, Junichi (2)
- Vasil’ev, Aleksandr Valer’evich (2)
- Yamilov, Ramis (2)
- Ziatdinov, Mansur (2)
- Abate, Alessandro (1)
- Ablayev, Marat (1)
- Adzkiya, Dieky (1)
- Amano, Kazuyuki (1)
- Amarilli, Antoine (1)
- Andrade de Melo, Alexsander (1)
- Arimura, Hiroki (1)
- Arnold, Stefan (1)
- Barbuti, Roberto (1)
- Barrett, Chris L. (1)
- Beame, Paul W. (1)
- Beck, J. Christopher (1)
- Behle, Markus (1)
- Bergstra, Jan A. (1)
- Bethke, Inge (1)
- Bodur, Merve (1)
- Braverman, Mark (1)
- Bro Miltersen, Peter (1)
- Capelle, Michael (1)
- Capelli, Florent (1)
- Castro, Margarita Paz (1)
- Chechik, Marsha (1)
- Chen, Wei (1)
- Christian, Tjandraatmadja (1)
- Cifuentes, Diego (1)
- Cook, Stephen Arthur (1)
- Cooper, Martin C. (1)
- Damm, Carsten (1)
- Davarnia, Danial (1)
- Denzumi, Shuhei (1)
- Devereux, Benet (1)
- Ďuriš, Pavol (1)
- Easterbrook, Steve (1)
- Ehlers, Rüdiger (1)
- Eibach, Tobias (1)
- Farenholtz, Martin (1)
- Fawzi, Hamza (1)
- Fronk, Alexander (1)
- Gainutdinova, A. F. (1)
- Gál, Anna (1)
- Gori, Roberta (1)
- Gouveia, Joao (1)
- Guglielmi, Alessio (1)
- Gurfinkel, Arie (1)
- Hosseininasab, Amin (1)
- and 78 more Authors
all
top 5
Serial
- Theory Comput. Syst. (17)
- Theor. Comput. Sci. (16)
- Inf. Process. Lett. (14)
- Discrete Appl. Math. (8)
- Inf. Comput. (8)
- Lobachevskii J. Math. (7)
- INFORMS J. Comput. (5)
- J. Comput. Syst. Sci. (4)
- Algorithmica (3)
- Eur. J. Oper. Res. (3)
- Math. Program. (3)
- Russ. Math. (3)
- Form. Methods Syst. Des. (3)
- Theor. Inform. Appl. (3)
- J. Symb. Log. (2)
- Constraints (2)
- J. Log. Algebr. Program. (2)
- Artif. Intell. (1)
- Discrete Math. (1)
- Inf. Sci. (1)
- Syst. Control Lett. (1)
- Sci. Comput. Program. (1)
- Math. Soc. Sci. (1)
- J. Symb. Comput. (1)
- J. Autom. Reasoning (1)
- Int. J. Found. Comput. Sci. (1)
- Discrete Event Dyn. Syst. (1)
- SIAM Rev. (1)
- Ann. Math. Artif. Intell. (1)
- J. Comb. Optim. (1)
- Fundam. Inform. (1)
- ACM Trans. Comput. Log. (1)
- J. Discrete Algorithms (1)
- Cryptogr. Commun. (1)
- Math. Program. Comput. (1)
- SIAM J. Appl. Algebra Geom. (1)
- Mat. Vopr. Kriptografii (1)
all
top 3
Software
- CUDD (10)
- azove (7)
- DIMACS (5)
- NuSMV (3)
- RelView (3)
- JBool (2)
- SINGULAR (2)
- SageMath (2)
- SparseMatrix (2)
- ATERM (1)
- Algorithm 97 (1)
- Binomials.m2 (1)
- Biq Mac (1)
- BuDDy (1)
- CAQE (1)
- CASPA (1)
- CPLEX (1)
- Chord (1)
- Chordal (1)
- ComputeTW (1)
- Concorde (1)
- DepQBF (1)
- Epsilon (1)
- FaPAS (1)
- GitHub (1)
- ISOLATE (1)
- JuMP (1)
- KEEL (1)
- KURE (1)
- Keccak (1)
- LTL2BA (1)
- MIPLIB (1)
- MUSCLE (1)
- Macaulay2 (1)
- Matlab (1)
- Maxplus (1)
- MiniSat (1)
- PATRICIA (1)
- PDDL (1)
- PESSOA (1)
- PMLB (1)
- PRISM (1)
- QESTO (1)
- QISKit (1)
- Quaffle (1)
- RAReQS (1)
- RSat (1)
- RegularChains (1)
- Reo (1)
- SAPPORO BDD (1)
- SATLIB (1)
- SATzilla (1)
- SCIP (1)
- SCTL-MUS (1)
- SHOT (1)
- SLAM (1)
- SPIN (1)
- Sharemind (1)
- VIFF (1)
- VeriSIMPL (1)
- clasp (1)
- eSTREAM (1)
- iRRAM (1)
- shap (1)
- sharpSAT (1)
- slimgb (1)
