Stasys Jukna: Online manuscripts of my papers

Co-authors ⇒

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

Notes on Boolean read-k and multilinear circuits [Abstract HTML] [pdf]
Discrete Appl. Math. vol. 360 (2025), 307-327.
Preprints: Arxiv ECCC Report Nr. 84, 2022
doi: 10.1016/j.dam.2024.09.023
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 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
A note on read-once branching programs for blocking sets in projective planes [pdf]
joint with A. Razborov
Unpublished manuscript
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. © Elsevier
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]
On the arithmetization of computations (in Russian) [pdf]
In: Math. Logics and its Applications,3, (Vilnius, 1983).
Self-correcting programs and their complexity [pdf]
In: Problemy Kibernetiki,38 (Nauka, Moscow, 1981), pp.217-258 (in Russian)