Papers by Stasys Jukna

S. Jukna

Online preprints of some 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.

Anti-chronological order:

Entropy of operators or why matrix multiplication is hard for depth-two circuits [pdf]
[Abstract (HTML)]
Theory of Comput. Syst., Published online: 16 July 2008, DOI 10.1007/s00224-008-9133-y
A nondeterministic space-time tradeoff for linear codes [pdf]
[Abstract (HTML)]
Inf. Proc. Letters (submitted)
On covering graphs by complete bipartite subgraphs [pdf]
joint with A. Kulikov
[Abstract (HTML)]
Discrete Mathematics (to appear)
On set intersection representations of graphs [pdf]
[Abstract (HTML)]
J. of Graph Theory (to appear)
Very large cliques are easy to detect [ps] [pdf]
joint with A. Andreev
[Abstract (HTML)]
Journal version in: Discrete Mathematics 308(16) (2007), 3717-3721, © Elsevier
Expanders and time-restricted branching programs [ps] [pdf]
[Abstract (HTML)]
Theoretical Computer Science (to appear) © Elsevier
Graphs and circuits: some further remarks [pdf]
Dagstuhl Seminar Proceedings, vol. 06111 (2006), 16 pp.
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)]
On graph complexity [ps] [pdf]
Journal version in: Combinatorics, Probability & Computing 15 (2006) 855-876 © Cambridge University Press
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)]
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)]
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
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
On nondeterministic linear time branching programs [ps] [pdf] Unpublished note, 2002
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
Some notes on the information flow in read-once branching programs [ps] [pdf]
joint with S. Zak
Springer LNCS, vol. 1963 (2000), 356-364. © Springer Verlag
Linear codes are hard for oblivious read-once parity branching programs [ps] [pdf]
Journal version in: Information Processing Letters, 69 (1999), 267-269 © Elsevier
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
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. © American Mathematical Society
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)]
Proc. 12-th Ann. IEEE Conf. on Comput. Complexity, (1997) pp. 302-313.
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
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
The graph of integer multiplication is hard for read-k times networks, tech. rep. 1995. [ps] [pdf]
[Abstract (HTML)]
On communication games with more than two players, tech. rep. 1995. [ps] [pdf
[Abstract (HTML)]
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
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]
A note on read-k times branching programs [ps] [pdf]
Tech. Rep. 448, Uni. Dortmund, (1992)
Journal version in RAIRO Theoret. Informatics and Appl., vol. 29, N. 1 (1995), 75-83.
Top-down lower bounds for depth-three circuits, FOCS'93 [ps] [pdf]
[Abstract (HTML)]
joint with J. Hastad and P. Pudlak
Journal version in: Computational Complexity, 5 (1995) 99-112. © Birkhäuser Verlag
Optimal versus stable in boolean formulae [pdf]
Lecture 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 Lecture 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 Lecture Notes in Comput. Sci. vol. 324 (1988) 371-380. © Springer Verlag
Lower bounds on communication complexity [ps] [pdf]
Mathematical Logics and Its Applications, 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)

Back to my home page