Stasys Jukna

According to our database, Stasys Jukna authored at least 84 papers between 1986 and 2022.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of three.

2022

Lower bounds for Boolean circuits of bounded negation width.

Stasys Jukna, Andrzej Lingas

J. Comput. Syst. Sci., 2022

Notes on Monotone Read-k Circuits.

Stasys Jukna

Electron. Colloquium Comput. Complex., 2022

Notes on Boolean Read-k and Multilinear Circuits.

Stasys Jukna

CoRR, 2022

2021

Tropical Kirchhoff's formula and postoptimality in matroid optimization.

Stasys Jukna, Hannes Seiwert

Discret. Appl. Math., 2021

2020

Coin Flipping in Dynamic Programming Is Almost Useless.

Stasys Jukna

ACM Trans. Comput. Theory, 2020

Approximation Limitations of Pure Dynamic Programming.

Stasys Jukna, Hannes Seiwert

SIAM J. Comput., 2020

Sorting can exponentially speed up pure dynamic programming.

Stasys Jukna, Hannes Seiwert

Inf. Process. Lett., 2020

Reciprocal Inputs in Arithmetic and Tropical Circuits.

Stasys Jukna, Hannes Seiwert, Igor Sergeev

Electron. Colloquium Comput. Complex., 2020

Notes on Hazard-Free Circuits.

Stasys Jukna

Electron. Colloquium Comput. Complex., 2020

2019

Coin Flipping Cannot Shorten Arithmetic Computations.

Stasys Jukna

Am. Math. Mon., 2019

Greedy can beat pure dynamic programming.

Stasys Jukna, Hannes Seiwert

Inf. Process. Lett., 2019

Lower Bounds for DeMorgan Circuits of Bounded Negation Width.

Stasys Jukna, Andrzej Lingas

Proceedings of the 36th International Symposium on Theoretical Aspects of Computer Science, 2019

2018

Incremental versus non-incremental dynamic programming.

Stasys Jukna

Oper. Res. Lett., 2018

Approximation Limitations of Tropical Circuits.

Stasys Jukna, Hannes Seiwert

Electron. Colloquium Comput. Complex., 2018

Greedy can also beat pure dynamic programming.

Stasys Jukna, Hannes Seiwert

Electron. Colloquium Comput. Complex., 2018

Lower Bounds for Circuits of Bounded Negation Width.

Stasys Jukna, Andrzej Lingas

Electron. Colloquium Comput. Complex., 2018

Derandomizing Dynamic Programming and Beyond.

Stasys Jukna

Electron. Colloquium Comput. Complex., 2018

2017

Minkowski Complexity of Sets: An Easy Lower Bound.

Stasys Jukna

Am. Math. Mon., 2017

2016

On the optimality of Bellman-Ford-Moore shortest path algorithm.

Stasys Jukna, Georg Schnitger

Theor. Comput. Sci., 2016

Tropical Complexity, Sidon Sets, and Dynamic Programming.

Stasys Jukna

Electron. Colloquium Comput. Complex., 2016

Lower bounds for monotone counting circuits.

Stasys Jukna

Discret. Appl. Math., 2016

2014

Lower Bounds for Tropical Circuits and Dynamic Programs.

Stasys Jukna

Electron. Colloquium Comput. Complex., 2014

Boolean Function Complexity Advances and Frontiers.

Stasys Jukna

Bull. EATCS, 2014

Limitations of Incremental Dynamic Programming.

Stasys Jukna

Algorithmica, 2014

2013

Complexity of Linear Boolean Operators.

Stasys Jukna, Igor Sergeev

Found. Trends Theor. Comput. Sci., 2013

2012

Cutting planes cannot approximate some integer programs.

Stasys Jukna, Georg Schnitger

Oper. Res. Lett., 2012

Clique problem, cutting plane proofs and communication complexity.

Stasys Jukna

Inf. Process. Lett., 2012

Limitations of Incremental Dynamic Programs.

Stasys Jukna

Electron. Colloquium Comput. Complex., 2012

Independent set problem for individual graphs has small communication complexity

Stasys Jukna

CoRR, 2012

Boolean Function Complexity - Advances and Frontiers.

Stasys Jukna

Algorithms and combinatorics 27, Springer, ISBN: 978-3-642-24507-7, 2012

2011

Extremal Combinatorics - With Applications in Computer Science

Stasys Jukna

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-642-17364-6, 2011

Yet harder knapsack problems.

Stasys Jukna, Georg Schnitger

Theor. Comput. Sci., 2011

Min-rank conjecture for log-depth circuits.

Stasys Jukna, Georg Schnitger

J. Comput. Syst. Sci., 2011

2010

On convex complexity measures.

Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák

Theor. Comput. Sci., 2010

Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits.

Stasys Jukna

Theory Comput. Syst., 2010

Representing (0, 1)-matrices by boolean circuits.

Stasys Jukna

Discret. Math., 2010

Circuits with arbitrary gates for random operators

Stasys Jukna, Georg Schnitger

CoRR, 2010

2009

On set intersection representations of graphs.

Stasys Jukna

J. Graph Theory, 2009

A nondeterministic space-time tradeoff for linear codes.

Stasys Jukna

Inf. Process. Lett., 2009

On covering graphs by complete bipartite subgraphs.

Stasys Jukna, Alexander S. Kulikov

Discret. Math., 2009

2008

Expanders and time-restricted branching programs.

Stasys Jukna

Theor. Comput. Sci., 2008

Entropy of operators or why matrix multiplication is hard for small depth circuits.

Stasys Jukna

Electron. Colloquium Comput. Complex., 2008

Very large cliques are easy to detect.

Alexander E. Andreev, Stasys Jukna

Discret. Math., 2008

Crashkurs Mathematik für Informatiker.

Stasys Jukna

Leitfäden der Informatik, Teubner, ISBN: 978-3-8351-0216-3, 2008

2006

Disproving the Single Level Conjecture.

Stasys Jukna

SIAM J. Comput., 2006

Graphs and Circuits: Some Further Remarks.

Stasys Jukna

Proceedings of the Complexity of Boolean Functions, 12.03. - 17.03.2006, 2006

2005

On the P versus NP intersected with co-NP question in communication complexity.

Stasys Jukna

Inf. Process. Lett., 2005

2004

On the minimum number of negations leading to super-polynomial savings.

Stasys Jukna

Inf. Process. Lett., 2004

On multi-partition communication complexity.

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

Inf. Comput., 2004

A note on the P versus NP intersected with co-NP question in communication complexity

Stasys Jukna

Electron. Colloquium Comput. Complex., 2004

On Graph Complexity

Stasys Jukna

Electron. Colloquium Comput. Complex., 2004

2003

On uncertainty versus size in branching programs.

Stasys Jukna, Stanislav Zák

Theor. Comput. Sci., 2003

2002

Triangle-Freeness Is Hard To Detect.

Stasys Jukna, Georg Schnitger

Comb. Probab. Comput., 2002

2001

On Multipartition Communication Complexity

Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger

Electron. Colloquium Comput. Complex., 2001

A Note on the Minimum Number of Negations Leading to Superpolynomial Savings

Stasys Jukna

Electron. Colloquium Comput. Complex., 2001

On Multi-Partition Communication Complexity of Triangle-Freeness

Stasys Jukna, Georg Schnitger

Electron. Colloquium Comput. Complex., 2001

Extremal Combinatorics - With Applications in Computer Science.

Stasys Jukna

Texts in Theoretical Computer Science. An EATCS Series, Springer, ISBN: 978-3-662-04650-0, 2001

2000

Some Notes on the Information Flow in Read-Once Branching Programs.

Stasys Jukna, Stanislav Zák

Proceedings of the SOFSEM 2000: Theory and Practice of Informatics, 27th Conference on Current Trends in Theory and Practice of Informatics, Milovy, Czech Republic, November 25, 2000

1999

Linear Codes are Hard for Oblivious Read-Once Parity Branching Programs.

Stasys Jukna

Inf. Process. Lett., 1999

On P versus NP cap co-NP for decision trees and read-once branching programs.

Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener

Comput. Complex., 1999

1998

Combinatorics of Monotone Computations

Stasys Jukna

Electron. Colloquium Comput. Complex., 1998

On Branching Programs With Bounded Uncertainty

Stasys Jukna, Stanislav Zák

Electron. Colloquium Comput. Complex., 1998

Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.

Stasys Jukna, Alexander A. Razborov

Discret. Appl. Math., 1998

Some Bounds on Multiparty Communication Complexity of Pointer Jumping.

Carsten Damm, Stasys Jukna, Jirí Sgall

Comput. Complex., 1998

On Branching Programs With Bounded Uncertainty (Extended Abstract).

Stasys Jukna, Stanislav Zák

Proceedings of the Automata, Languages and Programming, 25th International Colloquium, 1998

1997

Exponential Lower Bounds for Semantic Resolution

Stasys Jukna

Electron. Colloquium Comput. Complex., 1997

On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.

Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener

Proceedings of the Mathematical Foundations of Computer Science 1997, 1997

Finite Limits and Monotone Computations: The Lower Bounds Criterion.

Stasys Jukna

Proceedings of the Twelfth Annual IEEE Conference on Computational Complexity, 1997

1996

Finite Limits and Monotone Computations

Stasys Jukna

Electron. Colloquium Comput. Complex., 1996

1995

On Communication Games with More than Two Players

Stasys Jukna

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

The Graph of Integer Multiplication is Hard for Read-k-Times Networks

Stasys Jukna

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

On Multiparity Games for Pointer Jumping

Carsten Damm, Stasys Jukna

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1995

A Note on Read-<i>k</i> Times Branching Programs.

Stasys Jukna

RAIRO Theor. Informatics Appl., 1995

Computing Threshold Functions by Depth-3 Threshold Circuits with Smaller Thresholds of Their Gates.

Stasys Jukna

Inf. Process. Lett., 1995

Top-Down Lower Bounds for Depth-Three Circuits.

Johan Håstad, Stasys Jukna, Pavel Pudlák

Comput. Complex., 1995

1994

Finite Limits and Lower Bounds for Circuits Size

Stasys Jukna

Universität Trier, Mathematik/Informatik, Forschungsbericht, 1994

A Note on Read-k Times Branching Programs

Stasys Jukna

Electron. Colloquium Comput. Complex., 1994

1993

Top-Down Lower Bounds for Depth 3 Circuits

Johan Håstad, Stasys Jukna, Pavel Pudlák

Proceedings of the 34th Annual Symposium on Foundations of Computer Science, 1993

1991

Optimal versus Stable in Boolean Formulae.

Stasys Jukna

Proceedings of the Fundamentals of Computation Theory, 8th International Symposium, 1991

1989

The Effect of Null-Chains on the Complexity of Contact Schemes.

Stasys Jukna

Proceedings of the Fundamentals of Computation Theory, 1989

1988

Entropy of Contact Circuits and Lower Bounds on Their Complexity.

Stasys Jukna

Theor. Comput. Sci., 1988

Two Lower Bounds for Circuits over the Basis (&, V, -).

Stasys Jukna

Proceedings of the Mathematical Foundations of Computer Science 1988, 1988

1987

Information Flow and Width of Branching Programs (Extended Abstract).

Stasys Jukna

Proceedings of the Fundamentals of Computation Theory, 1987

1986

Lower Bounds on the Complexity of Local Circuits (Preliminary Report).

Stasys Jukna

Proceedings of the Mathematical Foundations of Computer Science 1986, 1986