Stasys Jukna

ORCID

Publication Activity (10 Years)

Years Active: 1986-2022
Publications (10 Years): 31

Top Venues

Electron. Colloquium Comput. Complex.

CoRR

Am. Math. Mon.

SIAM J. Discret. Math.

Publications

Stasys Jukna
Notes on Monotone Read-k Circuits. Electron. Colloquium Comput. Complex. (2022)
Stasys Jukna, Andrzej Lingas
Lower bounds for Boolean circuits of bounded negation width. J. Comput. Syst. Sci. 129 (2022)
Stasys Jukna
Notes on Boolean Read-k and Multilinear Circuits. CoRR (2022)
Stasys Jukna
Notes on Hazard-Free Circuits. SIAM J. Discret. Math. 35 (2) (2021)
Stasys Jukna, Hannes Seiwert
Tropical Kirchhoff's formula and postoptimality in matroid optimization. Discret. Appl. Math. 289 (2021)
Stasys Jukna, Hannes Seiwert
Approximation Limitations of Pure Dynamic Programming. SIAM J. Comput. 49 (1) (2020)
Stasys Jukna
Notes on Hazard-Free Circuits. CoRR (2020)
Stasys Jukna
Coin Flipping in Dynamic Programming is Almost Useless. CoRR (2020)
Stasys Jukna, Hannes Seiwert
Sorting can exponentially speed up pure dynamic programming. Inf. Process. Lett. (2020)
Stasys Jukna, Hannes Seiwert
Sorting Can Exponentially Speed Up Pure Dynamic Programming. CoRR (2020)
Stasys Jukna
Coin Flipping in Dynamic Programming Is Almost Useless. ACM Trans. Comput. Theory 12 (3) (2020)
Stasys Jukna, Hannes Seiwert
Approximation Limitations of Pure Dynamic Programming. CoRR (2020)
Stasys Jukna, Hannes Seiwert, Igor Sergeev
Reciprocal Inputs in Arithmetic and Tropical Circuits. Electron. Colloquium Comput. Complex. 27 (2020)
Stasys Jukna, Hannes Seiwert
Tropical Kirchhoff's Formula and Postoptimality in Matroid Optimization. CoRR (2020)
Stasys Jukna
Notes on Hazard-Free Circuits. Electron. Colloquium Comput. Complex. 27 (2020)
Stasys Jukna, Andrzej Lingas
Lower Bounds for DeMorgan Circuits of Bounded Negation Width. STACS (2019)
Stasys Jukna, Hannes Seiwert
Greedy can beat pure dynamic programming. Inf. Process. Lett. 142 (2019)
Stasys Jukna, Hannes Seiwert
Sorting Can Exponentially Speed Up Pure Dynamic Programming. Electron. Colloquium Comput. Complex. 26 (2019)
Stasys Jukna
Coin Flipping Cannot Shorten Arithmetic Computations. Am. Math. Mon. 126 (4) (2019)
Stasys Jukna
Derandomizing Dynamic Programming and Beyond. Electron. Colloquium Comput. Complex. 25 (2018)
Stasys Jukna, Hannes Seiwert
Approximation Limitations of Tropical Circuits. Electron. Colloquium Comput. Complex. 25 (2018)
Stasys Jukna, Hannes Seiwert
Greedy can also beat pure dynamic programming. CoRR (2018)
Stasys Jukna
Incremental versus Non-Incremental Dynamic Programming. Electron. Colloquium Comput. Complex. 25 (2018)
Stasys Jukna, Hannes Seiwert
Greedy can also beat pure dynamic programming. Electron. Colloquium Comput. Complex. 25 (2018)
Stasys Jukna
Incremental versus non-incremental dynamic programming. Oper. Res. Lett. 46 (3) (2018)
Stasys Jukna, Andrzej Lingas
Lower Bounds for Circuits of Bounded Negation Width. Electron. Colloquium Comput. Complex. 25 (2018)
Stasys Jukna
Minkowski Complexity of Sets: An Easy Lower Bound. Am. Math. Mon. 124 (8) (2017)
Stasys Jukna
Lower bounds for monotone counting circuits. Discret. Appl. Math. 213 (2016)
Stasys Jukna, Georg Schnitger
On the optimality of Bellman-Ford-Moore shortest path algorithm. Theor. Comput. Sci. 628 (2016)
Stasys Jukna
Tropical Complexity, Sidon Sets, and Dynamic Programming. SIAM J. Discret. Math. 30 (4) (2016)
Stasys Jukna
Tropical Complexity, Sidon Sets, and Dynamic Programming. Electron. Colloquium Comput. Complex. 23 (2016)
Stasys Jukna
Lower Bounds for Monotone Counting Circuits. CoRR (2015)
Stasys Jukna, Georg Schnitger
On the Optimality of Bellman-Ford-Moore Shortest Path Algorithm. Electron. Colloquium Comput. Complex. 22 (2015)
Stasys Jukna
Lower Bounds for Tropical Circuits and Dynamic Programs. Theory Comput. Syst. 57 (1) (2015)
Stasys Jukna
Boolean Function Complexity Advances and Frontiers. Bull. EATCS 113 (2014)
Stasys Jukna
Limitations of Incremental Dynamic Programming. Algorithmica 69 (2) (2014)
Stasys Jukna
Lower Bounds for Tropical Circuits and Dynamic Programs. Electron. Colloquium Comput. Complex. 21 (2014)
Stasys Jukna
Lower Bounds for Tropical Circuits and Dynamic Programs. CoRR (2014)
Stasys Jukna
Lower Bounds for Monotone Counting Circuits. Electron. Colloquium Comput. Complex. 21 (2014)
Stasys Jukna, Igor Sergeev
Complexity of Linear Boolean Operators. Found. Trends Theor. Comput. Sci. 9 (1) (2013)
Stasys Jukna
Independent set problem for individual graphs has small communication complexity CoRR (2012)
Stasys Jukna
Limitations of Incremental Dynamic Programs. Electron. Colloquium Comput. Complex. 19 (2012)
Stasys Jukna
Clique Problem, Cutting Plane Proofs, and Communication Complexity. Electron. Colloquium Comput. Complex. 19 (2012)
Stasys Jukna
Clique problem, cutting plane proofs and communication complexity. Inf. Process. Lett. 112 (20) (2012)
Stasys Jukna, Georg Schnitger
Cutting planes cannot approximate some integer programs. Oper. Res. Lett. 40 (4) (2012)
Stasys Jukna, Georg Schnitger
Min-rank conjecture for log-depth circuits. J. Comput. Syst. Sci. 77 (6) (2011)
Stasys Jukna, Georg Schnitger
Yet harder knapsack problems. Theor. Comput. Sci. 412 (45) (2011)
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
On convex complexity measures. Theor. Comput. Sci. 411 (16-18) (2010)
Stasys Jukna, Georg Schnitger
Circuits with arbitrary gates for random operators CoRR (2010)
Stasys Jukna
Representing (0, 1)-matrices by boolean circuits. Discret. Math. 310 (1) (2010)
Stasys Jukna, Georg Schnitger
Min-Rank Conjecture for Log-Depth Circuits CoRR (2010)
Stasys Jukna
Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits. Theory Comput. Syst. 46 (2) (2010)
Stasys Jukna, Alexander S. Kulikov
On covering graphs by complete bipartite subgraphs. Discret. Math. 309 (10) (2009)
Stasys Jukna
On set intersection representations of graphs. J. Graph Theory 61 (1) (2009)
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
On convex complexity measures. Electron. Colloquium Comput. Complex. 16 (2009)
Stasys Jukna
A nondeterministic space-time tradeoff for linear codes. Inf. Process. Lett. 109 (5) (2009)
Stasys Jukna, Georg Schnitger
Min-Rank Conjecture for Log-Depth Circuits. Electron. Colloquium Comput. Complex. 16 (2009)
Stasys Jukna
Expanders and time-restricted branching programs. Theor. Comput. Sci. 409 (3) (2008)
Alexander E. Andreev, Stasys Jukna
Very large cliques are easy to detect. Discret. Math. 308 (16) (2008)
Stasys Jukna
Entropy of operators or why matrix multiplication is hard for small depth circuits. Electron. Colloquium Comput. Complex. 15 (019) (2008)
Alexander E. Andreev, Stasys Jukna
Very Large Cliques are Easy to Detect. Complexity of Boolean Functions (2006)
Stasys Jukna
Disproving the Single Level Conjecture. SIAM J. Comput. 36 (1) (2006)
Stasys Jukna
Graphs and Circuits: Some Further Remarks. Complexity of Boolean Functions (2006)
Stasys Jukna
On Graph Complexity. Comb. Probab. Comput. 15 (6) (2006)
Stasys Jukna
Expanders and time-restricted branching programs Electron. Colloquium Comput. Complex. (079) (2005)
Stasys Jukna
Disproving the single level conjecture Electron. Colloquium Comput. Complex. (021) (2005)
Stasys Jukna
On the P versus NP intersected with co-NP question in communication complexity. Inf. Process. Lett. 96 (6) (2005)
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
On multi-partition communication complexity. Inf. Comput. 194 (1) (2004)
Stasys Jukna
On Graph Complexity Electron. Colloquium Comput. Complex. (005) (2004)
Stasys Jukna
On the minimum number of negations leading to super-polynomial savings. Inf. Process. Lett. 89 (2) (2004)
Stasys Jukna
A note on the P versus NP intersected with co-NP question in communication complexity Electron. Colloquium Comput. Complex. (062) (2004)
Stasys Jukna, Stanislav Zák
On uncertainty versus size in branching programs. Theor. Comput. Sci. 290 (3) (2003)
Stasys Jukna, Georg Schnitger
Triangle-Freeness Is Hard To Detect. Comb. Probab. Comput. 11 (6) (2002)
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
On Multipartition Communication Complexity. STACS (2001)
Stasys Jukna, Georg Schnitger
On Multi-Partition Communication Complexity of Triangle-Freeness Electron. Colloquium Comput. Complex. 8 (49) (2001)
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
On Multipartition Communication Complexity Electron. Colloquium Comput. Complex. 8 (066) (2001)
Stasys Jukna, Stanislav Zák
On Uncertainty versus Size in Branching Programs Electron. Colloquium Comput. Complex. 8 (39) (2001)
Stasys Jukna
A Note on the Minimum Number of Negations Leading to Superpolynomial Savings Electron. Colloquium Comput. Complex. 8 (058) (2001)
Stasys Jukna, Stanislav Zák
Some Notes on the Information Flow in Read-Once Branching Programs. SOFSEM (2000)
Stasys Jukna
Linear Codes are Hard for Oblivious Read-Once Parity Branching Programs. Inf. Process. Lett. 69 (6) (1999)
Stasys Jukna
Combinatorics of Monotone Computations. Comb. 19 (1) (1999)
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
On P versus NP cap co-NP for decision trees and read-once branching programs. Comput. Complex. 8 (4) (1999)
Stasys Jukna
Combinatorics of Monotone Computations Electron. Colloquium Comput. Complex. 5 (41) (1998)
Carsten Damm, Stasys Jukna, Jirí Sgall
Some Bounds on Multiparty Communication Complexity of Pointer Jumping. Comput. Complex. 7 (2) (1998)
Stasys Jukna, Stanislav Zák
On Branching Programs With Bounded Uncertainty Electron. Colloquium Comput. Complex. 5 (30) (1998)
Stasys Jukna, Stanislav Zák
On Branching Programs With Bounded Uncertainty (Extended Abstract). ICALP (1998)
Stasys Jukna, Alexander A. Razborov
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much. Discret. Appl. Math. 85 (3) (1998)
Stasys Jukna
Finite Limits and Monotone Computations: The Lower Bounds Criterion. Computational Complexity Conference (1997)
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs Electron. Colloquium Comput. Complex. 4 (23) (1997)
Stasys Jukna
Exponential Lower Bounds for Semantic Resolution Electron. Colloquium Comput. Complex. 4 (7) (1997)
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)
Stasys Jukna, Alexander A. Razborov
Neither Reading Few Bits Twice nor Reading Illegally Helps Much Electron. Colloquium Comput. Complex. 3 (37) (1996)
Carsten Damm, Stasys Jukna, Jirí Sgall
Some Bounds on Multiparty Communication Complexity of Pointer Jumping. STACS (1996)
Stasys Jukna
Finite Limits and Monotone Computations Electron. Colloquium Comput. Complex. 3 (26) (1996)
Stasys Jukna
Exponential lower bounds for semantic resolution. Proof Complexity and Feasible Arithmetics (1996)
Stasys Jukna
On Communication Games with More than Two Players Universität Trier, Mathematik/Informatik, Forschungsbericht (1995)
Stasys Jukna
Times Branching Programs. RAIRO Theor. Informatics Appl. 29 (1) (1995)
Carsten Damm, Stasys Jukna, Jirí Sgall
Some Bounds on Multiparty Communication Complexity of Pointer Jumping Universität Trier, Mathematik/Informatik, Forschungsbericht (1995)
Carsten Damm, Stasys Jukna, Jirí Sgall
Some Bounds on Multiparty Communication Complexity of Pointer Jumping Electron. Colloquium Comput. Complex. 2 (44) (1995)
Johan Håstad, Stasys Jukna, Pavel Pudlák
Top-Down Lower Bounds for Depth-Three Circuits. Comput. Complex. 5 (2) (1995)

Stasys Jukna.css-eqlu8i{font-size:small;padding-left:4px;}

Publication Activity (10 Years)

Top Topics

Top Venues

Stasys Jukna