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