×

zbMATH — the first resource for mathematics

Yukna, Stasys P.

Compute Distance To:
Author ID: yukna.stasys-p Recent zbMATH articles by "Yukna, Stasys P."
Published as: Jukna, S.; Jukna, S. P.; Jukna, Stasys; Jukna, Stasys P.; Yukna, S.; Yukna, S. I.; Yukna, S. P.; Yukna, Stasys; Yukna, Stasys P.
Documents Indexed: 69 Publications since 1979, including 4 Books
Reviewing Activity: 68 Reviews

Publications by Year

Citations contained in zbMATH

39 Publications have been cited 311 times in 252 Documents Cited by Year
Extremal combinatorics. With applications in computer science. Zbl 0978.05001
Jukna, Stasys
52
2001
Boolean function complexity. Advances and frontiers. Zbl 1235.94005
Jukna, Stasys
51
2012
Extremal combinatorics. With applications in computer science. 2nd ed. Zbl 1239.05001
Jukna, Stasys
34
2011
A note on read-\(k\) times branching programs. Zbl 0889.68021
Jukna, Stasys
23
1995
Neither reading few bits twice nor reading illegally helps much. Zbl 0903.68074
Jukna, S.; Razborov, A.
13
1998
Entropy of contact circuits and lower bounds on their complexity. Zbl 0655.94020
Jukna, Stasys P.
13
1988
Top-down lower bounds for depth-three circuits. Zbl 0838.68056
Håstad, Johan; Jukna, S.; Pudlák, P.
12
1995
On covering graphs by complete bipartite subgraphs. Zbl 1218.05136
Jukna, S.; Kulikov, A. S.
11
2009
On graph complexity. Zbl 1160.68480
Jukna, S.
10
2006
On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs. Zbl 0962.68075
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
10
1999
On set intersection representations of graphs. Zbl 1211.05086
Jukna, Stasys
9
2009
Lower bounds for tropical circuits and dynamic programs. Zbl 1320.68093
Jukna, Stasys
7
2015
On multi-partition communication complexity. Zbl 1073.68030
Ďuriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
5
2004
Combinatorics of monotone computations. Zbl 0962.03030
Jukna, Stasys
5
1999
Complexity of linear Boolean operators. Zbl 1280.68004
Jukna, Stasys; Sergeev, Igor
4
2013
Some bounds on multiparty communication complexity of pointer jumping. Zbl 0912.68052
Damm, Carsten; Jukna, Stasys; Sgall, Jiří
4
1998
On P versus \(\text{NP}\cap co-\text{NP}\) for decision trees and read-once branching programs. Zbl 0941.68062
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
4
1997
The effect of null-chains on the complexity of contact schemes. Zbl 0728.94012
Jukna, Stasys P.
4
1989
Lower bounds on the complexity of local circuits. Zbl 0609.94018
Jukna, S. P.
4
1986
Tropical complexity, Sidon sets, and dynamic programming. Zbl 1353.68103
Jukna, Stasys
3
2016
Entropy of operators or why matrix multiplication is hard for depth-two circuits. Zbl 1209.68280
Jukna, Stasys
3
2010
On convex complexity measures. Zbl 1192.68295
Hrubeš, P.; Jukna, S.; Kulikov, A.; Pudlák, P.
3
2010
Linear codes are hard for oblivious read-once parity branching programs. Zbl 1002.68054
Jukna, Stasys
3
1999
Greedy can beat pure dynamic programming. Zbl 06989096
Jukna, Stasys; Seiwert, Hannes
2
2019
A nondeterministic space-time tradeoff for linear codes. Zbl 1192.94126
Jukna, S.
2
2009
Expanders and time-restricted branching programs. Zbl 1155.68056
Jukna, Stasys
2
2008
Disproving the single level conjecture. Zbl 1113.94013
Jukna, Stasys
2
2006
Triangle-freeness is hard to detect. Zbl 1013.05033
Jukna, S.; Schnitger, G.
2
2002
Exponential lower bounds for semantic resolution. Zbl 0890.03032
Jukna, Stasys
2
1998
Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates. Zbl 0875.94139
Jukna, Stasys
2
1995
On the characterization problem of partial correctness theories of programs. Zbl 0413.68011
Yukna, S.
2
1979
On the optimality of Bellman-Ford-Moore shortest path algorithm. Zbl 1339.90327
Jukna, Stasys; Schnitger, Georg
1
2016
Limitations of incremental dynamic programming. Zbl 1360.90269
Jukna, Stasys
1
2014
On the P versus NP intersected with co-NP question in communication complexity. Zbl 1184.68265
Jukna, Stasys
1
2005
On the minimum number of negations leading to super-polynomial savings. Zbl 1178.68283
Jukna, Stasys
1
2004
On multipartition communication complexity (extended abstract). Zbl 0976.68514
Duriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
1
2001
Some notes on the information flow in read-once branching programs. Zbl 1043.68557
Jukna, Stasys; Žák, Stanislav
1
2000
Some bounds on multiparty communication complexity of pointer jumping. Zbl 1379.68128
Damm, Carsten; Jukna, Stasys; Sgall, Jiří
1
1996
Arithmetical representations of machine complexity classes. Zbl 0515.68045
Yukna, S.
1
1982
Greedy can beat pure dynamic programming. Zbl 06989096
Jukna, Stasys; Seiwert, Hannes
2
2019
Tropical complexity, Sidon sets, and dynamic programming. Zbl 1353.68103
Jukna, Stasys
3
2016
On the optimality of Bellman-Ford-Moore shortest path algorithm. Zbl 1339.90327
Jukna, Stasys; Schnitger, Georg
1
2016
Lower bounds for tropical circuits and dynamic programs. Zbl 1320.68093
Jukna, Stasys
7
2015
Limitations of incremental dynamic programming. Zbl 1360.90269
Jukna, Stasys
1
2014
Complexity of linear Boolean operators. Zbl 1280.68004
Jukna, Stasys; Sergeev, Igor
4
2013
Boolean function complexity. Advances and frontiers. Zbl 1235.94005
Jukna, Stasys
51
2012
Extremal combinatorics. With applications in computer science. 2nd ed. Zbl 1239.05001
Jukna, Stasys
34
2011
Entropy of operators or why matrix multiplication is hard for depth-two circuits. Zbl 1209.68280
Jukna, Stasys
3
2010
On convex complexity measures. Zbl 1192.68295
Hrubeš, P.; Jukna, S.; Kulikov, A.; Pudlák, P.
3
2010
On covering graphs by complete bipartite subgraphs. Zbl 1218.05136
Jukna, S.; Kulikov, A. S.
11
2009
On set intersection representations of graphs. Zbl 1211.05086
Jukna, Stasys
9
2009
A nondeterministic space-time tradeoff for linear codes. Zbl 1192.94126
Jukna, S.
2
2009
Expanders and time-restricted branching programs. Zbl 1155.68056
Jukna, Stasys
2
2008
On graph complexity. Zbl 1160.68480
Jukna, S.
10
2006
Disproving the single level conjecture. Zbl 1113.94013
Jukna, Stasys
2
2006
On the P versus NP intersected with co-NP question in communication complexity. Zbl 1184.68265
Jukna, Stasys
1
2005
On multi-partition communication complexity. Zbl 1073.68030
Ďuriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
5
2004
On the minimum number of negations leading to super-polynomial savings. Zbl 1178.68283
Jukna, Stasys
1
2004
Triangle-freeness is hard to detect. Zbl 1013.05033
Jukna, S.; Schnitger, G.
2
2002
Extremal combinatorics. With applications in computer science. Zbl 0978.05001
Jukna, Stasys
52
2001
On multipartition communication complexity (extended abstract). Zbl 0976.68514
Duriš, Pavol; Hromkovič, Juraj; Jukna, Stasys; Sauerhoff, Martin; Schnitger, Georg
1
2001
Some notes on the information flow in read-once branching programs. Zbl 1043.68557
Jukna, Stasys; Žák, Stanislav
1
2000
On P versus NP\(\cap\)co-NP for decision trees and read-once branching programs. Zbl 0962.68075
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
10
1999
Combinatorics of monotone computations. Zbl 0962.03030
Jukna, Stasys
5
1999
Linear codes are hard for oblivious read-once parity branching programs. Zbl 1002.68054
Jukna, Stasys
3
1999
Neither reading few bits twice nor reading illegally helps much. Zbl 0903.68074
Jukna, S.; Razborov, A.
13
1998
Some bounds on multiparty communication complexity of pointer jumping. Zbl 0912.68052
Damm, Carsten; Jukna, Stasys; Sgall, Jiří
4
1998
Exponential lower bounds for semantic resolution. Zbl 0890.03032
Jukna, Stasys
2
1998
On P versus \(\text{NP}\cap co-\text{NP}\) for decision trees and read-once branching programs. Zbl 0941.68062
Jukna, S.; Razborov, A.; Savický, P.; Wegener, I.
4
1997
Some bounds on multiparty communication complexity of pointer jumping. Zbl 1379.68128
Damm, Carsten; Jukna, Stasys; Sgall, Jiří
1
1996
A note on read-\(k\) times branching programs. Zbl 0889.68021
Jukna, Stasys
23
1995
Top-down lower bounds for depth-three circuits. Zbl 0838.68056
Håstad, Johan; Jukna, S.; Pudlák, P.
12
1995
Computing threshold functions by depth-3 threshold circuits with smaller thresholds of their gates. Zbl 0875.94139
Jukna, Stasys
2
1995
The effect of null-chains on the complexity of contact schemes. Zbl 0728.94012
Jukna, Stasys P.
4
1989
Entropy of contact circuits and lower bounds on their complexity. Zbl 0655.94020
Jukna, Stasys P.
13
1988
Lower bounds on the complexity of local circuits. Zbl 0609.94018
Jukna, S. P.
4
1986
Arithmetical representations of machine complexity classes. Zbl 0515.68045
Yukna, S.
1
1982
On the characterization problem of partial correctness theories of programs. Zbl 0413.68011
Yukna, S.
2
1979
all top 5

Cited by 399 Authors

25 Yukna, Stasys P.
9 Göös, Mika
6 Pitassi, Toniann
5 Bollig, Beate
5 Razborov, Aleksandr Aleksandrovich
5 Schnitger, Georg
5 Watson, Thomas C.
4 Find, Magnus Gausdal
4 Kochergin, Vadim Vasil’evich
4 Mikhailovich, Anna Vital’evna
4 Podol’skiĭ, Vladimir Vladimirovich
4 Sauerhoff, Martin
4 Sergeev, Igor S.
4 Sieling, Detlef
4 Wigderson, Avi
3 Alon, Noga M.
3 Amano, Kazuyuki
3 Boyar, Joan F.
3 Dehmer, Matthias
3 Farràs, Oriol
3 Gál, Anna
3 Gutin, Gregory Z.
3 Král’, Daniel
3 Kulikov, Alexander S.
3 Mathew, Rogers
3 Meesum, Syed Mohammad
3 Meir, Or
3 Mowshowitz, Abbe
3 Raz, Ran
3 Saurabh, Saket
3 Savický, Petr
3 Seiwert, Hannes
3 Sherstov, Alexander A.
3 Wegener, Ingo
3 Yeo, Anders
3 Yukna, Stasis
2 Ablaev, Farid M.
2 Aw, Alan J.
2 Balachandran, Niranjan
2 Beimel, Amos
2 Bury, Marc
2 Cherkashin, Danila D.
2 Colbourn, Charles J.
2 De Bonis, Annalisa
2 Dinesh, Krishnamoorthy
2 Duginov, O. I.
2 Frankl, Péter
2 Grigorescu, Elena
2 Guo, Siyao
2 Homeister, Matthias
2 Hromkovič, Juraj
2 Hrubeš, Pavel
2 Impagliazzo, Russell
2 Itsykson, Dmitry M.
2 Järvisalo, Matti
2 Kabanets, Valentine
2 Karpinski, Marek
2 Komargodski, Ilan
2 Krause, Matthias
2 Lepin, V. V.
2 Lovett, Shachar
2 Marques de Sá, Eduardo
2 Meka, Raghu
2 Mishra, Tapas Kumar
2 Moazami, Farokhlagha
2 Mubayi, Dhruv
2 Paturi, Ramamohan
2 Pudlák, Pavel
2 Razgon, Igor
2 Rossman, Benjamin
2 Sarkar, Kaushik
2 Sarma M. N., Jayalal
2 Servedio, Rocco A.
2 Sorge, Manuel
2 Tardos, Gábor
2 Turán, Gyorgy
2 Vaccaro, Ugo
2 Watson, Thomas Michael
2 Wimmer, Karl
2 Yehudayoff, Amir
2 Zak, Stanislav
2 Zhao, Yi
2 Zuckerman, David
1 Adiga, Abhijin
1 Akama, Yohji
1 Akbari, Saieed
1 Alm, Jeremy F.
1 Anthony, Martin H. G.
1 Aspnes, James
1 Balaji, Nikhil
1 Balogh, József
1 Barani, Ahmad
1 Beame, Paul W.
1 Beldiceanu, Nicolas
1 Ben-Eliezer, Ido
1 Bernasconi, Anna
1 Blakeley, Brandon
1 Blanchet-Sadri, Francine
1 Blum, Norbert
1 Bollobás, Béla
...and 299 more Authors
all top 5

Cited in 65 Serials

33 Theoretical Computer Science
21 Information Processing Letters
18 Journal of Computer and System Sciences
13 Theory of Computing Systems
11 SIAM Journal on Computing
11 Computational Complexity
10 Discrete Mathematics
9 Discrete Applied Mathematics
7 Algorithmica
6 European Journal of Combinatorics
5 Combinatorica
5 Information and Computation
4 Journal of Combinatorial Theory. Series A
4 Graphs and Combinatorics
4 SIAM Journal on Discrete Mathematics
4 Designs, Codes and Cryptography
4 The Electronic Journal of Combinatorics
3 Discrete Mathematics and Applications
3 Linear Algebra and its Applications
3 Journal of Discrete Algorithms
2 Artificial Intelligence
2 Lithuanian Mathematical Journal
2 Mathematical Notes
2 Applied Mathematics and Computation
2 Journal of Graph Theory
2 Operations Research Letters
2 Discrete & Computational Geometry
2 Random Structures & Algorithms
2 Computational Geometry
2 International Journal of Foundations of Computer Science
2 Distributed Computing
2 RAIRO. Informatique Théorique et Applications
2 Trudy Instituta Matematiki
2 Diskretnyĭ Analiz i Issledovanie Operatsiĭ
1 Russian Mathematical Surveys
1 Algebra Universalis
1 Journal of Soviet Mathematics
1 Kybernetika
1 Mathematika
1 Topology and its Applications
1 Annals of Pure and Applied Logic
1 Bulletin of the Iranian Mathematical Society
1 International Journal of Approximate Reasoning
1 Journal of the American Mathematical Society
1 Journal of Cryptology
1 Games and Economic Behavior
1 Elemente der Mathematik
1 Bulletin of the American Mathematical Society. New Series
1 Mathematical Programming. Series A. Series B
1 Russian Mathematics
1 Journal of Algebraic Combinatorics
1 Combinatorics, Probability and Computing
1 Journal of Mathematical Sciences (New York)
1 Advances in Computational Mathematics
1 Annals of Mathematics and Artificial Intelligence
1 Constraints
1 Mathematical Problems in Engineering
1 Journal of Combinatorial Optimization
1 Diskretnyĭ Analiz i Issledovanie Operatsiĭ. Seriya 1
1 RAIRO. Theoretical Informatics and Applications
1 Quantum Information Processing
1 Sibirskie Èlektronnye Matematicheskie Izvestiya
1 Mathematics in Computer Science
1 Algorithms
1 Cryptography and Communications

Citations by Year