S. Jukna

Online preprints of my papers

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. 
  1. Incremental vs. non-incremental dynamic programming   [pdf]     [Abstract (HTML)]
    Submitted, 2018

  2. Minkowski complexity of sets: an easy lower bound   [pdf]     [Abstract (HTML)]
    Amer. Math. Monthly 124:8 (2017) 749-753   © 2017 Mathematical Association of America. All Rights Reserved.

  3. 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

  4. 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

  5. Lower bounds for monotone counting circuits   [pdf]     [Abstract (HTML)]
    Discrete Applied Mathematics 213 (2016) 139-152   © Elsevier

  6. 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

  7. Limitations of incremental dynamic programming   [pdf]     [Abstract (HTML)]
    Algorithmica, 69(2) (2014) 461-492     ©  Springer Verlag
    doi: 10.1007/s00453-013-9747-6

  8. 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

  9. Computational complexity of graphs     [pdf]     [Abstract (HTML)]
    Advances in Network Complexity, Quantitative and Network Biology, Vol. 4,
    Willey-Blackwell, 2013, 99-154 (book chapter)    © John Wiley & Sons

  10. 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

  11. 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

  12. 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

  13. 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

  14. On convex complexity measures     [pdf] [Abstract (HTML)]  
    Joint with Pavel Hrubes, Alexander Kulikov and Pavel Pudlak
    Theoretical Computer Science, vol. 411 (2010), pp. 1842-1854.    ©Elsevier
    doi: 10.1016/j.tcs.2010.02.004

  15. Circuits with arbitrary gates for random operators     [pdf]  [Abstract (HTML)]
    Joint with Georg Schnitger

  16. 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

  17. 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

  18. A nondeterministic space-time tradeoff for linear codes     [pdf]  [Abstract (HTML)] 
    Information Processing Letters  109(5) (2009) 286-289   © Elsevier

  19. On covering graphs by complete bipartite subgraphs     [pdf]  [Abstract (HTML)]
    joint with Alexander Kulikov
    Discrete Mathematics 309(10) (2009) 3399-3403.    © Elsevier

  20. On set intersection representations of graphs    [pdf]   [Abstract (HTML)]
    Journal of Graph Theory 61(1) (2009) 55-75    © John Wiley & Sons

  21. 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

  22. 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

  23. Disproving the single level conjecture     [pdf]  [Abstract (HTML)]
    SIAM J. Comput.   36(1) (2006) 83-98 © Society for Industrial and Applied Mathematics
    [ Dagstuhl seminar slides (pdf)]
    doi: 10.1137/S0097539705447001

  24. Graphs and circuits: some further remarks    [pdf] 
    Dagstuhl Seminar Proceedings, vol. 06111 (2006), 16 pp.

  25. On graph complexity  [pdf]
    Combinatorics, Probability & Computing     15 (2006) 855-876      © Cambridge University Press
    Slides of a talk on a local seminar

  26. 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

  27. On the minimum number of negations leading to  super-polynomial savings [pdf]   [Abstract (HTML)]
    Information Processing Letters   89:2, (2004)  71-74 © Elsevier

  28. On uncertainty versus size in branching programs   [pdf]
    joint with S. Zák.
    Theoretical Computer Science  290:3 (2003), 1851-1867. © Elsevier
    doi: 10.1016/S0304-3975(02)00323-7
    Here is a nice application of our method.

  29. On multi-partition communication complexity  [ps]  [pdf]
    joint with P. Duris, J. Hromkovic, M. Sauerhoff and G. Schnitger  
    Information and Computation194:1  (2004), 49-75 © Elsevier
    doi: 10.1016/j.ic.2004.05.002

  30. Triangle-freeness is hard to detect  [ps] [pdf]
    joint with G. Schnitger
      Combinatorics, Probability & Computing 11:6 (2002), 549-569. ©  Cambridge University Press
    [ Abstract (HTML)]   See also a Comment

  31. Some notes on the information flow in read-once branching programs  [ps] [pdf]
    joint with S. Zák
    Springer Lect. Notes in Comput. Sci., vol. 1963 (2000), 356-364.   ©  Springer Verlag

  32. Linear codes are hard for oblivious read-once parity branching programs  [ps] [pdf]
    Information Processing Letters, 69 (1999), 267-269 © Elsevier
    doi: 10.1016/S0020-0190(99)00027-7

  33. On P versus NP intersected with co-NP for decision trees and read-once branching programs  [ps] [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

  34. Exponential lower bounds on the size of clause based semantic derivations, Manuscript, 1996.  [ps]  [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. © Amer. Math. Soc.

  35. Combinatorics of monotone computations [pdf]  
    Abstract (HTML)]
    Combinatorica, 19(1) (1999), pp. 65-85 ©  Springer Verlag
    Preliminary version "Finite Limits and Monotone Computations" appeared 1996 as ECCC Report Nr. 26.
    In the boolean case the lower bounds criterion  is particularly simple: see an excerpt from my book.

  36. Finite limits and monotone computations: the lower bounds criterion [ps] [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

  37. Neither reading few bits twice nor reading illegally helps much [ps] [pdf]
    joint with A. Razborov
    Discrete Applied Mathematics, 85:3 (1998), 223-238   © Elsevier
    doi: 10.1016/S0166-218X(98)00042-0

  38. Some bounds on multiparty communication complexity of pointer jumping [ps] [pdf]
    joint with C. Damm and J. Sgall
    Computational Complexity, 7:2 (1998), pp. 109-127   © Birkhäuser Verlag
    doi: 10.1007/PL00001595

  39. Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates  [ps] [pdf] 
    [Abstract (HTML)]
    Information Processing Letters, 56 (1995), 147-150   © Elsevier
    doi: 10.1016/0020-0190(95)00137-2

  40. A note on read-k times branching programs [pdf]
    RAIRO Theoret. Informatics and Appl., vol. 29, N. 1 (1995), 75-83.

  41. Top-down lower bounds for depth-three circuits [ps] [pdf]
    [Abstract (HTML)]
    joint with J. Hastad and P. Pudlak
    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

  42. The graph of integer multiplication is hard for read-k times networks, tech. rep. 1995. [ps] [pdf]
    [Abstract (HTML)]

  43. On multiparty games for pointer jumping  [ps] [pdf]
    joint with C. Damm, tech. rep. 1995.

  44. On communication games with more than two players, tech. rep. 1995. [ps] [pdf
    [Abstract (HTML)]

  45. Finite limits and lower bounds for circuit size tech. rep. 1994 [ps] [pdf]

  46. Optimal versus stable in boolean formulae [pdf]
    Springer Lect. Notes in Comput. Sci. vol. 529 (1991) 265--274.    © Springer Verlag

  47. A criterion for monotone circuit complexity, unpublished manuscript, 1991 [ps] [pdf]

  48. Functional approximations in the theory of circuit lower bounds (in Russian)   [pdf]
    Diskretnaja Matematika 2:2 (1990) 45-59. © Nauka

  49. Monotone circuits and local computations [ps] [pdf]
    Proc. of 31-th Conf. of Lithuanian Math. Soc. (1990).

  50. 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

  51. Entropy of contact circuits and lower bounds on their complexity  [pdf]
    Theoretical Computer Science 57:1 (1988) 113-129. © Elsevier

  52. Two lower bounds for circuits over the basis {&,V,-}   [pdf]
    Springer Lect. Notes in Comput. Sci. vol. 324 (1988) 371-380. © Springer Verlag

  53. Information flow and width of branching programs [pdf]
    Springer Lect. Notes in Comput. Sci., vol. 278(1987) 228-230 © Springer Verlag

  54. Lower bounds on communication complexity  [ps] [pdf]
    Math, Logics and Its Appl., vol. 5 (Vilnius, 1987), 22-31.

  55. On the arithmetization of computations (in Russian)  [pdf]
    In: Math. Logics and its Applications,3, (Vilnius, 1983).

  56. Self-correcting programs and their complexity   [pdf]
    In: Problemy Kibernetiki,38 (Nauka, Moscow, 1981), pp.217-258 (in Russian)

Back to my home page