S. Jukna

Online preprints of some papers

• Limitations of incremental dynamic programming     [pdf]     [Abstract (HTML)]
  Algorithmica
  10.1007/s00453-013-9747-6

• Computational complexity of graphs     [pdf] 
  A chapter in a forthcoming book "Advances in Network Complexity" (submitted)

• 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

• Cutting planes cannot approximate some integer programs     [pdf]  [Abstract (HTML)]  
  Joint with Georg Schnitger
  Operations Research Letters 40(4) (2012) 272-275
  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

• 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

• 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 © Society for Industrial and Applied Mathematics
  [ Dagstuhl seminar slides (pdf)]
  doi: 10.1137/S0097539705447001
  
  
• 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
  
  
• 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
  
  
• 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
  
  
• 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.
  
  
• On multi-partition communication complexity  [ps]  [pdf]
  joint with P. Duris, J. Hromkovic, 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  [ps] [pdf]
  joint with G. Schnitger
    Combinatorics, Probability & Computing 11:6 (2002), 549-569. ©  Cambridge University Press
  [ Abstract (HTML)]   See also a Comment
  
  
• Some notes on the information flow in read-once branching programs  [ps] [pdf]
  joint with S. Zak
  Springer Lect. Notes in Comput. Sci., vol. 1963 (2000), 356-364.   ©  Springer Verlag
  
  
• 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
  
  
• 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
  
  
• 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.
  
  
• Combinatorics of monotone computations [pdf]  
  Abstract (HTML)]
  Combinatorica, 19(1) (1999), pp. 65-85 ©  Springer Verlag
  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 [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
  
  
• 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
  
  
• 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
  
  
• 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
  
  
• A note on read-k times branching programs [ps] [pdf]
  RAIRO Theoret. Informatics and Appl., vol. 29, N. 1 (1995), 75-83.
  
  
• 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
  
  
• The graph of integer multiplication is hard for read-k times networks, tech. rep. 1995. [ps] [pdf]
  [Abstract (HTML)]
  
  
• On multiparty games for pointer jumping  [ps] [pdf]
  joint with C. Damm, tech. rep. 1995.
  
  
• On communication games with more than two players, tech. rep. 1995. [ps] [pdf
  [Abstract (HTML)]
  
  
• Finite limits and lower bounds for circuit size tech. rep. 1994 [ps] [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 [ps] [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 [ps] [pdf]
  Proc. of 31-th Conf. of Lithuanian Math. Soc. (1990).
  
  
• The effect of null-chains on the complexity of contact schemes  [pdf]
  Proc. of FCT'89 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]
  Proc. of MFCS'88 Springer Lect. Notes in Comput. Sci. vol. 324 (1988) 371-380. © Springer Verlag
  
  
• Information flow and width of branching programs [pdf]
  Proc. of 6th MFCS Springer Lect. Notes in Comput. Sci., vol. 278(1987) 228-230 © Springer Verlag
  
  
• Lower bounds on communication complexity  [ps] [pdf]
  Math, Logics and Its Appl., vol. 5 (Vilnius, 1987), 22-31.
  
  
• On the arithmetization of computations (in Russian)  [pdf]
  In: Math. Logics and its Applications,3, (Vilnius, 1983).
  
  

• Combinatorics of Finite Computations: The Lower Bounds Problem    [pdf]
  Summary of the second doctor degree dr. habil. (in Lithuanian)

• List of some older papers (not available online)