 | 2012 |
|---|
| 70 |       | Stasys Jukna:
Independent set problem for individual graphs has small communication complexity
CoRR abs/1203.5414: (2012) |
| 69 | | Stasys Jukna:
Clique Problem, Cutting Plane Proofs, and Communication Complexity.
Electronic Colloquium on Computational Complexity (ECCC) 19: 39 (2012) |
| 68 | | Stasys Jukna:
Limitations of Incremental Dynamic Programs.
Electronic Colloquium on Computational Complexity (ECCC) 19: 41 (2012) |
| 2011 |
|---|
| 67 | | Stasys Jukna,
Georg Schnitger:
Min-rank conjecture for log-depth circuits.
J. Comput. Syst. Sci. 77(6): 1023-1038 (2011) |
| 66 | | Stasys Jukna,
Georg Schnitger:
Yet harder knapsack problems.
Theor. Comput. Sci. 412(45): 6351-6358 (2011) |
| 2010 |
|---|
| 65 | | Stasys Jukna,
Georg Schnitger:
Circuits with arbitrary gates for random operators
CoRR abs/1004.5236: (2010) |
| 64 | | Stasys Jukna,
Georg Schnitger:
Min-Rank Conjecture for Log-Depth Circuits
CoRR abs/1005.1009: (2010) |
| 63 | | Stasys Jukna:
Representing (0, 1)-matrices by boolean circuits.
Discrete Mathematics 310(1): 184-187 (2010) |
| 62 | | Pavel Hrubes,
Stasys Jukna,
Alexander S. Kulikov,
Pavel Pudlák:
On convex complexity measures.
Theor. Comput. Sci. 411(16-18): 1842-1854 (2010) |
| 61 | | Stasys Jukna:
Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits.
Theory Comput. Syst. 46(2): 301-310 (2010) |
| 2009 |
|---|
| 60 | | Stasys Jukna,
Alexander S. Kulikov:
On covering graphs by complete bipartite subgraphs.
Discrete Mathematics 309(10): 3399-3403 (2009) |
| 59 | | Pavel Hrubes,
Stasys Jukna,
Alexander S. Kulikov,
Pavel Pudlák:
On convex complexity measures.
Electronic Colloquium on Computational Complexity (ECCC) 16: 40 (2009) |
| 58 | | Stasys Jukna,
Georg Schnitger:
Min-Rank Conjecture for Log-Depth Circuits.
Electronic Colloquium on Computational Complexity (ECCC) 16: 8 (2009) |
| 57 | | Stasys Jukna:
A nondeterministic space-time tradeoff for linear codes.
Inf. Process. Lett. 109(5): 286-289 (2009) |
| 56 | | Stasys Jukna:
On set intersection representations of graphs.
Journal of Graph Theory 61(1): 55-75 (2009) |
| 2008 |
|---|
| 55 | | Alexander E. Andreev,
Stasys Jukna:
Very large cliques are easy to detect.
Discrete Mathematics 308(16): 3717-3721 (2008) |
| 54 | | Stasys Jukna:
Entropy of operators or why matrix multiplication is hard for small depth circuits.
Electronic Colloquium on Computational Complexity (ECCC) 15(019): (2008) |
| 53 | | Stasys Jukna:
Expanders and time-restricted branching programs.
Theor. Comput. Sci. 409(3): 471-476 (2008) |
| 2006 |
|---|
| 52 | | Stasys Jukna:
Graphs and Circuits: Some Further Remarks.
Complexity of Boolean Functions 2006 |
| 51 | | Alexander E. Andreev,
Stasys Jukna:
Very Large Cliques are Easy to Detect.
Complexity of Boolean Functions 2006 |
| 50 | | Stasys Jukna:
On Graph Complexity.
Combinatorics, Probability & Computing 15(6): 855-876 (2006) |
| 49 | | Stasys Jukna:
Disproving the Single Level Conjecture.
SIAM J. Comput. 36(1): 83-98 (2006) |
| 2005 |
|---|
| 48 | | Stasys Jukna:
Disproving the single level conjecture
Electronic Colloquium on Computational Complexity (ECCC)(021): (2005) |
| 47 | | Stasys Jukna:
Expanders and time-restricted branching programs
Electronic Colloquium on Computational Complexity (ECCC)(079): (2005) |
| 46 | | Stasys Jukna:
On the P versus NP intersected with co-NP question in communication complexity.
Inf. Process. Lett. 96(6): 202-206 (2005) |
| 2004 |
|---|
| 45 | | Stasys Jukna:
On Graph Complexity
Electronic Colloquium on Computational Complexity (ECCC)(005): (2004) |
| 44 | | Stasys Jukna:
A note on the P versus NP intersected with co-NP question in communication complexity
Electronic Colloquium on Computational Complexity (ECCC)(062): (2004) |
| 43 | | Pavol Duris,
Juraj Hromkovic,
Stasys Jukna,
Martin Sauerhoff,
Georg Schnitger:
On multi-partition communication complexity.
Inf. Comput. 194(1): 49-75 (2004) |
| 42 | | Stasys Jukna:
On the minimum number of negations leading to super-polynomial savings.
Inf. Process. Lett. 89(2): 71-74 (2004) |
| 2003 |
|---|
| 41 | | Stasys Jukna,
Stanislav Zák:
On uncertainty versus size in branching programs.
Theor. Comput. Sci. 290(3): 1851-1867 (2003) |
| 2002 |
|---|
| 40 | | Stasys Jukna,
Georg Schnitger:
Triangle-Freeness Is Hard To Detect.
Combinatorics, Probability & Computing 11(6): 549-569 (2002) |
| 2001 |
|---|
| 39 | | Stasys Jukna:
Extremal combinatorics - with applications in computer science.
Springer 2001: I-XVII, 1-375 |
| 38 | | Pavol Duris,
Juraj Hromkovic,
Stasys Jukna,
Martin Sauerhoff,
Georg Schnitger:
On Multipartition Communication Complexity.
STACS 2001: 206-217 |
| 37 | | Stasys Jukna:
A Note on the Minimum Number of Negations Leading to Superpolynomial Savings
Electronic Colloquium on Computational Complexity (ECCC) 8(058): (2001) |
| 36 | | Pavol Duris,
Juraj Hromkovic,
Stasys Jukna,
Martin Sauerhoff,
Georg Schnitger:
On Multipartition Communication Complexity
Electronic Colloquium on Computational Complexity (ECCC) 8(066): (2001) |
| 35 | | Stasys Jukna,
Stanislav Zák:
On Uncertainty versus Size in Branching Programs
Electronic Colloquium on Computational Complexity (ECCC) 8(39): (2001) |
| 34 | | Stasys Jukna,
Georg Schnitger:
On Multi-Partition Communication Complexity of Triangle-Freeness
Electronic Colloquium on Computational Complexity (ECCC) 8(49): (2001) |
| 2000 |
|---|
| 33 | | Stasys Jukna,
Stanislav Zák:
Some Notes on the Information Flow in Read-Once Branching Programs.
SOFSEM 2000: 356-364 |
| 1999 |
|---|
| 32 | | Stasys Jukna:
Combinatorics of Monotone Computations.
Combinatorica 19(1): 65-85 (1999) |
| 31 | | Stasys Jukna,
Alexander A. Razborov,
Petr Savický,
Ingo Wegener:
On P versus NP cap co-NP for decision trees and read-once branching programs.
Computational Complexity 8(4): 357-370 (1999) |
| 30 | | Stasys Jukna:
Linear Codes are Hard for Oblivious Read-Once Parity Branching Programs.
Inf. Process. Lett. 69(6): 267-269 (1999) |
| 1998 |
|---|
| 29 | | Stasys Jukna,
Stanislav Zák:
On Branching Programs With Bounded Uncertainty (Extended Abstract).
ICALP 1998: 259-270 |
| 28 | | Carsten Damm,
Stasys Jukna,
Jiri Sgall:
Some Bounds on Multiparty Communication Complexity of Pointer Jumping.
Computational Complexity 7(2): 109-127 (1998) |
| 27 | | Stasys Jukna,
Alexander A. Razborov:
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.
Discrete Applied Mathematics 85(3): 223-238 (1998) |
| 26 | | Stasys Jukna,
Stanislav Zák:
On Branching Programs With Bounded Uncertainty
Electronic Colloquium on Computational Complexity (ECCC) 5(30): (1998) |
| 25 | | Stasys Jukna:
Combinatorics of Monotone Computations
Electronic Colloquium on Computational Complexity (ECCC) 5(41): (1998) |
| 1997 |
|---|
| 24 | | Stasys Jukna:
Finite Limits and Monotone Computations: The Lower Bounds Criterion.
IEEE Conference on Computational Complexity 1997: 302-313 |
| 23 | | Stasys Jukna,
Alexander A. Razborov,
Petr Savický,
Ingo Wegener:
On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.
MFCS 1997: 319-326 |
| 22 | | Stasys Jukna,
Alexander A. Razborov,
Petr Savický,
Ingo Wegener:
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs
Electronic Colloquium on Computational Complexity (ECCC) 4(23): (1997) |
| 21 | | Stasys Jukna:
Exponential Lower Bounds for Semantic Resolution
Electronic Colloquium on Computational Complexity (ECCC) 4(7): (1997) |
| 1996 |
|---|
| 20 | | Carsten Damm,
Stasys Jukna,
Jiri Sgall:
Some Bounds on Multiparty Communication Complexity of Pointer Jumping.
STACS 1996: 643-654 |
| 19 | | Stasys Jukna:
Finite Limits and Monotone Computations
Electronic Colloquium on Computational Complexity (ECCC) 3(26): (1996) |
| 18 | | Stasys Jukna,
Alexander A. Razborov:
Neither Reading Few Bits Twice nor Reading Illegally Helps Much
Electronic Colloquium on Computational Complexity (ECCC) 3(37): (1996) |
| 1995 |
|---|
| 17 | | Johan Håstad,
Stasys Jukna,
Pavel Pudlák:
Top-Down Lower Bounds for Depth-Three Circuits.
Computational Complexity 5(2): 99-112 (1995) |
| 16 | | Carsten Damm,
Stasys Jukna,
Jiri Sgall:
Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Electronic Colloquium on Computational Complexity (ECCC) 2(44): (1995) |
| 15 |  | Stasys Jukna:
A Note on Read-k Times Branching Programs.
ITA 29(1): 75-83 (1995) |
| 14 | | Stasys Jukna:
Computing Threshold Functions by Depth-3 Threshold Circuits with Smaller Thresholds of Their Gates.
Inf. Process. Lett. 56(3): 147-150 (1995) |
| 13 | | Carsten Damm,
Stasys Jukna:
On Multiparity Games for Pointer Jumping
Universität Trier, Mathematik/Informatik, Forschungsbericht 95-09: (1995) |
| 12 | | Stasys Jukna:
The Graph of Integer Multiplication is Hard for Read-k-Times Networks
Universität Trier, Mathematik/Informatik, Forschungsbericht 95-10: (1995) |
| 11 | | Stasys Jukna:
On Communication Games with More than Two Players
Universität Trier, Mathematik/Informatik, Forschungsbericht 95-11: (1995) |
| 10 | | Carsten Damm,
Stasys Jukna,
Jiri Sgall:
Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Universität Trier, Mathematik/Informatik, Forschungsbericht 95-17: (1995) |
| 1994 |
|---|
| 9 | | Stasys Jukna:
A Note on Read-k Times Branching Programs
Electronic Colloquium on Computational Complexity (ECCC) 1(27): (1994) |
| 8 | | Stasys Jukna:
Finite Limits and Lower Bounds for Circuits Size
Universität Trier, Mathematik/Informatik, Forschungsbericht 94-06: (1994) |
| 1993 |
|---|
| 7 | | Johan Håstad,
Stasys Jukna,
Pavel Pudlák:
Top-Down Lower Bounds for Depth 3 Circuits
FOCS 1993: 124-129 |
| 1991 |
|---|
| 6 | | Stasys Jukna:
Optimal versus Stable in Boolean Formulae.
FCT 1991: 265-274 |
| 1989 |
|---|
| 5 | | Stasys Jukna:
The Effect of Null-Chains on the Complexity of Contact Schemes.
FCT 1989: 246-256 |
| 1988 |
|---|
| 4 | | Stasys Jukna:
Two Lower Bounds for Circuits over the Basis (&, V, -).
MFCS 1988: 371-380 |
| 3 | | Stasys Jukna:
Entropy of Contact Circuits and Lower Bounds on Their Complexity.
Theor. Comput. Sci. 57: 113-129 (1988) |
| 1987 |
|---|
| 2 | | Stasys Jukna:
Information Flow and Width of Branching Programs (Extended Abstract).
FCT 1987: 228-230 |
| 1986 |
|---|
| 1 | | Stasys Jukna:
Lower Bounds on the Complexity of Local Circuits (Preliminary Report).
MFCS 1986: 440-448 |
Data released under the ODC-BY 1.0 license — See also our legal information page