Search results
- 1.0581950 - MÚ 2024 RIV US eng J - Journal Article
Gavinsky, Dmitry - Lee, T. - Santha, M. - Sanyal, S.
Optimal composition theorem for randomized query complexity.
Theory of Computing. Roč. 19, December (2023), č. článku 9. ISSN 1557-2862. E-ISSN 1557-2862
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : query complexity * randomized decision tree * composed function * lower bound
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 1, year: 2022
Method of publishing: Open access
http://dx.doi.org/10.4086/toc.2021.v017a008
Permanent Link: https://hdl.handle.net/11104/0350086File Download Size Commentary Version Access Gavinsky.pdf 2 510.5 KB Publisher’s postprint open-access - 2.0577240 - MÚ 2024 RIV IL eng J - Journal Article
Hrubeš, Pavel - Yehudayoff, A.
Shadows of Newton polytopes.
Israel Journal of Mathematics. Roč. 256, č. 1 (2023), s. 311-343. ISSN 0021-2172. E-ISSN 1565-8511
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : Newton polytopes * shadow complexity
OECD category: Pure mathematics
Impact factor: 1, year: 2022
Method of publishing: Limited access
https://doi.org/10.1007/s11856-023-2510-z
Permanent Link: https://hdl.handle.net/11104/0346450File Download Size Commentary Version Access Hrubes2.pdf 0 434 KB Publisher’s postprint require - 3.0572825 - MÚ 2024 RIV DE eng J - Journal Article
Hrubeš, Pavel - Talebanfard, Navid
On the extension complexity of polytopes separating subsets of the Boolean cube.
Discrete & Computational Geometry. Roč. 70, č. 1 (2023), s. 268-278. ISSN 0179-5376. E-ISSN 1432-0444
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : Boolean cube * extension complexity * polytopes * sign patterns
OECD category: Pure mathematics
Impact factor: 0.8, year: 2022
Method of publishing: Limited access
https://doi.org/10.1007/s00454-022-00419-3
Permanent Link: https://hdl.handle.net/11104/0343383File Download Size Commentary Version Access Hrubes.pdf 0 292.4 KB Publisher’s postprint require - 4.0561963 - MÚ 2023 RIV HU eng J - Journal Article
Pudlák, Pavel - Rödl, V.
Extractors for small zero-fixing sources.
Combinatorica. Roč. 42, č. 4 (2022), s. 587-616. ISSN 0209-9683. E-ISSN 1439-6912
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : deterministic extracors * graphs
OECD category: Pure mathematics
Impact factor: 1.1, year: 2022
Method of publishing: Limited access
https://doi.org/10.1007/s00493-020-4626-7
Permanent Link: https://hdl.handle.net/11104/0334398File Download Size Commentary Version Access Pudlak1.pdf 2 528.8 KB Publisher’s postprint require - 5.0559957 - MÚ 2023 RIV US eng J - Journal Article
Khaniki, Erfan
On proof complexity of resolution over polynomial calculus.
ACM Transactions on Computational Logic. Roč. 23, č. 3 (2022), č. článku 16. ISSN 1529-3785. E-ISSN 1557-945X
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : lower bounds * modular counting * Polynomial Calculus * propositional pigeonhole principle
OECD category: Pure mathematics
Impact factor: 0.5, year: 2022
Method of publishing: Limited access
https://doi.org/10.1145/3506702
Permanent Link: https://hdl.handle.net/11104/0333080File Download Size Commentary Version Access Khaniki2.pdf 2 302.2 KB Publisher’s postprint require - 6.0553323 - MÚ 2023 RIV US eng J - Journal Article
Khaniki, Erfan
Not all Kripke models of HA are locally PA.
Advances in Mathematics. Roč. 397, March (2022), č. článku 108126. ISSN 0001-8708. E-ISSN 1090-2082
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : Heyting Arithmetic * Kripke models * Local models * PA-normal
OECD category: Pure mathematics
Impact factor: 1.7, year: 2022
Method of publishing: Limited access
https://doi.org/10.1016/j.aim.2021.108126
Permanent Link: http://hdl.handle.net/11104/0328281File Download Size Commentary Version Access Khaniki.pdf 2 392.9 KB Publisher’s postprint require - 7.0551098 - MÚ 2022 RIV DE eng J - Journal Article
Koucký, M. - Rödl, V. - Talebanfard, Navid
A separator theorem for hypergraphs and a CSP-SAT algorithm.
Logical Methods in Computer Science. Roč. 17, č. 4 (2021), č. článku 17. ISSN 1860-5974. E-ISSN 1860-5974
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : computational complexity * logic in computer science * computer science
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 0.591, year: 2021
Method of publishing: Open access
https://doi.org/10.46298/lmcs-17(4:17)2021
Permanent Link: http://hdl.handle.net/11104/0326454File Download Size Commentary Version Access Talebanfard.pdf 5 403.2 KB Publisher’s postprint open-access - 8.0546790 - MÚ 2023 RIV NL eng J - Journal Article
Pudlák, Pavel
On matrices potentially useful for tree codes.
Information Processing Letters. Roč. 174, March (2022), č. článku 106180. ISSN 0020-0190. E-ISSN 1872-6119
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : theory of computation * matrix * tree code * finite field * singleton bound
OECD category: Pure mathematics
Impact factor: 0.5, year: 2022
Method of publishing: Limited access
https://doi.org/10.1016/j.ipl.2021.106180
Permanent Link: http://hdl.handle.net/11104/0323169File Download Size Commentary Version Access Pudlak.pdf 2 234 KB Publisher’s postprint require - 9.0546785 - MÚ 2022 RIV US eng J - Journal Article
Gavinsky, Dmitry
The Layer complexity of Arthur-Merlin-like communication.
Theory of Computing. Roč. 17, č. 1 (2021), č. článku 8. ISSN 1557-2862. E-ISSN 1557-2862
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : communication complexity * complexity classes
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 0.816, year: 2021
Method of publishing: Open access
http://dx.doi.org/10.4086/toc.2021.v017a008
Permanent Link: http://hdl.handle.net/11104/0323166File Download Size Commentary Version Access Gavinsky1.pdf 2 321.6 KB Publisher’s postprint open-access - 10.0545830 - MÚ 2022 RIV US eng J - Journal Article
Gavinsky, Dmitry
Bare quantum simultaneity versus classical interactivity in communication complexity.
IEEE Transactions on Information Theory. Roč. 67, č. 10 (2021), s. 6583-6605. ISSN 0018-9448. E-ISSN 1557-9654
R&D Projects: GA ČR(CZ) GX19-27871X
Institutional support: RVO:67985840
Keywords : communication complexity * complexity theory * quantum communication
OECD category: Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)
Impact factor: 2.978, year: 2021
Method of publishing: Limited access
https://doi.org/10.1109/TIT.2021.3050528
Permanent Link: http://hdl.handle.net/11104/0322473File Download Size Commentary Version Access Gavinsky.pdf 2 733.3 KB Publisher’s postprint require