S. Jukna

Online preprints of some papers

Journal papers:

• On convex complexity measures     [pdf]   
  Joint with Pavel Hrubes, Alexander Kulikov and Pavel Pudlak
  [Abstract (HTML)]     Theoretical Computer Science (to appear)

• Complexity of random operators in circuits with arbitrary gates     [pdf]   
  Joint with Georg Schnitger
  [Abstract (HTML)]     (submitted)

• Min-rank conjecture for log-depth circuits     [pdf]   
  Joint with Georg Schnitger
  [Abstract (HTML)]    
  Journal version in: Journal of Comput. Syst. Sci. (to appear)    © Elsevier

• Representing (0,1)-matrices by depth-2 circuits with arbitrary gates    [pdf]   
  [Abstract (HTML)]  
  Journal version in: 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)]
  Journal version in: Theory of Computing Systems ©  Springer Verlag
  doi:10.1007/s00224-008-9133-y

• A nondeterministic space-time tradeoff for linear codes     [pdf] 
  [Abstract (HTML)] 
  Journal version: 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]
  joint with Alexander Kulikov
  [Abstract (HTML)] 
  Journal version in: 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 version in: Journal of Graph Theory 61(1) (2009) 55-75    © John Wiley & Sons
  doi:10.1002/jgt.20367

• Very large cliques are easy to detect    [ps]    [pdf]
  joint with Alexander Andreev
  [Abstract (HTML)]
  Journal version in: 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)] 
  Journal version in: Theoretical Computer Science 409 (3) (2008) 471-476    © Elsevier
  doi: 10.1016/j.tcs.2008.09.012

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

• On graph complexity  [pdf]
  Journal version in: Combinatorics, Probability & Computing     15 (2006) 855-876      © Cambridge University Press
  Slides of a talk on a local seminar
  doi: doi:10.1017/S0963548306007620

• On the P versus NP intersected with co-NP question in communication complexity   [ps]  [pdf]
  Journal version in: Information Processing Letters  96(6)  (2005)  202-206 © Elsevier
  [Abstract (HTML)]
  doi: 10.1016/j.ipl.2005.08.003

• On the minimum number of negations leading to  super-polynomial savings [ps] [pdf]  
  Journal version in: Information Processing Letters   89:2, (2004)  71-74 © Elsevier
  [Abstract (HTML)]
  doi: 10.1016/j.ipl.2003.10.003

• On uncertainty versus size in branching programs  [ps] [pdf]
  joint with S. Zák.
  Journal version in: Theoretical Computer Science  290:3 (2003), 1851-1867. © Elsevier
  doi: 10.1016/S0304-3975(02)00323-7
  
  
• On multi-partition communication complexity  [ps]  [pdf]
  joint with P. Duris, J. Hromkovic, M. Sauerhoff and G. Schnitger  
  Journal version in:  Information and Computation ,  194:1  (2004), 49-75 © Elsevier
  
  
• Triangle-freeness is hard to detect  [ps] [pdf]
  joint with G. Schnitger
  Journal version in:  Combinatorics, Probability & Computing 11:6 (2002), 549-569. ©  Cambridge University Press
  [ Abstract (HTML)]   See also a Comment
  
  
• Linear codes are hard for oblivious read-once parity branching programs  [ps] [pdf]
  Journal version in: 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,
  Journal version in: 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 [ps] [pdf]  
  Abstract (HTML)]
  Journal version in: Combinatorica, 19(1) (1999), pp. 65-85
  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
  Journal version in: 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
  Journal version in: 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)]
  Journal version in: 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]
  Journal version in 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
  Journal version in: Computational Complexity, 5 (1995) 99-112.   © Birkhäuser Verlag
  doi: 10.1007/BF01268140
  
  
• Functional approximations in the theory of circuit lower bounds (in Russian)   [pdf]
  Journal version in: Diskretnaja Matematika 2:2 (1990) 45-59. © Nauka
  
  
• Entropy of contact circuits and lower bounds on their complexity  [pdf]
  Journal version in: Theoretical Computer Science 57:1 (1988) 113-129. © Elsevier
  
  

Papers in proceedings, tech. reports, etc. without their journal versions:

• Graphs and circuits: some further remarks    [pdf] 
  Dagstuhl Seminar Proceedings, vol. 06111 (2006), 16 pp.
  http://drops.dagstuhl.de/opus/volltexte/2006/621/
  
  
• On nondeterministic linear time branching programs [ps] [pdf] Unpublished note, 2002
  
  
• 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
  
  
• 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.
  
  
• Finite limits and lower bounds for circuit size tech. rep. 1994 [ps] [pdf]
  
  
• On communication games with more than two players, tech. rep. 1995. [ps] [pdf
  [Abstract (HTML)]
  
  
• 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]
  
  
• 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
  
  
• 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
  
  
• Lower bounds on communication complexity  [ps] [pdf]
  Math, Logics and Its Appl., vol. 5 (Vilnius, 1987), 22-31.

• 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)