VU Duomenų mokslo ir skaitmeninių technologijų instituto / Matematikos ir informatikos instituto autoriaus (-ių) 'stasys jukna' publikacijų sąrašas (pagal Lietuvos akademinių bibliotekų tinklo (LABT) publikacijų bazes VUB [nuo 2011 m. iki dabar] ir LMAVB [iki 2010 m. imtinai]):
Publications of 'stasys jukna', VU Institute of Data Science and Digital Technologies / Institute of Mathematics and Informatics (based on 1. Lithuanian Academic Library Network (LABT) database of Vilnius University Library [since 2011 until now] and 2. LABT database of Wroblewski Library of the Lithuanian Academy of Sciences [until 2010]):
Eil. Nr. Publikacija
1Jukna, Stasys. Tropical circuit complexity: limits of pure dynamic programming. Cham : Springer Nature, 2023. 129 p. (SpringerBriefs in Mathematics, ISSN 2191-8198, eISSN 2191-8201). ISBN 9783031423536. eISBN 9783031423543. DOI: 10.1007/978-3-031-42354-3.
2Jukna, Stasys; Lingas, Andrzej. Lower bounds for Boolean circuits of bounded negation // Journal of computer and system sciences. San Diego, CA : Academic Press Inc Elsevier Science. ISSN 0022-0000. eISSN 1090-2724. 2022, vol. 129, p. 90-105. DOI: 10.1016/j.jcss.2022.05.003.
3Jukna, Stasys. Notes on hazard-free circuits // SIAM journal on discrete mathematics. Philadelphia : SIAM publications. ISSN 0895-4801. eISSN 1095-7146. 2021, vol. 35, iss. 2, p. 770-787. DOI: 10.1137/20M1355240.
4Jukna, Stasys; Seiwert, Hannes. Tropical Kirchhoff’s formula and postoptimality in matroid optimization // Discrete applied mathematics. Amsterdam : Elsevier. ISSN 0166-218X. eISSN 1872-6771. 2021, vol. 289, p. 12-21. DOI: 10.1016/j.dam.2020.09.018.
5Jukna, Stasys. Coin flipping in dynamic programming is almost useless // ACM Transactions on Computation Theory. New York : ACM. ISSN 1942-3454. eISSN 1942-3462. 2020, vol. 12, no. 3, art. no. 17, p. 1-26. DOI: 10.1145/3397476.
6Jukna, Stasys; Seiwert, Hannes. Approximation limitations of pure dynamic programming // SIAM journal on computing. Philadelphia : SIAM publishing. ISSN 0097-5397. eISSN 1095-7111. 2020, vol. 49, no. 1, p. 170-205. DOI: 10.1137/18M1196339.
7Jukna, Stasys; Seiwert, Hannes. Sorting can exponentially speed up pure dynamic programming // Information processing letters. Amsterdam : Elsevier. ISSN 0020-0190. eISSN 1872-6119. 2020, vol. 159-160, art. no. 105962, p. [1-4]. DOI: 10.1016/j.ipl.2020.105962.
8Jukna, Stasys; Lingas, Andrej. Lower bounds for DeMorgan circuits of bounded negation width // 36th International symposium on theoretical aspects of computer science (STACS 2019), March 13-16, 2019, Berlin, Germany / Editors: Rolf Niedermeier and Christophe Paul. Wadern : Leibniz-Zentrum für Informatik, Dagstuhl Publishing, 2019, art. no. 41. ISBN 9783959771009. p. [1-17]. (LIPICS, ISSN 1868-8969 ; 126). DOI: 10.4230/LIPIcs.STACS.2019.41.
9Jukna, Stasys. Coin flipping cannot shorten arithmetic computations // American mathematical monthly. Philadelphia : Taylor & Francis. ISSN 0002-9890. eISSN 1930-0972. 2019, vol. 126, iss. 4, p. 364-366. DOI: 10.1080/00029890.2019.1565883.
10Jukna, Stasys; Seiwert, Hannes. Greedy can beat pure dynamic programming // Information processing letters. Amsterdam : Elsevier Science BV. ISSN 0020-0190. eISSN 1872-6119. 2019, vol. 142, p. 90-95. DOI: 10.1016/j.ipl.2018.10.018.
11Jukna, Stasys. Incremental versus non-incremental dynamic programming // Operations research letters. Amsterdam : Elsevier Science BV. ISSN 0167-6377. eISSN 1872-7468. 2018, vol. 46, iss. 3, p. 278-281. DOI: 10.1016/j.orl.2018.02.003.
12Jukna, Stasys. Minkowski complexity of sets: an easy lower bound // American mathematical monthly. Washington : Mathematical association of America. ISSN 0002-9890. eISSN 1930-0972. 2017, Vol. 124, no 8, p. 749-753. DOI: 10.4169/amer.math.monthly.124.8.749.
13Jukna, Stasys. Tropical complexity, sidon sets, and dynamic programming // SIAM journal on discrete mathematics. Philadelphia : Society for Industrial and Applied Mathematics. ISSN 0895-4801. eISSN 1095-7146. 2016, Vol. 30, No. 4, p. 2064-2085. DOI: 10.1137/16M1064738.
14Jukna, Stasys. Lower bounds for monotone counting circuits // Discrete applied mathematics. Amsterdam : Elsevier. ISSN 0166-218X. eISSN 1872-6771. 2016, Vol. 213, p. 139-152. DOI: 10.1016/j.dam.2016.04.024.
15Jukna, Stasys; Schnitger, Georg. On the optimality of Bellman-Ford-Moore shortest path algorithm // Theoretical Computer Science. Amsterdam : Elsevier BV. ISSN 0304-3975. 2016, Vol. 628, p. 101-109. DOI: 10.1016/j.tcs.2016.03.014.
16Jukna, Stasys. Lower bounds for tropical circuits and dynamic programs // Theory of computing systems. New York : Springer New York LLC. ISSN 1432-4350. 2015, Vol. 57, no 1, p. 160-194. DOI: 10.1007/s00224-014-9574-4.
17Jukna, Stasys. Limitations of incremental dynamic programming // Algorithmica. New York : Springer New York LLC. ISSN 0178-4617. 2014, vol. 69, no 2, p. 461-492. DOI: 10.1007/s00453-013-9747-6.
18Jukna, Stasys; Sergeev, Igor. Complexity of linear boolean operators. Boston - Delft : Now Publishers Inc., 2013. 123 p. ISBN 9781601987266. DOI: 10.1561/0400000063.
19Jukna, Stasys. Computational complexity of graphs // Advances in network complexity / Editors: Matthias Dehmer, Abbe Mowshowitz, Frank Emmert-Streib. Hoboken : Wiley-Blackwell, 2013. ISBN 9783527332915. p. 99-153. Prieiga per internetą: <http://www.thi.informatik.uni-frankfurt.de/~jukna/ftp/graph-compl.pdf>.
20Jukna, Stasys. Clique problem, cutting plane proofs and communication complexity // Information processing letters. Amsterdam : Elsevier B.V. ISSN 0020-0190. 2012, Vol. 112, iss. 20, p. 772-777. DOI: 10.1016/j.ipl.2012.07.003.
21Jukna, Stasys; Schnitger, Georg. Cutting planes cannot approximate some integer programs // Operations research letters. Amsterdam : Elsevier BV. ISSN 0167-6377. 2012, vol. 40, no 4, p. 272-275. DOI: 10.1016/j.orl.2012.03.008.
22Jukna, Stasys. Boolean Function Complexity : Advances and Frontiers. Heidelberg : Springer, 2012. 632 p. ISBN 9783642245077. DOI: 10.1007/978-3-642-24508-4.
23Jukna, Stasys. Extremal combinatorics : with applications in computer science. Second edition. Berlin : Springer, 2011. XXIII, 411p. ISBN 9783642173639. DOI: 10.1007/978-3-642-17364-6.
24Jukna, Stasys; Schnitger, Georg. Min-rank conjecture for log-depth circuits // Journal of computer and system sciences. Maryland Heights : Academic Press. ISSN 0022-0000. 2011, vol. 77, iss. 6, p. 1023-1038. DOI: 10.1016/j.jcss.2009.09.003.
25Jukna, Stasys; Schnitger, Georg. Yet harder knapsack problems // Theoretical computer science. Amsterdam : Elsevier BV. ISSN 0304-3975. 2011, vol. 412, iss. 45, p. 6351-6358. DOI: 10.1016/j.tcs.2011.07.003.
26Hrubeš, Pavel; Jukna, Stasys; Kulikov, Alexander; Pudlák, Pavel. On convex complexity measures // Theoretical computer science. ISSN 0304-3975. 2010, Vol. 411, iss. 16-18, p. 1842-1854. DOI: 10.1016/j.tcs.2010.02.004.
27Jukna, Stasys. Entropy of operators or why matrix multiplication is hard for depth-two circuits // Theory of computing systems. ISSN 1432-4350. 2010, Vol. 46, no. 2, p. 301-310. DOI: 10.1007/s00224-008-9133-y.
28Jukna, Stasys. Representing (0, 1)-matrices by boolean circuits // Discrete mathematics. ISSN 0012-365X. 2010, Vol. 310, iss. 1, p. 184-187. DOI: 10.1016/j.disc.2009.07.011.
29Jukna, Stasys. A nondeterministic space-time tradeoff for linear codes // Information processing letters. ISSN 0020-0190. 2009, Vol. 109, iss. 5, p. 286-289. DOI: 10.1016/j.ipl.2008.11.001.
30Jukna, Stasys; Kulikov, A.S. On covering graphs by complete bipartite subgraphs // Discrete mathematics. ISSN 0012-365X. 2009, Vol. 309, iss. 10, p. 3399-3403. DOI: 10.1016/j.disc.2008.09.036.
31Jukna, Stasys. On set intersection representations of graphs // Journal of graph theory. ISSN 0364-9024. 2009, Vol. 61, iss. 1, p. 55-75. DOI: 10.1002/jgt.20367.
32Jukna, Stasys. Linear codes are hard for oblivious read-once parity branching programs // Information processing letters. ISSN 0020-0190. 1999, Vol. 69, iss. 6, p. 267-269. DOI: 10.1016/S0020-0190(99)00027-7.
33Jukna, Stasys; Schnitger, Georg. Triangle-freeness is hard to detect // Combinatorics, probability and computing. ISSN 0963-5483. 2002, Vol. 11, iss. 6, p. 549-569. DOI: 10.1017/S0963548302005333.
34Jukna, Stasys; Razborov, Alexander. Neither reading few bits twice nor reading illegally helps much // Discrete applied mathematics. ISSN 0166-218X. 1998, Vol. 85, iss. 3, p. 223-238. DOI: 10.1016/S0166-218X(98)00042-0.
35Jukna, Stasys. Combinatorics of monotone computations // Combinatorica. ISSN 0209-9683. 1999, Vol. 19, no. 1, p. 65-85. DOI: 10.1007/s004930050046.
36Damm, Carsten; Jukna, Stasys; Sgall, Jirí. Some bounds on multiparty communication complexity of pointer jumping // Computational complexity. ISSN 1016-3328. 1998, Vol. 7, Iss. 2, p. 109-127. DOI: 10.1007/PL00001595.
37Håstad, Johan; Jukna, Stasys; Pudlák, Pavel. Top-down lower bounds for depth-three circuits // Computational complexity. ISSN 1016-3328. 1995, Vol. 5, Iss. 2, p. 99-112. DOI: 10.1007/BF01268140.
38Jukna, Stasys. Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates // Information processing letters. ISSN 0020-0190. 1995, Vol. 56, iss. 3, p. 147-150. DOI: 10.1016/0020-0190(95)00137-2.
39Jukna, Stasys. Entropy of contact circuits and lower bounds on their complexity // Theoretical computer science. ISSN 0304-3975. 1988, Vol. 57, iss. 1, p. 113-129. DOI: 10.1016/0304-3975(88)90166-1.
40Jukna, Stasys. Expanders and time-restricted branching programs // Theoretical Computer Science. ISSN 0304-3975. 2008, Vol. 409, iss. 3, p. 471-476. DOI: 10.1016/j.tcs.2008.09.012.
41Andreev, Alexander E.; Jukna, Stasys. Very large cliques are easy to detect // Discrete mathematics. ISSN 0012-365X. 2008, Vol. 308, iss. 16, p. 3717-3721. DOI: 10.1016/j.disc.2007.07.036.
42Jukna, Stasys; Žák, Stanislav. On uncertainty versus size in branching programs // Theoretical computer science. ISSN 0304-3975. 2003, Vol. 290, iss. 3, p. 1851-1867. DOI: 10.1016/S0304-3975(02)00323-7.
43Jukna, Stasys. Extremal combinatorics : with applications in computer science / Stasys Jukna. Berlin [etc.] : Springer, 2001. 375 p. ISBN 3540663134.
44Jukna, Stasys. Crashkurs Mathematik für Informatiker / Stasys Jukna. Wiesbaden : Teubner, 2008. 315 p. ISBN 9783835102163. DOI: 10.1007/978-3-8351-9214-0.
45Jukna, Stasys. Disproving the single level conjecture // SIAM journal on computing. ISSN 0097-5397. 2006, Vol. 36, Iss. 1, p. 83-98. DOI: 10.1137/S0097539705447001.
46Jukna, Stasys. On graph complexity // Combinatorics, probability and computing. ISSN 0963-5483. 2006, Vol. 15, Iss. 6, p. 855-876. DOI: 10.1017/S0963548306007620.
47Jukna, Stasys. Disproving the single level conjecture // Electronic colloquium on computational complexity. Reports [Elektroninis išteklius]. ISSN 1433-8092. 2005, TR05-021, p. 1-17. Prieiga per internetą: <http://eccc.hpi-web.de/eccc-reports/2005/TR05-021/index.html>.
48Jukna, Stasys. Expanders and time-restricted branching programs // Electronic colloquium on computational complexity. Reports [Elektroninis išteklius]. ISSN 1433-8092. 2005, TR05-079, p. 1-9. Prieiga per internetą: <http://eccc.hpi-web.de/eccc-reports/2005/TR05-079/index.html>.
49Jukna, Stasys. On the P versus NP intersected with co-NP question in communication complexity // Information processing letters. ISSN 0020-0190. 2005, Vol. 96, iss. 6, p. 202-206. DOI: 10.1016/j.ipl.2005.08.003.
50Jukna, Stasys; Razborov, Alexander; Savicky, Peter; Wegener, Ingo. On P versus NP boolean AND co-NP for decision trees and read-once branching programs // Computational complexity. ISSN 1016-3328. 1999, Vol. 8, iss. 4, p. 357-370. DOI: 10.1007/s000370050005.
51Ďuriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg. On multi-partition communication complexity // Information and computation. ISSN 0890-5401. 2004, Vol. 194, Iss. 1, p. 49-75. DOI: 10.1016/j.ic.2004.05.002.
52Jukna, Stasys. On the minimum number of negations leading to super-polynomial savings // Information processing letters. ISSN 0020-0190. 2004, Vol. 89, iss. 2, p. 71-74. DOI: 10.1016/j.ipl.2003.10.003.