Bérczi, Kristóf; Boros, Endre; Čepek, Ondřej; Kučera, Petr; Makino, Kazuhisa Unique key Horn functions. (English) Zbl 1500.68005 Theor. Comput. Sci. 922, 170-178 (2022). Reviewer: Hirokazu Nishimura (Tsukuba) MSC: 68P15 03B05 05C65 06E30 68Q25 68W25 PDFBibTeX XMLCite \textit{K. Bérczi} et al., Theor. Comput. Sci. 922, 170--178 (2022; Zbl 1500.68005) Full Text: DOI arXiv
Bérczi, Kristóf; Boros, Endre; Čepek, Ondřej; Kučera, Petr; Makino, Kazuhisa Approximating minimum representations of key Horn functions. (English) Zbl 1504.68052 SIAM J. Comput. 51, No. 1, 116-138 (2022). MSC: 68P15 03B05 05C65 06E30 68Q25 68W25 PDFBibTeX XMLCite \textit{K. Bérczi} et al., SIAM J. Comput. 51, No. 1, 116--138 (2022; Zbl 1504.68052) Full Text: DOI arXiv
Gkenosis, Dimitrios; Grammel, Nathaniel; Hellerstein, Lisa; Kletenik, Devorah The stochastic Boolean function evaluation problem for symmetric Boolean functions. (English) Zbl 07456399 Discrete Appl. Math. 309, 269-277 (2022). MSC: 68W25 06E30 94D10 PDFBibTeX XMLCite \textit{D. Gkenosis} et al., Discrete Appl. Math. 309, 269--277 (2022; Zbl 07456399) Full Text: DOI arXiv
Srinivasan, Srikanth; Tripathi, Utkarsh; Venkitesh, S. On the probabilistic degrees of symmetric Boolean functions. (English) Zbl 1527.68088 SIAM J. Discrete Math. 35, No. 3, 2070-2092 (2021). MSC: 68Q25 06E30 68Q06 68Q10 68Q17 PDFBibTeX XMLCite \textit{S. Srinivasan} et al., SIAM J. Discrete Math. 35, No. 3, 2070--2092 (2021; Zbl 1527.68088) Full Text: DOI arXiv
Jeřábek, Emil On the complexity of the clone membership problem. (English) Zbl 1522.68240 Theory Comput. Syst. 65, No. 5, 839-868 (2021). MSC: 68Q25 06E30 08A40 68Q06 68Q17 PDFBibTeX XMLCite \textit{E. Jeřábek}, Theory Comput. Syst. 65, No. 5, 839--868 (2021; Zbl 1522.68240) Full Text: DOI arXiv
Belovs, Aleksandrs; Blais, Eric A polynomial lower bound for testing monotonicity. (English) Zbl 1522.68238 SIAM J. Comput. 50, No. 3, STOC16-406-STOC16-433 (2021). MSC: 68Q17 06E30 68Q25 68W20 PDFBibTeX XMLCite \textit{A. Belovs} and \textit{E. Blais}, SIAM J. Comput. 50, No. 3, STOC16--406-STOC16--433 (2021; Zbl 1522.68238) Full Text: DOI
Bun, Mark; Kothari, Robin; Thaler, Justin The polynomial method strikes back: tight quantum query bounds via dual polynomials. (English) Zbl 1462.68060 Theory Comput. 16, Paper No. 10, 71 p. (2020). MSC: 68Q12 06E30 68Q17 PDFBibTeX XMLCite \textit{M. Bun} et al., Theory Comput. 16, Paper No. 10, 71 p. (2020; Zbl 1462.68060) Full Text: DOI
Sherstov, Alexander A. Algorithmic polynomials. (English) Zbl 1495.68096 SIAM J. Comput. 49, No. 6, 1173-1231 (2020). MSC: 68Q17 03B05 06E30 68Q12 81P68 PDFBibTeX XMLCite \textit{A. A. Sherstov}, SIAM J. Comput. 49, No. 6, 1173--1231 (2020; Zbl 1495.68096) Full Text: DOI
Kozachinskiy, Alexander Recognizing read-once functions from depth-three formulas. (English) Zbl 1434.68201 Theory Comput. Syst. 64, No. 1, 3-16 (2020). MSC: 68Q25 06E30 68Q17 PDFBibTeX XMLCite \textit{A. Kozachinskiy}, Theory Comput. Syst. 64, No. 1, 3--16 (2020; Zbl 1434.68201) Full Text: DOI arXiv
Srinivasan, Srikanth; Tripathi, Utkarsh; Venkitesh, S. On the probabilistic degrees of symmetric Boolean functions. (English) Zbl 1527.68089 Chattopadhyay, Arkadev (ed.) et al., 39th IARCS annual conference on foundations of software technology and theoretical computer science, FSTTCS 2019, Bombay, India, December 11–13, 2019. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 150, Article 28, 14 p. (2019). MSC: 68Q25 06E30 68Q06 68Q10 68Q17 PDFBibTeX XMLCite \textit{S. Srinivasan} et al., LIPIcs -- Leibniz Int. Proc. Inform. 150, Article 28, 14 p. (2019; Zbl 1527.68089) Full Text: DOI
Chattopadhyay, Eshan; Hatami, Pooya; Hosseini, Kaave; Lovett, Shachar Pseudorandom generators from polarizing random walks. (English) Zbl 1435.68217 Theory Comput. 15, Paper No. 10, 26 p. (2019). MSC: 68Q87 06E30 60G50 68Q17 68W20 PDFBibTeX XMLCite \textit{E. Chattopadhyay} et al., Theory Comput. 15, Paper No. 10, 26 p. (2019; Zbl 1435.68217) Full Text: DOI
Wu, WanQing; Zhang, HuanGuo A quantum query algorithm for computing the degree of a perfect nonlinear Boolean function. (English) Zbl 1417.81104 Quantum Inf. Process. 18, No. 3, Paper No. 62, 13 p. (2019). MSC: 81P68 81P94 94A60 06B30 68Q17 68Q12 68Q05 PDFBibTeX XMLCite \textit{W. Wu} and \textit{H. Zhang}, Quantum Inf. Process. 18, No. 3, Paper No. 62, 13 p. (2019; Zbl 1417.81104) Full Text: DOI
Keller, Nathan; Klein, Ohad WITHDRAWN: Quantum speedups need structure. arXiv:1911.03748 Preprint, arXiv:1911.03748 [cs.CC] (2019); retraction notice ibid. MSC: 68Q12 68Q15 68Q17 68Q87 06E30 05D40 BibTeX Cite \textit{N. Keller} and \textit{O. Klein}, ``WITHDRAWN: Quantum speedups need structure'', Preprint, arXiv:1911.03748 [cs.CC] (2019); retraction notice ibid. Full Text: arXiv OA License
Hamburger, Peter; Mcconnell, Ross M.; Pór, Attila; Spinrad, Jeremy P.; Xu, Zhisheng Double threshold digraphs. (English) Zbl 1512.68227 Potapov, Igor (ed.) et al., 43rd international symposium on mathematical foundations of computer science. MFCS 2018, Liverpool, United Kingdom, August 27–31, 2018. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 117, Article 69, 12 p. (2018). MSC: 68R10 05C20 06A06 68W25 91E99 PDFBibTeX XMLCite \textit{P. Hamburger} et al., LIPIcs -- Leibniz Int. Proc. Inform. 117, Article 69, 12 p. (2018; Zbl 1512.68227) Full Text: DOI arXiv
Chattopadhyay, Eshan; Hatami, Pooya; Hosseini, Kaave; Lovett, Shachar Pseudorandom generators from polarizing random walks. (English) Zbl 1441.68149 Servedio, Rocco A. (ed.), 33rd computational complexity conference, CCC 2018, June 22–24, 2018, San Diego, California, USA. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 102, Article 1, 21 p. (2018). MSC: 68Q87 06E30 60G50 68Q17 68W20 PDFBibTeX XMLCite \textit{E. Chattopadhyay} et al., LIPIcs -- Leibniz Int. Proc. Inform. 102, Article 1, 21 p. (2018; Zbl 1441.68149) Full Text: DOI
Banks, Jacqueline; Garrabrant, Scott M.; Huber, Mark L.; Perizzolo, Anne Using TPA to count linear extensions. (English) Zbl 1410.68261 J. Discrete Algorithms 51, 1-11 (2018). MSC: 68R05 06A07 68W20 68W25 PDFBibTeX XMLCite \textit{J. Banks} et al., J. Discrete Algorithms 51, 1--11 (2018; Zbl 1410.68261) Full Text: DOI arXiv
Kozachinskiy, Alexander Recognizing read-once functions from depth-three formulas. (English) Zbl 1434.68200 Fomin, Fedor V. (ed.) et al., Computer science – theory and applications. 13th international computer science symposium in Russia, CSR 2018, Moscow, Russia, June 6–10, 2018. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 10846, 232-243 (2018). MSC: 68Q25 06E30 68Q17 PDFBibTeX XMLCite \textit{A. Kozachinskiy}, Lect. Notes Comput. Sci. 10846, 232--243 (2018; Zbl 1434.68200) Full Text: DOI arXiv
Bach, Eric; Dusart, Jérémie; Hellerstein, Lisa; Kletenik, Devorah Submodular goal value of Boolean functions. (English) Zbl 1403.68340 Discrete Appl. Math. 238, 1-13 (2018). MSC: 68W25 06E30 94D10 PDFBibTeX XMLCite \textit{E. Bach} et al., Discrete Appl. Math. 238, 1--13 (2018; Zbl 1403.68340) Full Text: DOI arXiv
Bhakta, Prateek; Cousins, Ben; Fahrbach, Matthew; Randall, Dana Approximately sampling elements with fixed rank in graded posets. (English) Zbl 1410.68395 Klein, Philip N. (ed.), Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16–19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1828-1838 (2017). MSC: 68W25 05A17 06A07 60J22 PDFBibTeX XMLCite \textit{P. Bhakta} et al., in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1828--1838 (2017; Zbl 1410.68395) Full Text: DOI arXiv
Vömel, Christof; de Lorenzi, Flavio; Beer, Samuel; Fuchs, Erwin The secret life of keys: on the calculation of mechanical lock systems. (English) Zbl 1370.90232 SIAM Rev. 59, No. 2, 393-422 (2017). MSC: 90C27 05C60 06A12 68W20 90C35 90C59 PDFBibTeX XMLCite \textit{C. Vömel} et al., SIAM Rev. 59, No. 2, 393--422 (2017; Zbl 1370.90232) Full Text: DOI
Aaronson, Scott; Ambainis, Andris; Iraids, Janis; Kokainis, Martins; Smotrovs, Juris Polynomials, quantum query complexity, and Grothendieck’s inequality. (English) Zbl 1380.68184 Raz, Ran (ed.), 31st conference on computational complexity, CCC’16, Tokyo, Japan, May 29 – June 1, 2016. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-008-8). LIPIcs – Leibniz International Proceedings in Informatics 50, Article 25, 19 p. (2016). MSC: 68Q12 06E30 94C10 PDFBibTeX XMLCite \textit{S. Aaronson} et al., LIPIcs -- Leibniz Int. Proc. Inform. 50, Article 25, 19 p. (2016; Zbl 1380.68184) Full Text: DOI arXiv
Van Alten, C. J. Embedding ordered sets into distributive lattices. (English) Zbl 1357.06002 Order 33, No. 3, 419-427 (2016). Reviewer: Hernando Gaitán (Bogotá) MSC: 06D05 06A06 68Q17 68Q25 PDFBibTeX XMLCite \textit{C. J. Van Alten}, Order 33, No. 3, 419--427 (2016; Zbl 1357.06002) Full Text: DOI
Bun, Mark; Thaler, Justin Dual polynomials for collision and element distinctness. (English) Zbl 1393.68055 Theory Comput. 12, Paper No. 16, 34 p. (2016). MSC: 68Q17 06E30 68Q12 PDFBibTeX XMLCite \textit{M. Bun} and \textit{J. Thaler}, Theory Comput. 12, Paper No. 16, 34 p. (2016; Zbl 1393.68055) Full Text: DOI arXiv
Behrisch, Mike; Hermann, Miki; Mengel, Stefan; Salzer, Gernot The next whisky bar. (English) Zbl 1475.68136 Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 11th international computer science symposium in Russia, CSR 2016, St. Petersburg, Russia, June 9–13, 2016. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 9691, 41-56 (2016). MSC: 68Q25 06E30 68R07 68Q17 90C60 PDFBibTeX XMLCite \textit{M. Behrisch} et al., Lect. Notes Comput. Sci. 9691, 41--56 (2016; Zbl 1475.68136) Full Text: DOI
Simon, Hans Ulrich Efficient computation of approximate isomorphisms between Boolean functions. (English) Zbl 1347.68187 Inf. Process. Lett. 116, No. 3, 237-240 (2016). MSC: 68Q25 06E30 68W20 68W25 94C10 PDFBibTeX XMLCite \textit{H. U. Simon}, Inf. Process. Lett. 116, No. 3, 237--240 (2016; Zbl 1347.68187) Full Text: DOI
Bulatov, Andrei A.; Hedayaty, Amir Galois correspondence for counting quantifiers. (English) Zbl 1394.08009 J. Mult.-Val. Log. Soft Comput. 24, No. 5-6, 405-424 (2015). MSC: 08A70 08A40 06A15 68Q25 PDFBibTeX XMLCite \textit{A. A. Bulatov} and \textit{A. Hedayaty}, J. Mult.-Val. Log. Soft Comput. 24, No. 5--6, 405--424 (2015; Zbl 1394.08009) Full Text: arXiv Link
Bessos, Mai Ben Adar; Gabbay, Dov M. Topological aspects of matrix abduction. II. (English) Zbl 1376.06003 Koslow, Arnold (ed.) et al., The road to universal logic. Festschrift for the 50th birthday of Jean-Yves Béziau. Volume II. New York, NY: Birkhäuser/Springer (ISBN 978-3-319-15367-4/pbk; 978-3-319-15368-1/ebook). Studies in Universal Logic, 357-385 (2015). MSC: 06A07 03B48 68Q17 03B80 PDFBibTeX XMLCite \textit{M. B. A. Bessos} and \textit{D. M. Gabbay}, in: The road to universal logic. Festschrift for the 50th birthday of Jean-Yves Béziau. Volume II. New York, NY: Birkhäuser/Springer. 357--385 (2015; Zbl 1376.06003) Full Text: DOI
Cardinal, Jean; Felsner, Stefan Covering partial cubes with zones. (English) Zbl 1343.05120 Electron. J. Comb. 22, No. 3, Research Paper P3.31, 18 p. (2015). MSC: 05C70 05C60 06A07 68Q17 68Q25 68R10 PDFBibTeX XMLCite \textit{J. Cardinal} and \textit{S. Felsner}, Electron. J. Comb. 22, No. 3, Research Paper P3.31, 18 p. (2015; Zbl 1343.05120) Full Text: arXiv Link
Yuan, Chen; Kan, Haibin A refined analysis on the jump number problem of interval orders. (English) Zbl 1332.68289 Inf. Process. Lett. 115, No. 11, 797-800 (2015). MSC: 68W25 06A07 PDFBibTeX XMLCite \textit{C. Yuan} and \textit{H. Kan}, Inf. Process. Lett. 115, No. 11, 797--800 (2015; Zbl 1332.68289) Full Text: DOI
Arvind, V.; Köbler, Johannes; Kuhnert, Sebastian; Rattan, Gaurav; Vasudev, Yadu On the isomorphism problem for decision trees and decision lists. (English) Zbl 1327.68123 Theor. Comput. Sci. 590, 38-54 (2015). MSC: 68Q25 05C60 06E30 68Q17 PDFBibTeX XMLCite \textit{V. Arvind} et al., Theor. Comput. Sci. 590, 38--54 (2015; Zbl 1327.68123) Full Text: DOI
Cardinal, Jean; Felsner, Stefan Covering partial cubes with zones. (English) Zbl 1343.05119 Akiyama, Jin (ed.) et al., Discrete and computational geometry and graphs. 16th Japanese conference, JCDCGG 2013, Tokyo, Japan, September 17–19, 2013. Revised selected papers. Cham: Springer (ISBN 978-3-319-13286-0/pbk; 978-3-319-13287-7/ebook). Lecture Notes in Computer Science 8845, 1-13 (2014). MSC: 05C70 05C60 06A07 68Q17 68Q25 68R10 PDFBibTeX XMLCite \textit{J. Cardinal} and \textit{S. Felsner}, Lect. Notes Comput. Sci. 8845, 1--13 (2014; Zbl 1343.05119) Full Text: DOI arXiv
Chai, Fengjuan A step-by-step CS method and its applications in cryptanalysis of stream ciphers. (Chinese. English summary) Zbl 1313.94043 J. Syst. Sci. Math. Sci. 34, No. 3, 273-283 (2014). MSC: 94A60 68W25 06E30 PDFBibTeX XMLCite \textit{F. Chai}, J. Syst. Sci. Math. Sci. 34, No. 3, 273--283 (2014; Zbl 1313.94043)
Ambainis, Andris; De Wolf, Ronald How low can approximate degree and quantum query complexity be for total Boolean functions? (English) Zbl 1314.68133 Comput. Complexity 23, No. 2, 305-322 (2014). MSC: 68Q12 06E30 41A10 68Q17 PDFBibTeX XMLCite \textit{A. Ambainis} and \textit{R. De Wolf}, Comput. Complexity 23, No. 2, 305--322 (2014; Zbl 1314.68133) Full Text: DOI arXiv
Del Valle, Jennifer; Kreinovich, Vladik; Wojciechowski, Piotr J. Feasible algorithms for lattice and directed subspaces. (English) Zbl 1311.06016 Math. Proc. R. Ir. Acad. 114A, No. 2, 199-204 (2014). MSC: 06F25 06-04 68W30 68Q17 PDFBibTeX XMLCite \textit{J. Del Valle} et al., Math. Proc. R. Ir. Acad. 114A, No. 2, 199--204 (2014; Zbl 1311.06016) Full Text: DOI Link
Huber, Mark Near-linear time simulation of linear extensions of a height-2 poset with bounded interaction. (English) Zbl 1372.68293 Chic. J. Theor. Comput. Sci. 2014, Article No. 3, 16 p. (2014). MSC: 68W20 06A07 68Q25 68W25 PDFBibTeX XMLCite \textit{M. Huber}, Chic. J. Theor. Comput. Sci. 2014, Article No. 3, 16 p. (2014; Zbl 1372.68293) Full Text: DOI
Čepek, Ondřej; Kučera, Petr; Kuřík, Stanislav Boolean functions with long prime implicants. (English) Zbl 1285.06006 Inf. Process. Lett. 113, No. 19-21, 698-703 (2013). MSC: 06E30 68W25 68W40 94C10 PDFBibTeX XMLCite \textit{O. Čepek} et al., Inf. Process. Lett. 113, No. 19--21, 698--703 (2013; Zbl 1285.06006) Full Text: DOI
Cohen, David A.; Cooper, Martin C.; Creed, Páidí; Jeavons, Peter G.; Živný, Stanislav An algebraic theory of complexity for discrete optimization. (English) Zbl 1305.08007 SIAM J. Comput. 42, No. 5, 1915-1939 (2013). Reviewer: Václav Koubek (Praha) MSC: 08A70 06A15 68W40 68Q25 68Q17 90C27 PDFBibTeX XMLCite \textit{D. A. Cohen} et al., SIAM J. Comput. 42, No. 5, 1915--1939 (2013; Zbl 1305.08007) Full Text: DOI arXiv Link
Bachmaier, Christian; Brandenburg, Franz Josef; Gleißner, Andreas; Hofmeier, Andreas On maximum rank aggregation problems. (English) Zbl 1407.68201 Lecroq, Thierry (ed.) et al., Combinatorial algorithms. 24th international workshop, IWOCA 2013, Rouen, France, July 10–12, 2013. Revised selected papers. Berlin: Springer. Lect. Notes Comput. Sci. 8288, 14-27 (2013). MSC: 68Q25 06A06 06A07 68Q17 91B08 PDFBibTeX XMLCite \textit{C. Bachmaier} et al., Lect. Notes Comput. Sci. 8288, 14--27 (2013; Zbl 1407.68201) Full Text: DOI
Boros, Endre; Čepek, Ondřej; Kučera, Petr A decomposition method for CNF minimality proofs. (English) Zbl 1358.68120 Theor. Comput. Sci. 510, 111-126 (2013). MSC: 68Q25 06E30 68Q17 94C10 PDFBibTeX XMLCite \textit{E. Boros} et al., Theor. Comput. Sci. 510, 111--126 (2013; Zbl 1358.68120) Full Text: DOI
Krysztowiak, Przemysław An improved approximation ratio for the jump number problem on interval orders. (English) Zbl 1335.68295 Theor. Comput. Sci. 513, 77-84 (2013). MSC: 68W25 05C70 05C85 06A07 68Q17 90C27 PDFBibTeX XMLCite \textit{P. Krysztowiak}, Theor. Comput. Sci. 513, 77--84 (2013; Zbl 1335.68295) Full Text: DOI
van Alten, C. J. Partial algebras and complexity of satisfiability and universal theory for distributive lattices, Boolean algebras and Heyting algebras. (English) Zbl 1296.03020 Theor. Comput. Sci. 501, 82-92 (2013). MSC: 03B70 06D05 06D20 06E05 08A55 08A70 68Q17 68Q25 PDFBibTeX XMLCite \textit{C. J. van Alten}, Theor. Comput. Sci. 501, 82--92 (2013; Zbl 1296.03020) Full Text: DOI
Grigorescu, Elena; Wimmer, Karl; Xie, Ning Tight lower bounds for testing linear isomorphism. (English) Zbl 1405.68128 Raghavendra, Prasad (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 16th international workshop, APPROX 2013, and 17th international workshop, RANDOM 2013, Berkeley, CA, USA, August 21–23, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40327-9/pbk). Lecture Notes in Computer Science 8096, 559-574 (2013). MSC: 68Q17 06E30 68Q10 68W20 PDFBibTeX XMLCite \textit{E. Grigorescu} et al., Lect. Notes Comput. Sci. 8096, 559--574 (2013; Zbl 1405.68128) Full Text: DOI
Arvind, Vikraman; Köbler, Johannes; Kuhnert, Sebastian; Rattan, Gaurav; Vasudev, Yadu On the isomorphism problem for decision trees and decision lists. (English) Zbl 1368.68218 Gąsieniec, Leszek (ed.) et al., Fundamentals of computation theory. 19th international symposium, FCT 2013, Liverpool, UK, August 19–21, 2013. Proceedings. Berlin: Springer (ISBN 978-3-642-40163-3/pbk). Lecture Notes in Computer Science 8070, 16-27 (2013). MSC: 68Q25 68Q17 05C60 06E30 PDFBibTeX XMLCite \textit{V. Arvind} et al., Lect. Notes Comput. Sci. 8070, 16--27 (2013; Zbl 1368.68218) Full Text: DOI
De, Anindya; Diakonikolas, Ilias; Servedio, Rocco A robust Khintchine inequality, and algorithms for computing optimal constants in Fourier analysis and high-dimensional geometry. (English) Zbl 1336.68261 Fomin, Fedor V. (ed.) et al., Automata, languages, and programming. 40th international colloquium, ICALP 2013, Riga, Latvia, July 8–12, 2013, Proceedings, Part I. Berlin: Springer (ISBN 978-3-642-39205-4/pbk). Lecture Notes in Computer Science 7965, 376-387 (2013). MSC: 68U05 06E30 68Q17 68W25 PDFBibTeX XMLCite \textit{A. De} et al., Lect. Notes Comput. Sci. 7965, 376--387 (2013; Zbl 1336.68261) Full Text: DOI arXiv
Ron, Dana; Rubinfeld, Ronitt; Safra, Muli; Samorodnitsky, Alex; Weinstein, Omri Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity. (English) Zbl 1322.68109 ACM Trans. Comput. Theory 4, No. 4, Article No. 11, 12 p. (2012). MSC: 68Q25 06E30 68Q17 68W20 68W25 PDFBibTeX XMLCite \textit{D. Ron} et al., ACM Trans. Comput. Theory 4, No. 4, Article No. 11, 12 p. (2012; Zbl 1322.68109) Full Text: DOI
Amano, Kazuyuki Bounding the randomized decision tree complexity of read-once Boolean functions. (English) Zbl 1376.68057 Randall, Dana (ed.), Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23–25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1729-1744 (2011). MSC: 68Q25 06E30 68Q17 94D10 PDFBibTeX XMLCite \textit{K. Amano}, in: Proceedings of the 22nd annual ACM-SIAM symposium on discrete algorithms, SODA 2011, San Francisco, CA, USA, January 23--25, 2011. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 1729--1744 (2011; Zbl 1376.68057) Full Text: Link
Ambühl, Christoph; Mastrolilli, Monaldo; Mutsanas, Nikolaus; Svensson, Ola On the approximability of single-machine scheduling with precedence constraints. (English) Zbl 1238.90059 Math. Oper. Res. 36, No. 4, 653-669 (2011). MSC: 90B35 68W25 05C15 06A07 68Q25 PDFBibTeX XMLCite \textit{C. Ambühl} et al., Math. Oper. Res. 36, No. 4, 653--669 (2011; Zbl 1238.90059) Full Text: DOI
Ron, Dana; Rubinfeld, Ronitt; Safra, Muli; Weinstein, Omri Approximating the influence of monotone Boolean functions in \(O(\sqrt{n})\) query complexity. (English) Zbl 1343.68305 Goldberg, Leslie Ann (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 14th international workshop, APPROX 2011, and 15th international workshop, RANDOM 2011, Princeton, NJ, USA, August 17–19, 2011. Proceedings. Berlin: Springer (ISBN 978-3-642-22934-3/pbk). Lecture Notes in Computer Science 6845, 664-675 (2011). MSC: 68W20 06E30 68Q17 68W25 PDFBibTeX XMLCite \textit{D. Ron} et al., Lect. Notes Comput. Sci. 6845, 664--675 (2011; Zbl 1343.68305) Full Text: DOI
Bollig, Beate Larger lower bounds on the OBDD complexity of integer multiplication. (English) Zbl 1217.68111 Inf. Comput. 209, No. 3, 333-343 (2011). MSC: 68Q25 68Q17 06E30 PDFBibTeX XMLCite \textit{B. Bollig}, Inf. Comput. 209, No. 3, 333--343 (2011; Zbl 1217.68111) Full Text: DOI
Laber, Eduardo; Molinaro, Marco An approximation algorithm for binary searching in trees. (English) Zbl 1211.68512 Algorithmica 59, No. 4, 601-620 (2011). MSC: 68W25 05C05 06A07 68R10 PDFBibTeX XMLCite \textit{E. Laber} and \textit{M. Molinaro}, Algorithmica 59, No. 4, 601--620 (2011; Zbl 1211.68512) Full Text: DOI
Matuschke, Jannik; Peis, Britta Lattices and maximum flow algorithms in planar graphs. (English) Zbl 1310.05201 Thilikos, Dimitrios M. (ed.), Graph theoretic concepts in computer science. 36th international workshop, WG 2010, Zarós, Crete, Greece, June 28–30, 2010. Revised papers. Berlin: Springer (ISBN 978-3-642-16925-0/pbk). Lecture Notes in Computer Science 6410, 324-335 (2010). MSC: 05C85 05C10 05C21 06C10 90C59 PDFBibTeX XMLCite \textit{J. Matuschke} and \textit{B. Peis}, Lect. Notes Comput. Sci. 6410, 324--335 (2010; Zbl 1310.05201) Full Text: DOI arXiv
Howard, David; Trenk, Ann N. The \(t\)-discrepancy of a poset. (English) Zbl 1201.06001 Discrete Appl. Math. 158, No. 16, 1789-1798 (2010). MSC: 06A07 68Q17 68W05 PDFBibTeX XMLCite \textit{D. Howard} and \textit{A. N. Trenk}, Discrete Appl. Math. 158, No. 16, 1789--1798 (2010; Zbl 1201.06001) Full Text: DOI
Alon, Noga; Blais, Eric Testing Boolean function isomorphism. (English) Zbl 1305.68327 Serna, Maria (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 13th international workshop, APPROX 2010, and 14th international workshop, RANDOM 2010, Barcelona, Spain, September 1–3, 2010. Proceedings. Berlin: Springer (ISBN 978-3-642-15368-6/pbk). Lecture Notes in Computer Science 6302, 394-405 (2010). MSC: 68W20 06E30 68Q17 94C10 PDFBibTeX XMLCite \textit{N. Alon} and \textit{E. Blais}, Lect. Notes Comput. Sci. 6302, 394--405 (2010; Zbl 1305.68327) Full Text: DOI
Bazzi, Louay M. J. Polylogarithmic independence can fool DNF formulas. (English) Zbl 1188.68156 SIAM J. Comput. 38, No. 6, 2220-2272 (2009). MSC: 68Q25 06A07 60C05 60E15 68W20 94C10 PDFBibTeX XMLCite \textit{L. M. J. Bazzi}, SIAM J. Comput. 38, No. 6, 2220--2272 (2009; Zbl 1188.68156) Full Text: DOI
Kijima, Shuji; Nemoto, Toshio Finding a level ideal of a poset. (English) Zbl 1248.68220 Ngo, Hung Q. (ed.), Computing and combinatorics. 15th annual international conference, COCOON 2009, Niagara Falls, NY, USA, July 13–15, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02881-6/pbk). Lecture Notes in Computer Science 5609, 317-327 (2009). MSC: 68Q17 06A07 68Q25 68W20 68W25 91B68 PDFBibTeX XMLCite \textit{S. Kijima} and \textit{T. Nemoto}, Lect. Notes Comput. Sci. 5609, 317--327 (2009; Zbl 1248.68220) Full Text: DOI
Traxler, Patrick Variable influences in conjunctive normal forms. (English) Zbl 1247.94075 Kullmann, Oliver (ed.), Theory and applications of satisfiability testing – SAT 2009. 12th international conference, SAT 2009, Swansea, UK, June 30–July 3, 2009. Proceedings. Berlin: Springer (ISBN 978-3-642-02776-5/pbk). Lecture Notes in Computer Science 5584, 101-113 (2009). MSC: 94C10 06E30 68Q17 68Q25 PDFBibTeX XMLCite \textit{P. Traxler}, Lect. Notes Comput. Sci. 5584, 101--113 (2009; Zbl 1247.94075) Full Text: DOI
Krokhin, Andrei; Larose, Benoit A note on supermodular sublattices in finite relatively complemented lattices. (English) Zbl 1170.06001 Algebra Univers. 59, No. 1-2, 237-241 (2008). Reviewer: T. Katriňák (Bratislava) MSC: 06B05 06B10 68Q17 68Q25 PDFBibTeX XMLCite \textit{A. Krokhin} and \textit{B. Larose}, Algebra Univers. 59, No. 1--2, 237--241 (2008; Zbl 1170.06001) Full Text: DOI
Dereniowski, Dariusz Edge ranking and searching in partial orders. (English) Zbl 1152.68014 Discrete Appl. Math. 156, No. 13, 2493-2500 (2008). MSC: 68P10 06A06 68Q17 68Q25 68R10 PDFBibTeX XMLCite \textit{D. Dereniowski}, Discrete Appl. Math. 156, No. 13, 2493--2500 (2008; Zbl 1152.68014) Full Text: DOI
Khachiyan, Leonid; Boros, Endre; Elbassioni, Khaled; Gurvich, Vladimir Generating all minimal integral solutions to AND-OR systems of monotone inequalities: Conjunctions are simpler than disjunctions. (English) Zbl 1160.68018 Discrete Appl. Math. 156, No. 11, 2020-2034 (2008). MSC: 68Q25 05B35 06E30 05C65 68Q17 PDFBibTeX XMLCite \textit{L. Khachiyan} et al., Discrete Appl. Math. 156, No. 11, 2020--2034 (2008; Zbl 1160.68018) Full Text: DOI
Moonen, Linda S.; Spieksma, Frits C. R. Partitioning a weighted partial order. (English) Zbl 1136.06003 J. Comb. Optim. 15, No. 4, 342-356 (2008). MSC: 06A07 68Q17 90C27 90C59 PDFBibTeX XMLCite \textit{L. S. Moonen} and \textit{F. C. R. Spieksma}, J. Comb. Optim. 15, No. 4, 342--356 (2008; Zbl 1136.06003) Full Text: DOI Link
Kosub, Sven Dichotomy results for fixed-point existence problems for Boolean dynamical systems. (English) Zbl 1138.68034 Math. Comput. Sci. 1, No. 3, 487-505 (2008). MSC: 68Q17 68Q25 68R10 05C83 06E30 37B15 68Q80 68Q85 PDFBibTeX XMLCite \textit{S. Kosub}, Math. Comput. Sci. 1, No. 3, 487--505 (2008; Zbl 1138.68034) Full Text: DOI
Vinterbo, Staal A. A stab at approximating minimum subadditive join. (English) Zbl 1209.68654 Dehne, Frank (ed.) et al., Algorithms and data structures. 10th international workshop, WADS 2007, Halifax, Canada, August 15–17, 2007. Proceedings. Berlin: Springer (ISBN 978-3-540-73948-7/pbk). Lecture Notes in Computer Science 4619, 214-225 (2007). MSC: 68W25 05C70 06A12 PDFBibTeX XMLCite \textit{S. A. Vinterbo}, Lect. Notes Comput. Sci. 4619, 214--225 (2007; Zbl 1209.68654) Full Text: DOI
Herlihy, Brian; Schachte, Peter; Søndergaard, Harald Un-Kleene Boolean equation solving. (English) Zbl 1119.68049 Int. J. Found. Comput. Sci. 18, No. 2, 227-250 (2007). MSC: 68N30 68W25 06E30 PDFBibTeX XMLCite \textit{B. Herlihy} et al., Int. J. Found. Comput. Sci. 18, No. 2, 227--250 (2007; Zbl 1119.68049) Full Text: DOI
Berman, Piotr; Dasgupta, Bhaskar; Mubayi, Dhruv; Sloan, Robert; Turán, György; Zhang, Yi The inverse protein folding problem on 2D and 3D lattices. (English) Zbl 1113.92024 Discrete Appl. Math. 155, No. 6-7, 719-732 (2007). MSC: 92C40 68Q25 68R10 05C90 06B99 PDFBibTeX XMLCite \textit{P. Berman} et al., Discrete Appl. Math. 155, No. 6--7, 719--732 (2007; Zbl 1113.92024) Full Text: DOI
Broniek, Przemyslaw On-line chain partitioning as a model for real-time scheduling. (English) Zbl 1272.06005 Lescanne, Pierre (ed.) et al., Proceedings of the 2nd workshop on computational logic and applications (CLA 2004), Lyon, France, June 17–18, 2004. Amsterdam: Elsevier. Electronic Notes in Theoretical Computer Science 140, 15-29 (2005). MSC: 06A07 68M20 68Q17 68W27 PDFBibTeX XMLCite \textit{P. Broniek}, Electron. Notes Theor. Comput. Sci. 140, 15--29 (2005; Zbl 1272.06005) Full Text: Link
Bulatov, A. A. The complexity of the conservative generalized satisfiability problem. (English. Russian original) Zbl 1378.68065 Dokl. Math. 70, No. 1, 597-598 (2004); translation from Dokl. Akad. Nauk 397, No. 5, 583-585 (2004). MSC: 68Q25 06E30 68Q17 PDFBibTeX XMLCite \textit{A. A. Bulatov}, Dokl. Math. 70, No. 1, 597--598 (2004; Zbl 1378.68065); translation from Dokl. Akad. Nauk 397, No. 5, 583--585 (2004)
Achlioptas, Dimitris; Peres, Yuval The threshold for random \(k\)-SAT is \(2^k\log 2-O(k)\). (English) Zbl 1093.68075 J. Am. Math. Soc. 17, No. 4, 947-973 (2004). MSC: 68R99 05C80 06E30 68Q17 68Q25 68T20 PDFBibTeX XMLCite \textit{D. Achlioptas} and \textit{Y. Peres}, J. Am. Math. Soc. 17, No. 4, 947--973 (2004; Zbl 1093.68075) Full Text: DOI arXiv
Carmo, R.; Donadelli, J.; Kohayakawa, Y.; Laber, E. Searching in random partially ordered sets. (English) Zbl 1068.68050 Theor. Comput. Sci. 321, No. 1, 41-57 (2004). MSC: 68P10 05C80 06A06 68W25 PDFBibTeX XMLCite \textit{R. Carmo} et al., Theor. Comput. Sci. 321, No. 1, 41--57 (2004; Zbl 1068.68050) Full Text: DOI
Ceroi, Stéphan A weighted version of the jump number problem on two-dimensional orders is NP-complete. (English) Zbl 1027.06002 Order 20, No. 1, 1-11 (2003). MSC: 06A06 11Y16 68Q17 PDFBibTeX XMLCite \textit{S. Ceroi}, Order 20, No. 1, 1--11 (2003; Zbl 1027.06002) Full Text: DOI
Fischer, Eldar; Lehman, Eric; Newman, Ilan; Raskhodnikova, Sofya; Rubinfeld, Ronitt; Samorodnitsky, Alex Monotonicity testing over general poset domains. (English) Zbl 1192.68359 Proceedings of the thirty-fourth annual ACM symposium on theory of computing (STOC 2002), Montreal, Quebec, Canada, May 19–21, 2002. New York, NY: ACM Press (ISBN 1-581-13495-9). 474-483, electronic only (2002). MSC: 68Q25 05C85 06E30 68Q17 68W20 PDFBibTeX XMLCite \textit{E. Fischer} et al., in: Proceedings of the thirty-fourth annual ACM symposium on theory of computing, STOC 2002. Montreal, Quebec, Canada, May 19--21, 2002. New York, NY: ACM Press. 474--483 (2002; Zbl 1192.68359) Full Text: DOI
Tonoyan, G. P. Complexity estimations of satisfiability of systems of Boolean equations of special classes. (English) Zbl 1029.06009 Algebra, geometry and their applications. Seminar proceedings, Yerevan State University, Yerevan, Armenia. Vol. 2, 2002. Yerevan: Yerevan State University Press. 19-25 (2002). MSC: 06E30 68Q17 68Q25 PDFBibTeX XMLCite \textit{G. P. Tonoyan}, in: Algebra, geometry and their applications. Seminar proceedings, Yerevan State University, Yerevan, Armenia. Vol. 2, 2002. Yerevan: Yerevan State University Press. 19--25 (2002; Zbl 1029.06009)
Kuznetsov, Sergei O. On computing the size of a lattice and related decision problems. (English) Zbl 0991.06006 Order 18, No. 4, 313-321 (2001). Reviewer: Václav Koubek (Praha) MSC: 06B99 68Q25 68Q17 06A15 PDFBibTeX XMLCite \textit{S. O. Kuznetsov}, Order 18, No. 4, 313--321 (2001; Zbl 0991.06006) Full Text: DOI
Habib, Michel; Möhring, Rolf H. Treewidth of cocomparability graphs and a new order-theoretic parameter. (English) Zbl 0811.06001 Order 11, No. 1, 47-60 (1994). Reviewer: H.Müller (Jena) MSC: 06A06 05C85 68Q25 68R10 PDFBibTeX XMLCite \textit{M. Habib} and \textit{R. H. Möhring}, Order 11, No. 1, 47--60 (1994; Zbl 0811.06001) Full Text: DOI
Kannan, Sampath; Warnow, Tandy Tree reconstruction from partial orders. (English) Zbl 1504.68169 Dehne, Frank (ed.) et al., Algorithms and data structures. 3rd workshop, WADS ’93. Montréal, Canada 11–13, 1993. Proceedings. Berlin: Springer-Verlag. Lect. Notes Comput. Sci. 709, 397-408 (1993). MSC: 68R10 05C05 06A07 68Q17 68Q25 92D15 PDFBibTeX XMLCite \textit{S. Kannan} and \textit{T. Warnow}, Lect. Notes Comput. Sci. 709, 397--408 (1993; Zbl 1504.68169) Full Text: DOI
Mitas, Jutta Tackling the jump number of interval orders. (English) Zbl 0737.06003 Order 8, No. 2, 115-132 (1991). MSC: 06A07 68Q25 05C70 05C85 68R10 PDFBibTeX XMLCite \textit{J. Mitas}, Order 8, No. 2, 115--132 (1991; Zbl 0737.06003) Full Text: DOI
Paoluzzi, A.; Ramella, M.; Santarelli, A. Boolean algebra over linear polyhedra. (English) Zbl 0686.65009 Comput.-Aided Des. 21, No. 8, 474-484 (1989). Reviewer: N.Ţăndăreanu MSC: 65D15 06E15 PDFBibTeX XMLCite \textit{A. Paoluzzi} et al., Comput.-Aided Des. 21, No. 8, 474--484 (1989; Zbl 0686.65009) Full Text: DOI
Zimmermann, Karel Some optimization problems with extremal operations. (English) Zbl 0558.90102 Math. Program. Study 22, 237-251 (1984). Reviewer: U.Zimmermann MSC: 90C48 06F15 41A65 41A50 PDFBibTeX XMLCite \textit{K. Zimmermann}, Math. Program. Study 22, 237--251 (1984; Zbl 0558.90102) Full Text: DOI
Michaud, Pierre; Marcotorchino, Francois Modeles d’optimisation en analyse des données rélationnelles. (French) Zbl 0446.62058 Math. Sci. Hum. 67, 7-38 (1979). MSC: 62H30 65C99 65D15 05C35 06-04 PDFBibTeX XMLCite \textit{P. Michaud} and \textit{F. Marcotorchino}, Math. Sci. Hum. 67, 7--38 (1979; Zbl 0446.62058) Full Text: Numdam EuDML