Stasys Jukna: Online manuscripts of my papers

List at Google scholar
List at DBLP. Schloss Dagstuhl. Bibliography run by Michael Ley.

Copyright Notice © Please note that some of the publications are subject to copyright restrictions but you are free to use such publications for personal research or education purposes. For papers that have already been published, the versions available here are, as a rule, those of the earlier preprints, and may not contain corrections made in the editing process.

Notes on Boolean read-k and multilinear circuits [Abstract HTML] [pdf]
Submitted to: Discrete Appl. Math.
Lower bounds for circuits of bounded negation width [Abstract HTML] [pdf]
Joint with Andrzej Lingas
Journal of Comput. Syst. Sci., 129 (2022) 90-105. ©Elsevier
doi: 10.1016/j.jcss.2022.05.003
Notes on hazard-free circuits [Abstract HTML] [pdf]
SIAM J. on Discrete Math., 35:2 (2021) 770-787 © SIAM
doi: 10.1137/20M1355240
Preprint: ECCC Report Nr. 102, 2020.
Tropical Kirchhoff's formula and postoptimality in matroid optimization [Abstract (HTML)] [pdf]
Joint with Hannes Seiwert
Discrete Appl. Math. 289:31 (2021) 12-21 © Elsevier
doi: /10.1016/j.dam.2020.09.018
Reciprocal inputs in arithmetic and tropical circuits [Abstract (HTML)] [pdf]
Joint with Hannes Seiwert and Igor Sergeev
Preprint: ECCC Report Nr. 170 2020.
A supplementary note (proof for example in Fig. 2) [pdf]
Approximation limitations of pure dynamic programming [Abstract (HTML)] [pdf]
Joint with Hannes Seiwert
SIAM J. on Computing 49:1 (2020) 170-207 © SIAM
doi: 18M1196339
Preprint: ECCC Report Nr. 127 2018 (under the title "Approximation limitations of tropical circuits").
Coin flipping in dynamic programming is almost useless [Abstract (HTML)] [pdf]
ACM Trans. on Computation Theory (2020) 26 pages, Article 17 © ACM
doi: 10.1145/3397476
Preprint:ECCC Report Nr. 51 2018.
Sorting can exponentially speed up pure dynamic programming [Abstract (HTML)] [pdf]
Joint with Hannes Seiwert
Information Processing Letters 159-160 (2020), article Nr. 105962 © Elsevier
doi: 10.1016/j.ipl.2020.105962
Preprint: ECCC Report Nr. 158 2019.
Coin flipping cannot shorten arithmetic computations [Abstract (HTML)] [pdf]
Amer. Math. Monthly 126:4 (2019) 364-366 ©2019 MAA
doi: 10.1080/00029890.2019.1565883
Greedy can beat pure dynamic programming [Abstract (HTML)] [pdf]
Joint with Hannes Seiwert
Information Processing Letters 142 (2019) 90-95 © Elsevier
doi: 10.1016/j.ipl.2018.10.018
Preprint: ECCC Report Nr. 49 2018.
Incremental versus non-incremental dynamic programming [Abstract (HTML)] [pdf]
Operations Research Letters 46:3 (2018), 278-281. © Elsevier
doi: 10.1016/j.orl.2018.02.003
Preprint: ECCC Report Nr. 42 2018
(Min, Plus) is not stronger than (Or, And)
Comment 1 to ECCC Report Nr. 20 2018.
Minkowski complexity of sets: an easy lower bound [pdf] [Abstract (HTML)]
Amer. Math. Monthly 124:8 (2017) 749-753 © 2017 MAA
Tropical complexity, Sidon sets, and dynamic programming [pdf] [Abstract (HTML)]
SIAM J. on Discrete Math. 30:4 (2016) 2064-2085 © SIAM
doi: 10.1137/16M1064738
Preprint: ECCC Report Nr. 123, 2016
On the optimality of Bellman-Ford-Moore shortest path algorithm [pdf] [Abstract (HTML)]
Joint with Georg Schnitger
Theoretical Computer Science 628 (2016) 101-109 © Elsevier
doi:10.1016/j.tcs.2016.03.014
Preprint: ECCC TR Nr. 127, 2015
Lower bounds for monotone counting circuits [pdf] [Abstract (HTML)]
Discrete Applied Mathematics 213 (2016) 139-152 © Elsevier
doi:10.1016/j.dam.2016.04.024
Preprint: ECCC TR Nr. 169, 2014
Lower bounds for tropical circuits and dynamic programs [pdf] [Abstract (HTML)]
Theory of Computing Systems 57:1 (2015), 160-194 © Springer Verlag
doi: 10.1007/s00224-014-9574-4
Preprint: ECCC Report Nr. 80, 2014
Limitations of incremental dynamic programming [pdf] [Abstract (HTML)]
Algorithmica, 69(2) (2014) 461-492 © Springer Verlag
doi: 10.1007/s00453-013-9747-6
Preprint: ECCC Report Nr. 41
Complexity of linear boolean operators [pdf] [Abstract (HTML)]
Joint with Igor Sergeev
Foundations and Trends in Theoretical Computer Science, Vol. 9, No. 1 (2013) 1-123. © S. Jukna and I. Sergeev
doi: 10.1561/0400000063
Clique problem, cutting plane proofs and communication complexity [pdf] [Abstract (HTML)]
Information Processing Letters 112(20) (2012) 772-777 © Elsevier
doi: 10.1016/j.ipl.2012.07.003
Preprint: ECCC Report Nr. 39, 2012
Cutting planes cannot approximate some integer programs [pdf] [Abstract (HTML)]
Joint with Georg Schnitger
Operations Research Letters 40(4) (2012) 272-275 © Elsevier
doi: 10.1016/j.orl.2012.03.008
Yet harder knapsack problems [pdf] [Abstract (HTML)]
Joint with Georg Schnitger
Theoretical Computer Science 412 (2011), 6351-6358. ©Elsevier
doi: 10.1016/j.tcs.2011.07.003
Min-rank conjecture for log-depth circuits [pdf] [Abstract (HTML)]
Joint with Georg Schnitger
Journal of Comput. Syst. Sci. 77:6 (2011), 1023-1038. © Elsevier
doi: 10.1016/j.jcss.2009.09.003
Preprint: ECCC Report Nr. 8, 2009
On convex complexity measures [pdf] [Abstract (HTML)]
Joint with Pavel Hrubes, Alexander Kulikov and Pavel Pudlák
Theoretical Computer Science, vol. 411 (2010), pp. 1842-1854. ©Elsevier
doi: 10.1016/j.tcs.2010.02.004
Preprint: ECCC Report Nr. 40, 2009
Circuits with arbitrary gates for random operators [pdf] [Abstract (HTML)]
Joint with Georg Schnitger
arXiv:1004.5236v1
Representing (0,1)-matrices by depth-2 circuits with arbitrary gates [pdf] [Abstract (HTML)]
Discrete Mathematics 310 (2010) 184-187. © Elsevier
doi: 10.1016/j.disc.2009.07.011
Entropy of operators or why matrix multiplication is hard for depth-two circuits [pdf] [Abstract (HTML)]
[ Dagstuhl seminar slides (pdf)]
Theory of Computing Systems 46(2) (2010) 301-310. ; Springer Verlag
doi:10.1007/s00224-008-9133-y
A nondeterministic space-time tradeoff for linear codes [pdf] [Abstract (HTML)]
Information Processing Letters 109(5) (2009) 286-289 © Elsevier
doi:10.1016/j.ipl.2008.11.001
On covering graphs by complete bipartite subgraphs [pdf] [Abstract (HTML)]
joint with Alexander Kulikov
Discrete Mathematics 309(10) (2009) 3399-3403. © Elsevier
doi:10.1016/j.disc.2008.09.036
On set intersection representations of graphs [pdf] [Abstract (HTML)]
Journal of Graph Theory 61(1) (2009) 55-75 © John Wiley & Sons
doi:10.1002/jgt.20367
Very large cliques are easy to detect [pdf] [Abstract (HTML)]
joint with Alexander Andreev
Discrete Mathematics 308(16) (2008), 3717-3721, © Elsevier
doi: 10.1016/j.disc.2007.07.036
Expanders and time-restricted branching programs [pdf] [Abstract (HTML)]
Theoretical Computer Science 409 (3) (2008) 471-476 © Elsevier
doi: 10.1016/j.tcs.2008.09.012
Disproving the single level conjecture [pdf] [Abstract (HTML)]
SIAM J. Comput. 36(1) (2006) 83-98 © SIAM
[ Dagstuhl seminar slides (pdf)]
doi: 10.1137/S0097539705447001
Preprint: ECCC Report Nr. 21, 2005
Graphs and circuits: some further remarks [pdf]
Dagstuhl Seminar Proceedings, vol. 06111 (2006), 16 pp.
http://drops.dagstuhl.de/opus/volltexte/2006/621/
On graph complexity [pdf]
Combinatorics, Probability & Computing 15 (2006) 855-876 © Cambridge University Press
Slides of a talk on a local seminar
doi:10.1017/S0963548306007620
Preprint: ECCC Report Nr. 5, 2004
On the P versus NP intersected with co-NP question in communication complexity [pdf] [Abstract (HTML)]
Information Processing Letters 96(6) (2005) 202-206 © Elsevier
doi: 10.1016/j.ipl.2005.08.003
Preprint: ECCC Report Nr. 62, 2004
On the minimum number of negations leading to super-polynomial savings [pdf] [Abstract (HTML)]
Information Processing Letters 89:2, (2004) 71-74 © Elsevier
10.1016/j.ipl.2003.10.003
Preprint: ECCC Report Nr. 58, 2001
On uncertainty versus size in branching programs [pdf]
joint with S. Žák
Theoretical Computer Science 290:3 (2003), 1851-1867. © Elsevier
doi: 10.1016/S0304-3975(02)00323-7
Conference version in: Proc. of ICALP'98, Springer LNCS 1443 (1998) 259-270.
Here is a nice application of our method.
On multi-partition communication complexity [pdf]
joint with P. Ďuriš, J. Hromkovič, M. Sauerhoff and G. Schnitger
Information and Computation, 194:1 (2004), 49-75 © Elsevier
doi: 10.1016/j.ic.2004.05.002
Triangle-freeness is hard to detect [pdf] [Abstract (HTML)]
joint with Georg Schnitger
Combinatorics, Probability & Computing 11:6 (2002), 549-569. © Cambridge University Press
See also a Comment
Some notes on the information flow in read-once branching programs [pdf]
joint with S. Žák
Proc. of 27th Ann. Conf. on Current Trends in Theory and Practice of Informatics , Springer Lect. Notes in Comput. Sci., vol. 1963 (2000), 356-364. © Springer Verlag
Linear codes are hard for oblivious read-once parity branching programs [pdf]
Information Processing Letters, 69 (1999), 267-269 © Elsevier
doi: 10.1016/S0020-0190(99)00027-7
On P versus NP intersected with co-NP for decision trees and read-once branching programs [pdf]
joint with A. Razborov, P. Savicky and I. Wegener,
Computational Complexity 8:4 (1999), pp. 357-370 © Birkhäuser Verlag
doi: 10.1007/s000370050005
Exponential lower bounds on the size of clause based semantic derivations, Manuscript, 1996. [pdf]
A version of it "Exponential lower bounds for semantic resolution"
appeared in: Feasible Arithmetics and Length of Proofs P. Beame and S. Buss, Eds.,
DIMACS Series in Discrete Mathematics and Theoretical Comput. Sci., vol. 39 (1998), pp. 163-172. © AMS
Combinatorics of monotone computations [pdf] Abstract (HTML)]
Combinatorica, 19(1) (1999), pp. 65-85 © Springer Verlag
Preliminary version "Finite Limits and Monotone Computations" appeared as ECCC Report Nr. 26, 1996
In the boolean case the lower bounds criterion is particularly simple: see an excerpt from my book.
Finite limits and monotone computations: the lower bounds criterion [pdf] [Abstract (HTML)]
In: Balcazar, Jose (ed.) : Proc. 12-th Ann. IEEE Conf. on Comput. Complexity. IEEE Computer Society, 1997, pp. 223-238. - ISBN 0-8186-7907-7
Neither reading few bits twice nor reading illegally helps much [pdf]
joint with A. Razborov
Discrete Applied Mathematics, 85:3 (1998), 223-238 ©Elsevier
doi: 10.1016/S0166-218X(98)00042-0
Some bounds on multiparty communication complexity of pointer jumping [pdf]
joint with C. Damm and J. Sgall
Computational Complexity, 7:2 (1998), pp. 109-127 © Birkhäuser Verlag
doi: 10.1007/PL00001595
Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates [pdf] [Abstract (HTML)]
Information Processing Letters, 56 (1995), 147-150 © Elsevier
doi: 10.1016/0020-0190(95)00137-2
A note on read-k times branching programs [pdf]
RAIRO Theoret. Informatics and Appl., vol. 29, N. 1 (1995), 75-83.
Top-down lower bounds for depth-three circuits   [pdf] [Abstract (HTML)]
joint with J. Håstad and P. Pudlák
In Proc. 34-th FOCS'93   doi: 10.1109/SFCS.1993.366875
Computational Complexity, 5 (1995) 99-112.   © Birkhäuser Verlag
doi: 10.1007/BF01268140
The graph of integer multiplication is hard for read-k times networks, tech. rep. 1995. [pdf] [Abstract (HTML)]
On multiparty games for pointer jumping [pdf]
joint with C. Damm, tech. rep. 1995.
On communication games with more than two players, tech. rep. 1995. [pdf] [Abstract (HTML)]
Finite limits and lower bounds for circuit size tech. rep. 1994 [pdf]
Optimal versus stable in boolean formulae [pdf]
Springer Lect. Notes in Comput. Sci. vol. 529 (1991) 265--274. © Springer Verlag
A criterion for monotone circuit complexity, unpublished manuscript, 1991 [pdf]
Functional approximations in the theory of circuit lower bounds (in Russian) [pdf]
Diskretnaja Matematika 2:2 (1990) 45-59. © Nauka
Monotone circuits and local computations [pdf]
Proc. of 31-th Conf. of Lithuanian Math. Soc. (1990).
The effect of null-chains on the complexity of contact schemes [pdf]
Springer Lect. Notes in Comput. Sci. vol. 380 (1989) 346-356. © Springer Verlag
Entropy of contact circuits and lower bounds on their complexity [pdf]
Theoretical Computer Science 57:1 (1988) 113-129. © Elsevie
Two lower bounds for circuits over the basis {&,V,-} [pdf]
Springer Lect. Notes in Comput. Sci. vol. 324 (1988) 371-380. © Springer Verlag
On an entropic method of obtaining lower bounds on the complexity of Boolean functions [pdf]
Doklady Akademii Nauk SSSR, 298:3 (1988 556-559 . Translation in: Soviet Math Doklady 37:1 (1988),126-129.
Information flow and width of branching programs [pdf]
MFCS'87.Springer Lect. Notes in Comput. Sci., vol. 278 (1987) 228-230 © Springer Verlag
Lower bounds on communication complexity [pdf]
Math, Logics and Its Appl., vol. 5 (Vilnius, 1987), 22-31.
Lower bounds on the complexity of local circuits (preliminary report) [pdf]
MFCS'86, Springer Lect. Notes in Comput. Sci., vol. 233 (1986) 440-448 © Springer Verlag
Journal version in: Theoretical Computer Science 57:1 (1988) 113-129. [pdf]
Succinct data representations and the complexity of computations
In: Colloquia Mathematica Societatis Janos Bolyai 44, (North-Holland, Amsterdam, 1985) pp. 271-282.
Convolutional characterization of computability and complexity
In: Colloquia Mathematica Societatis Janos Bolyai 44, (North-Holland, Amsterdam, 1985) pp. 251-270
On the arithmetization of computations (in Russian) [pdf]
In: Math. Logics and its Applications,3, (Vilnius, 1983).
Self-correcting programs and theircomplexity [pdf]
In: Problemy Kibernetiki,38 (Nauka, Moscow, 1981), pp.217-258 (in Russian)