Stasys Jukna

116 papers A* 2A 4B 7Journal 96Unranked 3
YearRankTypeTitle / Venue / Authors
2022 J jnl
Lower bounds for Boolean circuits of bounded negation width.
J. Comput. Syst. Sci.
Stasys Jukna, Andrzej Lingas
2022 J jnl
Notes on Boolean Read-k and Multilinear Circuits.
CoRR
Stasys Jukna
2022 J jnl
Notes on Monotone Read-k Circuits.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2021 J jnl
Notes on Hazard-Free Circuits.
SIAM J. Discret. Math.
Stasys Jukna
2021 J jnl
Tropical Kirchhoff's formula and postoptimality in matroid optimization.
Discret. Appl. Math.
Stasys Jukna, Hannes Seiwert
2020 J jnl
Approximation Limitations of Pure Dynamic Programming.
CoRR
Stasys Jukna, Hannes Seiwert
2020 J jnl
Approximation Limitations of Pure Dynamic Programming.
SIAM J. Comput.
Stasys Jukna, Hannes Seiwert
2020 J jnl
Coin Flipping in Dynamic Programming Is Almost Useless.
ACM Trans. Comput. Theory
Stasys Jukna
2020 J jnl
Coin Flipping in Dynamic Programming is Almost Useless.
CoRR
Stasys Jukna
2020 J jnl
Notes on Hazard-Free Circuits.
CoRR
Stasys Jukna
2020 J jnl
Notes on Hazard-Free Circuits.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2020 J jnl
Reciprocal Inputs in Arithmetic and Tropical Circuits.
Electron. Colloquium Comput. Complex.
Stasys Jukna, Hannes Seiwert, Igor Sergeev
2020 J jnl
Sorting Can Exponentially Speed Up Pure Dynamic Programming.
CoRR
Stasys Jukna, Hannes Seiwert
2020 J jnl
Sorting can exponentially speed up pure dynamic programming.
Inf. Process. Lett.
Stasys Jukna, Hannes Seiwert
2020 J jnl
Tropical Kirchhoff's Formula and Postoptimality in Matroid Optimization.
CoRR
Stasys Jukna, Hannes Seiwert
2019 J jnl
Coin Flipping Cannot Shorten Arithmetic Computations.
Am. Math. Mon.
Stasys Jukna
2019 J jnl
Greedy can beat pure dynamic programming.
Inf. Process. Lett.
Stasys Jukna, Hannes Seiwert
2019 A conf
Lower Bounds for DeMorgan Circuits of Bounded Negation Width.
STACS
Stasys Jukna, Andrzej Lingas
2019 J jnl
Sorting Can Exponentially Speed Up Pure Dynamic Programming.
Electron. Colloquium Comput. Complex.
Stasys Jukna, Hannes Seiwert
2018 J jnl
Approximation Limitations of Tropical Circuits.
Electron. Colloquium Comput. Complex.
Stasys Jukna, Hannes Seiwert
2018 J jnl
Derandomizing Dynamic Programming and Beyond.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2018 J jnl
Greedy can also beat pure dynamic programming.
CoRR
Stasys Jukna, Hannes Seiwert
2018 J jnl
Greedy can also beat pure dynamic programming.
Electron. Colloquium Comput. Complex.
Stasys Jukna, Hannes Seiwert
2018 J jnl
Incremental versus Non-Incremental Dynamic Programming.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2018 J jnl
Incremental versus non-incremental dynamic programming.
Oper. Res. Lett.
Stasys Jukna
2018 J jnl
Lower Bounds for Circuits of Bounded Negation Width.
Electron. Colloquium Comput. Complex.
Stasys Jukna, Andrzej Lingas
2017 J jnl
Minkowski Complexity of Sets: An Easy Lower Bound.
Am. Math. Mon.
Stasys Jukna
2016 J jnl
Lower bounds for monotone counting circuits.
Discret. Appl. Math.
Stasys Jukna
2016 J jnl
On the optimality of Bellman-Ford-Moore shortest path algorithm.
Theor. Comput. Sci.
Stasys Jukna, Georg Schnitger
2016 J jnl
Tropical Complexity, Sidon Sets, and Dynamic Programming.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2016 J jnl
Tropical Complexity, Sidon Sets, and Dynamic Programming.
SIAM J. Discret. Math.
Stasys Jukna
2015 J jnl
Lower Bounds for Monotone Counting Circuits.
CoRR
Stasys Jukna
2015 J jnl
Lower Bounds for Tropical Circuits and Dynamic Programs.
Theory Comput. Syst.
Stasys Jukna
2015 J jnl
On the Optimality of Bellman-Ford-Moore Shortest Path Algorithm.
Electron. Colloquium Comput. Complex.
Stasys Jukna, Georg Schnitger
2014 J jnl
Boolean Function Complexity Advances and Frontiers.
Bull. EATCS
Stasys Jukna
2014 J jnl
Limitations of Incremental Dynamic Programming.
Algorithmica
Stasys Jukna
2014 J jnl
Lower Bounds for Monotone Counting Circuits.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2014 J jnl
Lower Bounds for Tropical Circuits and Dynamic Programs.
CoRR
Stasys Jukna
2014 J jnl
Lower Bounds for Tropical Circuits and Dynamic Programs.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2013 J jnl
Complexity of Linear Boolean Operators.
Found. Trends Theor. Comput. Sci.
Stasys Jukna, Igor Sergeev
2012 — book
Boolean Function Complexity - Advances and Frontiers.
Stasys Jukna
2012 J jnl
Clique Problem, Cutting Plane Proofs, and Communication Complexity.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2012 J jnl
Clique problem, cutting plane proofs and communication complexity.
Inf. Process. Lett.
Stasys Jukna
2012 J jnl
Cutting planes cannot approximate some integer programs.
Oper. Res. Lett.
Stasys Jukna, Georg Schnitger
2012 J jnl
Independent set problem for individual graphs has small communication complexity
CoRR
Stasys Jukna
2012 J jnl
Limitations of Incremental Dynamic Programs.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2011 — book
Extremal Combinatorics - With Applications in Computer Science
Stasys Jukna
2011 J jnl
Min-rank conjecture for log-depth circuits.
J. Comput. Syst. Sci.
Stasys Jukna, Georg Schnitger
2011 J jnl
Yet harder knapsack problems.
Theor. Comput. Sci.
Stasys Jukna, Georg Schnitger
2010 J jnl
Circuits with arbitrary gates for random operators
CoRR
Stasys Jukna, Georg Schnitger
2010 J jnl
Entropy of Operators or why Matrix Multiplication is Hard for Depth-Two Circuits.
Theory Comput. Syst.
Stasys Jukna
2010 J jnl
Min-Rank Conjecture for Log-Depth Circuits
CoRR
Stasys Jukna, Georg Schnitger
2010 J jnl
On convex complexity measures.
Theor. Comput. Sci.
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
2010 J jnl
Representing (0, 1)-matrices by boolean circuits.
Discret. Math.
Stasys Jukna
2009 J jnl
A nondeterministic space-time tradeoff for linear codes.
Inf. Process. Lett.
Stasys Jukna
2009 J jnl
Min-Rank Conjecture for Log-Depth Circuits.
Electron. Colloquium Comput. Complex.
Stasys Jukna, Georg Schnitger
2009 J jnl
On convex complexity measures.
Electron. Colloquium Comput. Complex.
Pavel Hrubes, Stasys Jukna, Alexander S. Kulikov, Pavel Pudlák
2009 J jnl
On covering graphs by complete bipartite subgraphs.
Discret. Math.
Stasys Jukna, Alexander S. Kulikov
2009 J jnl
On set intersection representations of graphs.
J. Graph Theory
Stasys Jukna
2008 — book
Crashkurs Mathematik für Informatiker.
Stasys Jukna
2008 J jnl
Entropy of operators or why matrix multiplication is hard for small depth circuits.
Electron. Colloquium Comput. Complex.
Stasys Jukna
2008 J jnl
Expanders and time-restricted branching programs.
Theor. Comput. Sci.
Stasys Jukna
2008 J jnl
Very large cliques are easy to detect.
Discret. Math.
Alexander E. Andreev, Stasys Jukna
2006 J jnl
Disproving the Single Level Conjecture.
SIAM J. Comput.
Stasys Jukna
2006 — conf
Graphs and Circuits: Some Further Remarks.
Complexity of Boolean Functions
Stasys Jukna
2006 J jnl
On Graph Complexity.
Comb. Probab. Comput.
Stasys Jukna
2006 — conf
Very Large Cliques are Easy to Detect.
Complexity of Boolean Functions
Alexander E. Andreev, Stasys Jukna
2005 J jnl
Disproving the single level conjecture
Electron. Colloquium Comput. Complex.
Stasys Jukna
2005 J jnl
Expanders and time-restricted branching programs
Electron. Colloquium Comput. Complex.
Stasys Jukna
2005 J jnl
On the P versus NP intersected with co-NP question in communication complexity.
Inf. Process. Lett.
Stasys Jukna
2004 J jnl
A note on the P versus NP intersected with co-NP question in communication complexity
Electron. Colloquium Comput. Complex.
Stasys Jukna
2004 J jnl
On Graph Complexity
Electron. Colloquium Comput. Complex.
Stasys Jukna
2004 J jnl
On multi-partition communication complexity.
Inf. Comput.
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2004 J jnl
On the minimum number of negations leading to super-polynomial savings.
Inf. Process. Lett.
Stasys Jukna
2003 J jnl
On uncertainty versus size in branching programs.
Theor. Comput. Sci.
Stasys Jukna, Stanislav Zák
2002 J jnl
Triangle-Freeness Is Hard To Detect.
Comb. Probab. Comput.
Stasys Jukna, Georg Schnitger
2001 J jnl
A Note on the Minimum Number of Negations Leading to Superpolynomial Savings
Electron. Colloquium Comput. Complex.
Stasys Jukna
2001 — book
Extremal Combinatorics - With Applications in Computer Science.
Stasys Jukna
2001 J jnl
On Multi-Partition Communication Complexity of Triangle-Freeness
Electron. Colloquium Comput. Complex.
Stasys Jukna, Georg Schnitger
2001 J jnl
On Multipartition Communication Complexity
Electron. Colloquium Comput. Complex.
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2001 A conf
On Multipartition Communication Complexity.
STACS
Pavol Duris, Juraj Hromkovic, Stasys Jukna, Martin Sauerhoff, Georg Schnitger
2001 J jnl
On Uncertainty versus Size in Branching Programs
Electron. Colloquium Comput. Complex.
Stasys Jukna, Stanislav Zák
2000 B conf
Some Notes on the Information Flow in Read-Once Branching Programs.
SOFSEM
Stasys Jukna, Stanislav Zák
1999 J jnl
Combinatorics of Monotone Computations.
Comb.
Stasys Jukna
1999 J jnl
Linear Codes are Hard for Oblivious Read-Once Parity Branching Programs.
Inf. Process. Lett.
Stasys Jukna
1999 J jnl
On P versus NP cap co-NP for decision trees and read-once branching programs.
Comput. Complex.
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
1998 J jnl
Combinatorics of Monotone Computations
Electron. Colloquium Comput. Complex.
Stasys Jukna
1998 J jnl
Neither Reading Few Bits Twice Nor Reading Illegally Helps Much.
Discret. Appl. Math.
Stasys Jukna, Alexander A. Razborov
1998 J jnl
On Branching Programs With Bounded Uncertainty
Electron. Colloquium Comput. Complex.
Stasys Jukna, Stanislav Zák
1998 A* conf
On Branching Programs With Bounded Uncertainty (Extended Abstract).
ICALP
Stasys Jukna, Stanislav Zák
1998 J jnl
Some Bounds on Multiparty Communication Complexity of Pointer Jumping.
Comput. Complex.
Carsten Damm, Stasys Jukna, Jirí Sgall
1997 J jnl
Exponential Lower Bounds for Semantic Resolution
Electron. Colloquium Comput. Complex.
Stasys Jukna
1997 A conf
Finite Limits and Monotone Computations: The Lower Bounds Criterion.
CCC
Stasys Jukna
1997 B conf
On O versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs.
MFCS
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
1997 J jnl
On P versus NP \cap co-NP for Decision Trees and Read-Once Branching Programs
Electron. Colloquium Comput. Complex.
Stasys Jukna, Alexander A. Razborov, Petr Savický, Ingo Wegener
1996 — conf
Exponential lower bounds for semantic resolution.
Proof Complexity and Feasible Arithmetics
Stasys Jukna
1996 J jnl
Finite Limits and Monotone Computations
Electron. Colloquium Comput. Complex.
Stasys Jukna
1996 J jnl
Neither Reading Few Bits Twice nor Reading Illegally Helps Much
Electron. Colloquium Comput. Complex.
Stasys Jukna, Alexander A. Razborov
1996 A conf
Some Bounds on Multiparty Communication Complexity of Pointer Jumping.
STACS
Carsten Damm, Stasys Jukna, Jirí Sgall
1995 J jnl
A Note on Read-
RAIRO Theor. Informatics Appl.
Stasys Jukna
1995 J jnl
Computing Threshold Functions by Depth-3 Threshold Circuits with Smaller Thresholds of Their Gates.
Inf. Process. Lett.
Stasys Jukna
1995 J jnl
On Communication Games with More than Two Players
Universität Trier, Mathematik/Informatik, Forschungsbericht
Stasys Jukna
1995 J jnl
On Multiparity Games for Pointer Jumping
Universität Trier, Mathematik/Informatik, Forschungsbericht
Carsten Damm, Stasys Jukna
1995 J jnl
Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Electron. Colloquium Comput. Complex.
Carsten Damm, Stasys Jukna, Jirí Sgall
1995 J jnl
Some Bounds on Multiparty Communication Complexity of Pointer Jumping
Universität Trier, Mathematik/Informatik, Forschungsbericht
Carsten Damm, Stasys Jukna, Jirí Sgall
1995 J jnl
The Graph of Integer Multiplication is Hard for Read-k-Times Networks
Universität Trier, Mathematik/Informatik, Forschungsbericht
Stasys Jukna
1995 J jnl
Top-Down Lower Bounds for Depth-Three Circuits.
Comput. Complex.
Johan Håstad, Stasys Jukna, Pavel Pudlák
1994 J jnl
A Note on Read-k Times Branching Programs
Electron. Colloquium Comput. Complex.
Stasys Jukna
1994 J jnl
Finite Limits and Lower Bounds for Circuits Size
Universität Trier, Mathematik/Informatik, Forschungsbericht
Stasys Jukna
1993 A* conf
Top-Down Lower Bounds for Depth 3 Circuits
FOCS
Johan Håstad, Stasys Jukna, Pavel Pudlák
1991 B conf
Optimal versus Stable in Boolean Formulae.
FCT
Stasys Jukna
1989 B conf
The Effect of Null-Chains on the Complexity of Contact Schemes.
FCT
Stasys Jukna
1988 J jnl
Entropy of Contact Circuits and Lower Bounds on Their Complexity.
Theor. Comput. Sci.
Stasys Jukna
1988 B conf
Two Lower Bounds for Circuits over the Basis (&, V, -).
MFCS
Stasys Jukna
1987 B conf
Information Flow and Width of Branching Programs (Extended Abstract).
FCT
Stasys Jukna
1986 B conf
Lower Bounds on the Complexity of Local Circuits (Preliminary Report).
MFCS
Stasys Jukna