Yang, Peng; Huang, Yuan; Fu, Zhiguo The computational complexity of Holant problems on 3-regular graphs. (English) Zbl 07809103 Theor. Comput. Sci. 982, Article ID 114256, 13 p. (2024). MSC: 68Qxx PDFBibTeX XMLCite \textit{P. Yang} et al., Theor. Comput. Sci. 982, Article ID 114256, 13 p. (2024; Zbl 07809103) Full Text: DOI
Gong, Suning; Nong, Qingqin; Fang, Jiazhu; Du, Ding-Zhu Algorithms for cardinality-constrained monotone DR-submodular maximization with low adaptivity and query complexity. (English) Zbl 07794712 J. Optim. Theory Appl. 200, No. 1, 194-214 (2024). MSC: 90C27 68W25 68W40 PDFBibTeX XMLCite \textit{S. Gong} et al., J. Optim. Theory Appl. 200, No. 1, 194--214 (2024; Zbl 07794712) Full Text: DOI
Braverman, Mark Communication and information complexity. (English) Zbl 07822678 Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 1. Prize lectures. Berlin: European Mathematical Society (EMS). 284-320 (2023). MSC: 68Q11 68P30 94A15 PDFBibTeX XMLCite \textit{M. Braverman}, in: International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6--14, 2022. Volume 1. Prize lectures. Berlin: European Mathematical Society (EMS). 284--320 (2023; Zbl 07822678) Full Text: DOI OA License
Raz, Ran The work of Mark Braverman. (English) Zbl 07822670 Beliaev, Dmitry (ed.) et al., International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6–14, 2022. Volume 1. Prize lectures. Berlin: European Mathematical Society (EMS). 106-117 (2023). MSC: 01A70 68Q11 68P30 94A15 68Q01 68Q17 PDFBibTeX XMLCite \textit{R. Raz}, in: International congress of mathematicians 2022, ICM 2022, Helsinki, Finland, virtual, July 6--14, 2022. Volume 1. Prize lectures. Berlin: European Mathematical Society (EMS). 106--117 (2023; Zbl 07822670) Full Text: DOI OA License
Fontes, Lila; Laplante, Sophie; Laurière, Mathieu; Nolin, Alexandre The communication complexity of functions with large outputs. (English) Zbl 07786530 Rajsbaum, Sergio (ed.) et al., Structural information and communication complexity. 30th international colloquium, SIROCCO 2023, Alcalá de Henares, Spain, June 6–9, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13892, 427-458 (2023). MSC: 68Mxx 68Q11 68R10 PDFBibTeX XMLCite \textit{L. Fontes} et al., Lect. Notes Comput. Sci. 13892, 427--458 (2023; Zbl 07786530) Full Text: DOI arXiv
Dall’Agnol, Marcel; Gur, Tom; Lachish, Oded A structural theorem for local algorithms with applications to coding, testing, and verification. (English) Zbl 07780708 SIAM J. Comput. 52, No. 6, 1413-1463 (2023). MSC: 68R01 68Q17 68W40 05C90 PDFBibTeX XMLCite \textit{M. Dall'Agnol} et al., SIAM J. Comput. 52, No. 6, 1413--1463 (2023; Zbl 07780708) Full Text: DOI arXiv
Göös, Mika; Rubinstein, Aviad Near-optimal communication lower bounds for approximate Nash equilibria. (English) Zbl 07780705 SIAM J. Comput. 52, No. 6, FOCS18-316-FOCS18-348 (2023). MSC: 68Q25 91A05 PDFBibTeX XMLCite \textit{M. Göös} and \textit{A. Rubinstein}, SIAM J. Comput. 52, No. 6, FOCS18--316-FOCS18--348 (2023; Zbl 07780705) Full Text: DOI
Goldberg, Paul W.; Katzman, Matthew PPAD-complete approximate pure Nash equilibria in Lipschitz games. (English) Zbl 07767575 Theor. Comput. Sci. 980, Article ID 114218, 24 p. (2023). MSC: 68Qxx PDFBibTeX XMLCite \textit{P. W. Goldberg} and \textit{M. Katzman}, Theor. Comput. Sci. 980, Article ID 114218, 24 p. (2023; Zbl 07767575) Full Text: DOI
Deligkas, Argyrios; Fasoulakis, Michail; Markakis, Evangelos A polynomial-time algorithm for 1/3-approximate Nash equilibria in bimatrix games. (English) Zbl 07753182 ACM Trans. Algorithms 19, No. 4, Paper No. 31, 17 p. (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{A. Deligkas} et al., ACM Trans. Algorithms 19, No. 4, Paper No. 31, 17 p. (2023; Zbl 07753182) Full Text: DOI arXiv
Guo, Heng; Jerrum, Mark Counting vertices of integral polytopes defined by facets. (English) Zbl 07748818 Discrete Comput. Geom. 70, No. 3, 975-990 (2023). MSC: 68Q17 52B05 68W25 PDFBibTeX XMLCite \textit{H. Guo} and \textit{M. Jerrum}, Discrete Comput. Geom. 70, No. 3, 975--990 (2023; Zbl 07748818) Full Text: DOI arXiv OA License
Bshouty, Nader H. On one-sided testing affine subspaces. (English) Zbl 07745705 Mavronicolas, Marios (ed.), Algorithms and complexity. 13th international conference, CIAC 2023, Larnaca, Cyprus, June 13–16, 2023. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13898, 157-171 (2023). MSC: 68Wxx PDFBibTeX XMLCite \textit{N. H. Bshouty}, Lect. Notes Comput. Sci. 13898, 157--171 (2023; Zbl 07745705) Full Text: DOI
Deligkas, Argyrios; Fasoulakis, Michail; Markakis, Evangelos A polynomial-time Algorithm for 1/2-well-supported Nash equilibria in bimatrix games. (English) Zbl 07744116 SIAM J. Comput. 52, No. 5, 1083-1096 (2023). MSC: 68Q25 91A05 PDFBibTeX XMLCite \textit{A. Deligkas} et al., SIAM J. Comput. 52, No. 5, 1083--1096 (2023; Zbl 07744116) Full Text: DOI
He, Yuqiao; Qiu, Guoliang; Zhang, Chihao Approximability of the complementarily symmetric Holant problems on cubic graphs. (English) Zbl 07741116 Theor. Comput. Sci. 975, Article ID 114140, 10 p. (2023). MSC: 68Qxx PDFBibTeX XMLCite \textit{Y. He} et al., Theor. Comput. Sci. 975, Article ID 114140, 10 p. (2023; Zbl 07741116) Full Text: DOI
Fu, Zhiguo; Cai, Jin-Yi Holographic algorithms on domains of general size. (English) Zbl 07719392 Theory Comput. Syst. 67, No. 3, 417-436 (2023). MSC: 68Qxx 68Wxx 68Rxx PDFBibTeX XMLCite \textit{Z. Fu} and \textit{J.-Y. Cai}, Theory Comput. Syst. 67, No. 3, 417--436 (2023; Zbl 07719392) Full Text: DOI
Cai, Jin-Yi; Fu, Zhiguo Complexity classification of the eight-vertex model. (English) Zbl 07713428 Inf. Comput. 293, Article ID 105064, 38 p. (2023). MSC: 68Qxx PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{Z. Fu}, Inf. Comput. 293, Article ID 105064, 38 p. (2023; Zbl 07713428) Full Text: DOI arXiv
Chen, Zhaohua; Deng, Xiaotie; Huang, Wenhan; Li, Hanyu; Li, Yuhao On tightness of Tsaknakis-Spirakis descent methods for approximate Nash equilibria. (English) Zbl 07713418 Inf. Comput. 293, Article ID 105046, 29 p. (2023). MSC: 68Qxx PDFBibTeX XMLCite \textit{Z. Chen} et al., Inf. Comput. 293, Article ID 105046, 29 p. (2023; Zbl 07713418) Full Text: DOI
Bishnu, Arijit; Ghosh, Arijit; Kolay, Sudeshna; Mishra, Gopinath; Saurabh, Saket Almost optimal query algorithm for hitting set using a subset query. (English) Zbl 07709775 J. Comput. Syst. Sci. 137, 50-65 (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{A. Bishnu} et al., J. Comput. Syst. Sci. 137, 50--65 (2023; Zbl 07709775) Full Text: DOI
Cai, Jin-Yi; Fu, Zhiguo; Girstmair, Kurt; Kowalczyk, Michael A complexity trichotomy for \(k\)-regular asymmetric spin systems using number theory. (English) Zbl 07709619 Comput. Complexity 32, No. 1, Paper No. 4, 37 p. (2023). MSC: 68Q17 68Q25 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., Comput. Complexity 32, No. 1, Paper No. 4, 37 p. (2023; Zbl 07709619) Full Text: DOI
Goldberg, Paul W.; Katzman, Matthew J. Lower bounds for the query complexity of equilibria in Lipschitz games. (English) Zbl 07691018 Theor. Comput. Sci. 962, Article ID 113931, 14 p. (2023). MSC: 68Qxx PDFBibTeX XMLCite \textit{P. W. Goldberg} and \textit{M. J. Katzman}, Theor. Comput. Sci. 962, Article ID 113931, 14 p. (2023; Zbl 07691018) Full Text: DOI
Brailovskaya, Tatiana; Rácz, Miklós Z. Tree trace reconstruction using subtraces. (English) Zbl 1516.60004 J. Appl. Probab. 60, No. 2, 629-641 (2023). MSC: 60C05 94D99 68P20 68W32 PDFBibTeX XMLCite \textit{T. Brailovskaya} and \textit{M. Z. Rácz}, J. Appl. Probab. 60, No. 2, 629--641 (2023; Zbl 1516.60004) Full Text: DOI arXiv
Filos-Ratsikas, Aris; Hollender, Alexandros; Sotiraki, Katerina; Zampetakis, Manolis Consensus-halving: does it ever get easier? (English) Zbl 07680597 SIAM J. Comput. 52, No. 2, 412-451 (2023). MSC: 68Q25 68Q15 91B32 PDFBibTeX XMLCite \textit{A. Filos-Ratsikas} et al., SIAM J. Comput. 52, No. 2, 412--451 (2023; Zbl 07680597) Full Text: DOI arXiv
Cai, Jin-Yi; Fan, Austen Z.; Liu, Yin Bipartite 3-regular counting problems with mixed signs. (English) Zbl 07677365 J. Comput. Syst. Sci. 135, 15-31 (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., J. Comput. Syst. Sci. 135, 15--31 (2023; Zbl 07677365) Full Text: DOI
Filos-Ratsikas, Aris; Giannakopoulos, Yiannis; Hollender, Alexandros; Lazos, Philip; Poças, Diogo On the complexity of equilibrium computation in first-price auctions. (English) Zbl 07672225 SIAM J. Comput. 52, No. 1, 80-131 (2023). MSC: 68Q17 91A68 68Q25 91B26 PDFBibTeX XMLCite \textit{A. Filos-Ratsikas} et al., SIAM J. Comput. 52, No. 1, 80--131 (2023; Zbl 07672225) Full Text: DOI arXiv
Bshouty, Nader H. An optimal tester for \(k\)-Linear. (English) Zbl 1507.68344 Theor. Comput. Sci. 950, Article ID 113759, 12 p. (2023). MSC: 68W20 PDFBibTeX XMLCite \textit{N. H. Bshouty}, Theor. Comput. Sci. 950, Article ID 113759, 12 p. (2023; Zbl 1507.68344) Full Text: DOI
Fan, Austen Z.; Cai, Jin-Yi Dichotomy result on 3-regular bipartite non-negative functions. (English) Zbl 1507.68126 Theor. Comput. Sci. 949, Article ID 113745, 10 p. (2023). MSC: 68Q25 68R10 PDFBibTeX XMLCite \textit{A. Z. Fan} and \textit{J.-Y. Cai}, Theor. Comput. Sci. 949, Article ID 113745, 10 p. (2023; Zbl 1507.68126) Full Text: DOI
Govorov, Artem; Cai, Jin-Yi; Dyer, Martin A dichotomy for bounded degree graph homomorphisms with nonnegative weights. (English) Zbl 07639675 J. Comput. Syst. Sci. 132, 1-15 (2023). MSC: 68-XX PDFBibTeX XMLCite \textit{A. Govorov} et al., J. Comput. Syst. Sci. 132, 1--15 (2023; Zbl 07639675) Full Text: DOI arXiv
Sun, Xin; Xu, Dachuan; Zhang, Dongmei; Zhou, Yang An adaptive algorithm for maximization of non-submodular function with a matroid constraint. (English) Zbl 1513.90159 J. Ind. Manag. Optim. 19, No. 3, 2050-2070 (2023). MSC: 90C27 68W25 90C59 PDFBibTeX XMLCite \textit{X. Sun} et al., J. Ind. Manag. Optim. 19, No. 3, 2050--2070 (2023; Zbl 1513.90159) Full Text: DOI
Pallavoor, Ramesh Krishnan S.; Raskhodnikova, Sofya; Waingarten, Erik Approximating the distance to monotonicity of Boolean functions. (English) Zbl 1522.68749 Random Struct. Algorithms 60, No. 2, 233-260 (2022). MSC: 68W20 06E30 PDFBibTeX XMLCite \textit{R. K. S. Pallavoor} et al., Random Struct. Algorithms 60, No. 2, 233--260 (2022; Zbl 1522.68749) Full Text: DOI
Elkind, Edith; Ghosh, Abheek; Goldberg, Paul W. Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy. (English) Zbl 1520.91014 Kanellopoulos, Panagiotis (ed.) et al., Algorithmic game theory. 15th international symposium, SAGT 2022, Colchester, UK, September 12–15, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13584, 133-150 (2022). MSC: 91A10 91A68 68Q17 PDFBibTeX XMLCite \textit{E. Elkind} et al., Lect. Notes Comput. Sci. 13584, 133--150 (2022; Zbl 1520.91014) Full Text: DOI arXiv
Joswig, Michael; Klimm, Max; Spitz, Sylvain Generalized permutahedra and optimal auctions. (English) Zbl 1511.91034 SIAM J. Appl. Algebra Geom. 6, No. 4, 711-739 (2022). MSC: 91B03 91B26 52B12 68W30 PDFBibTeX XMLCite \textit{M. Joswig} et al., SIAM J. Appl. Algebra Geom. 6, No. 4, 711--739 (2022; Zbl 1511.91034) Full Text: DOI arXiv
Schnider, Patrick The complexity of sharing a pizza. (English) Zbl 1507.68131 CGT, Comput. Geom. Topol. 1, No. 1, Paper No. 4, 19 p. (2022). MSC: 68Q25 68Q17 68U05 91B32 PDFBibTeX XMLCite \textit{P. Schnider}, CGT, Comput. Geom. Topol. 1, No. 1, Paper No. 4, 19 p. (2022; Zbl 1507.68131) Full Text: DOI arXiv
Goldberg, Paul W.; Hollender, Alexandros; Igarashi, Ayumi; Manurangsi, Pasin; Suksompong, Warut Consensus halving for sets of items. (English) Zbl 1505.91198 Math. Oper. Res. 47, No. 4, 3357-3379 (2022). MSC: 91B32 68Q17 PDFBibTeX XMLCite \textit{P. W. Goldberg} et al., Math. Oper. Res. 47, No. 4, 3357--3379 (2022; Zbl 1505.91198) Full Text: DOI arXiv
Li, Yaqiao Trading information complexity for error. II: The case of a large error and the external information complexity. (English) Zbl 07629145 Inf. Comput. 289, Part A, Article ID 104952, 25 p. (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{Y. Li}, Inf. Comput. 289, Part A, Article ID 104952, 25 p. (2022; Zbl 07629145) Full Text: DOI
Grishutin, Alexander; Musatov, Daniil Discrete versions of the KKM lemma and their PPAD-completeness. (English) Zbl 07615737 Kulikov, Alexander S. (ed.) et al., Computer science – theory and applications. 17th international computer science symposium in Russia, CSR 2022, virtual event, June 29 – July 1, 2022. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13296, 170-189 (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Grishutin} and \textit{D. Musatov}, Lect. Notes Comput. Sci. 13296, 170--189 (2022; Zbl 07615737) Full Text: DOI
Deligkas, Argyrios; Filos-Ratsikas, Aris; Hollender, Alexandros Two’s company, three’s a crowd: consensus-halving for a constant number of agents. (English) Zbl 07613162 Artif. Intell. 313, Article ID 103784, 25 p. (2022). MSC: 68Txx PDFBibTeX XMLCite \textit{A. Deligkas} et al., Artif. Intell. 313, Article ID 103784, 25 p. (2022; Zbl 07613162) Full Text: DOI arXiv
Haviv, Ishay The complexity of finding fair independent sets in cycles. (English) Zbl 07605017 Comput. Complexity 31, No. 2, Paper No. 14, 32 p. (2022). MSC: 68Q17 68R10 PDFBibTeX XMLCite \textit{I. Haviv}, Comput. Complexity 31, No. 2, Paper No. 14, 32 p. (2022; Zbl 07605017) Full Text: DOI arXiv
Kumar, Mrinal; Volk, Ben Lee A lower bound on determinantal complexity. (English) Zbl 07605015 Comput. Complexity 31, No. 2, Paper No. 12, 20 p. (2022). MSC: 68Q06 68Q15 68Q17 PDFBibTeX XMLCite \textit{M. Kumar} and \textit{B. L. Volk}, Comput. Complexity 31, No. 2, Paper No. 12, 20 p. (2022; Zbl 07605015) Full Text: DOI arXiv
Chatterjee, Prerona; Kumar, Mrinal; She, Adrian; Lee Volk, Ben Quadratic lower bounds for algebraic branching programs and formulas. (English) Zbl 07565467 Comput. Complexity 31, No. 2, Paper No. 8, 54 p. (2022). MSC: 68Q06 68Q15 68Q17 PDFBibTeX XMLCite \textit{P. Chatterjee} et al., Comput. Complexity 31, No. 2, Paper No. 8, 54 p. (2022; Zbl 07565467) Full Text: DOI arXiv Backlinks: MO
Papadimitriou, Christos; Pierrakos, George; Psomas, Alexandros; Rubinstein, Aviad On the complexity of dynamic mechanism design. (English) Zbl 1497.91074 Games Econ. Behav. 134, 399-427 (2022). MSC: 91B03 91B26 68Q25 PDFBibTeX XMLCite \textit{C. Papadimitriou} et al., Games Econ. Behav. 134, 399--427 (2022; Zbl 1497.91074) Full Text: DOI arXiv
Chattopadhyay, Arkadev; Mande, Nikhil S. A short list of equalities induces large sign-rank. (English) Zbl 1502.68124 SIAM J. Comput. 51, No. 3, 820-848 (2022). MSC: 68Q11 68Q06 68Q15 68Q17 PDFBibTeX XMLCite \textit{A. Chattopadhyay} and \textit{N. S. Mande}, SIAM J. Comput. 51, No. 3, 820--848 (2022; Zbl 1502.68124) Full Text: DOI
Essaidi, Meryem; Weinberg, S. Matthew On symmetries in multi-dimensional mechanism design. (English) Zbl 07553917 Feldman, Michal (ed.) et al., Web and internet economics. 17th international conference, WINE 2021, Potsdam, Germany, December 14–17, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 13112, 59-75 (2022). MSC: 68M11 91A80 91B26 PDFBibTeX XMLCite \textit{M. Essaidi} and \textit{S. M. Weinberg}, Lect. Notes Comput. Sci. 13112, 59--75 (2022; Zbl 07553917) Full Text: DOI
Chen, Xi; Diakonikolas, Ilias; Orfanou, Anthi; Paparas, Dimitris; Sun, Xiaorui; Yannakakis, Mihalis On the complexity of optimal lottery pricing and randomized mechanisms for a unit-demand buyer. (English) Zbl 07534659 SIAM J. Comput. 51, No. 3, 492-548 (2022). MSC: 68Q17 PDFBibTeX XMLCite \textit{X. Chen} et al., SIAM J. Comput. 51, No. 3, 492--548 (2022; Zbl 07534659) Full Text: DOI
Bai, Zonglei; Cao, Yongzhi; Wang, Hanpin Zero-freeness and approximation of real Boolean Holant problems. (English) Zbl 07533875 Theor. Comput. Sci. 917, 12-30 (2022). MSC: 68Qxx PDFBibTeX XMLCite \textit{Z. Bai} et al., Theor. Comput. Sci. 917, 12--30 (2022; Zbl 07533875) Full Text: DOI
Servedio, Rocco A.; Tan, Li-Yang Improved pseudorandom generators from pseudorandom multi-switching lemmas. (English) Zbl 07528580 Theory Comput. 18, Paper No. 4, 46 p. (2022). MSC: 68Q17 68Qxx PDFBibTeX XMLCite \textit{R. A. Servedio} and \textit{L.-Y. Tan}, Theory Comput. 18, Paper No. 4, 46 p. (2022; Zbl 07528580) Full Text: DOI arXiv
Cai, Jin-Yi; Fu, Zhiguo Holographic algorithm with matchgates is universal for planar #CSP over Boolean domain. (English) Zbl 07516618 SIAM J. Comput. 51, No. 2, STOC17-50-STOC17-151 (2022). MSC: 68Q25 68Q17 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{Z. Fu}, SIAM J. Comput. 51, No. 2, STOC17--50-STOC17--151 (2022; Zbl 07516618) Full Text: DOI
Bu, Kaifeng; Koh, Dax Enshan Classical simulation of quantum circuits by half Gauss sums. (English) Zbl 07488556 Commun. Math. Phys. 390, No. 2, 471-500 (2022). MSC: 68Qxx 81Pxx 11Txx PDFBibTeX XMLCite \textit{K. Bu} and \textit{D. E. Koh}, Commun. Math. Phys. 390, No. 2, 471--500 (2022; Zbl 07488556) Full Text: DOI arXiv
Filos-Ratsikas, Aris; Goldberg, Paul W. The complexity of necklace splitting, consensus-halving, and discrete ham sandwich. (English) Zbl 07488094 SIAM J. Comput. 51, No. 1, STOC19-200-STOC19-268 (2022). MSC: 68Q15 68Q17 68R05 PDFBibTeX XMLCite \textit{A. Filos-Ratsikas} and \textit{P. W. Goldberg}, SIAM J. Comput. 51, No. 1, STOC19--200-STOC19--268 (2022; Zbl 07488094) Full Text: DOI
Lin, Jiabao The complexity of counting \(\mathrm{CSP}^d\). (English) Zbl 07473210 Theory Comput. Syst. 66, No. 1, 309-321 (2022). MSC: 68Qxx 05Cxx 68Rxx PDFBibTeX XMLCite \textit{J. Lin}, Theory Comput. Syst. 66, No. 1, 309--321 (2022; Zbl 07473210) Full Text: DOI
Cai, Jin-Yi; Fu, Zhiguo; Guo, Heng; Williams, Tyson FKT is not universal – a planar holant dichotomy for symmetric constraints. (English) Zbl 07473209 Theory Comput. Syst. 66, No. 1, 143-308 (2022). MSC: 68Qxx 82Bxx 68Rxx PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., Theory Comput. Syst. 66, No. 1, 143--308 (2022; Zbl 07473209) Full Text: DOI
Dyer, Martin; Heinrich, Marc; Jerrum, Mark; Müller, Haiko Polynomial-time approximation algorithms for the antiferromagnetic Ising model on line graphs. (English) Zbl 1511.68343 Comb. Probab. Comput. 30, No. 6, 905-921 (2021). MSC: 68W25 05C76 68Q17 68W20 68W40 82B20 PDFBibTeX XMLCite \textit{M. Dyer} et al., Comb. Probab. Comput. 30, No. 6, 905--921 (2021; Zbl 1511.68343) Full Text: DOI arXiv
Massar, Serge; Santha, Miklos Total functions in QMA. (English) Zbl 1509.81288 Quantum Inf. Process. 20, No. 1, Paper No. 35, 35 p. (2021). MSC: 81P68 68Q12 PDFBibTeX XMLCite \textit{S. Massar} and \textit{M. Santha}, Quantum Inf. Process. 20, No. 1, Paper No. 35, 35 p. (2021; Zbl 1509.81288) Full Text: DOI arXiv
Massar, Serge; Santha, Miklos Characterising the intersection of QMA and coQMA. (English) Zbl 1508.81501 Quantum Inf. Process. 20, No. 12, Paper No. 396, 48 p. (2021). MSC: 81P68 68Q15 PDFBibTeX XMLCite \textit{S. Massar} and \textit{M. Santha}, Quantum Inf. Process. 20, No. 12, Paper No. 396, 48 p. (2021; Zbl 1508.81501) Full Text: DOI
Zhang, Kaiqing; Yang, Zhuoran; Başar, Tamer Multi-agent reinforcement learning: a selective overview of theories and algorithms. (English) Zbl 07608712 Vamvoudakis, Kyriakos G. (ed.) et al., Handbook of reinforcement learning and control. Cham: Springer. Stud. Syst. Decis. Control 325, 321-384 (2021). MSC: 68Txx PDFBibTeX XMLCite \textit{K. Zhang} et al., Stud. Syst. Decis. Control 325, 321--384 (2021; Zbl 07608712) Full Text: DOI arXiv
Backens, Miriam A full dichotomy for \(\mathrm{Holant}^c\), inspired by quantum computation. (English) Zbl 1492.68101 SIAM J. Comput. 50, No. 6, 1739-1799 (2021). MSC: 68R10 68Q25 81P40 81P45 81P68 PDFBibTeX XMLCite \textit{M. Backens}, SIAM J. Comput. 50, No. 6, 1739--1799 (2021; Zbl 1492.68101) Full Text: DOI arXiv
Cai, Jin-Yi; Fan, Austen Z.; Liu, Yin Bipartite 3-regular counting problems with mixed signs. (English) Zbl 07530229 Bampis, Evripidis (ed.) et al., Fundamentals of computation theory. 23rd international symposium, FCT 2021, Athens, Greece, September 12–15, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12867, 135-148 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., Lect. Notes Comput. Sci. 12867, 135--148 (2021; Zbl 07530229) Full Text: DOI arXiv
Gishboliner, Lior; Shapira, Asaf Testing graphs against an unknown distribution. (English) Zbl 1487.05258 Isr. J. Math. 245, No. 2, 787-837 (2021). MSC: 05C99 68W20 68Q25 PDFBibTeX XMLCite \textit{L. Gishboliner} and \textit{A. Shapira}, Isr. J. Math. 245, No. 2, 787--837 (2021; Zbl 1487.05258) Full Text: DOI arXiv
Fan, Austen Z.; Cai, Jin-Yi Dichotomy result on 3-regular bipartite non-negative functions. (English) Zbl 07493526 Santhanam, Rahul (ed.) et al., Computer science – theory and applications. 16th international computer science symposium in Russia, CSR 2021, Sochi, Russia, June 28 – July 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12730, 102-115 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{A. Z. Fan} and \textit{J.-Y. Cai}, Lect. Notes Comput. Sci. 12730, 102--115 (2021; Zbl 07493526) Full Text: DOI arXiv
Datta, Samir; Tawari, Anuj; Vasudev, Yadu Dynamic complexity of expansion. (English) Zbl 07493524 Santhanam, Rahul (ed.) et al., Computer science – theory and applications. 16th international computer science symposium in Russia, CSR 2021, Sochi, Russia, June 28 – July 2, 2021. Proceedings. Cham: Springer. Lect. Notes Comput. Sci. 12730, 56-77 (2021). MSC: 68Qxx PDFBibTeX XMLCite \textit{S. Datta} et al., Lect. Notes Comput. Sci. 12730, 56--77 (2021; Zbl 07493524) Full Text: arXiv
Zhengwei, Xie; Daowen, Qiu; Guangya, Cai; Gruska, Jozef; Mateus, Paulo Testing Boolean functions properties. (English) Zbl 1522.68237 Fundam. Inform. 182, No. 4, 321-344 (2021). MSC: 68Q12 06E30 68W20 PDFBibTeX XMLCite \textit{X. Zhengwei} et al., Fundam. Inform. 182, No. 4, 321--344 (2021; Zbl 1522.68237) Full Text: DOI arXiv
Göös, Mika; Rubinstein, Aviad Near-optimal communication lower bounds for approximate Nash equilibria. (English) Zbl 07453415 SIAM J. Comput. 50, No. 5, FOCS18-316-FOCS18-348 (2021). MSC: 68Q11 91A05 91A10 91A68 PDFBibTeX XMLCite \textit{M. Göös} and \textit{A. Rubinstein}, SIAM J. Comput. 50, No. 5, FOCS18--316-FOCS18--348 (2021; Zbl 07453415) Full Text: DOI arXiv
Blanca, Antonio; Chen, Zongchen; Štefankovič, Daniel; Vigoda, Eric Hardness of identity testing for restricted Boltzmann machines and Potts models. (English) Zbl 07415095 J. Mach. Learn. Res. 22, Paper No. 152, 56 p. (2021). MSC: 68T05 PDFBibTeX XMLCite \textit{A. Blanca} et al., J. Mach. Learn. Res. 22, Paper No. 152, 56 p. (2021; Zbl 07415095) Full Text: arXiv Link
Farhadi, Alireza; Hajiaghayi, MohammadTaghi; Larsen, Kasper Green; Shi, Elaine Lower bounds for external memory integer sorting via network coding. (English) Zbl 1475.94052 SIAM J. Comput. 50, No. 5, STOC19-87-STOC19-111 (2021). MSC: 94A24 68P10 68P20 PDFBibTeX XMLCite \textit{A. Farhadi} et al., SIAM J. Comput. 50, No. 5, STOC19--87-STOC19--111 (2021; Zbl 1475.94052) Full Text: DOI
Cai, Jin-Yi; Govorov, Artem The complexity of counting edge colorings for simple graphs. (English) Zbl 1514.68205 Theor. Comput. Sci. 889, 14-24 (2021). MSC: 68R10 05C15 05C30 68Q17 PDFBibTeX XMLCite \textit{J.-Y. Cai} and \textit{A. Govorov}, Theor. Comput. Sci. 889, 14--24 (2021; Zbl 1514.68205) Full Text: DOI arXiv
Goldberg, Paul W.; Hollender, Alexandros The hairy ball problem is PPAD-complete. (English) Zbl 1527.68082 J. Comput. Syst. Sci. 122, 34-62 (2021). MSC: 68Q17 58C30 PDFBibTeX XMLCite \textit{P. W. Goldberg} and \textit{A. Hollender}, J. Comput. Syst. Sci. 122, 34--62 (2021; Zbl 1527.68082) Full Text: DOI arXiv Link
Hollender, Alexandros The classes PPA-\(k\): existence from arguments modulo \(k\). (English) Zbl 1514.68083 Theor. Comput. Sci. 885, 15-29 (2021). MSC: 68Q15 68Q25 91B32 PDFBibTeX XMLCite \textit{A. Hollender}, Theor. Comput. Sci. 885, 15--29 (2021; Zbl 1514.68083) Full Text: DOI arXiv
Ishizuka, Takashi The complexity of the parity argument with potential. (English) Zbl 1515.68243 J. Comput. Syst. Sci. 120, 14-41 (2021). MSC: 68R10 68Q25 PDFBibTeX XMLCite \textit{T. Ishizuka}, J. Comput. Syst. Sci. 120, 14--41 (2021; Zbl 1515.68243) Full Text: DOI
Ganor, Anat; Kol, Gillat; Raz, Ran Exponential separation of communication and external information. (English) Zbl 1464.68101 SIAM J. Comput. 50, No. 3, STOC16-236-STOC16-254 (2021). MSC: 68P30 68Q11 PDFBibTeX XMLCite \textit{A. Ganor} et al., SIAM J. Comput. 50, No. 3, STOC16--236-STOC16--254 (2021; Zbl 1464.68101) Full Text: DOI
Assadi, Sepehr; Khanna, Sanjeev; Li, Yang Tight bounds for single-pass streaming complexity of the set cover problem. (English) Zbl 1464.68124 SIAM J. Comput. 50, No. 3, STOC16-341-STOC16-376 (2021). MSC: 68Q25 68Q11 68W25 68W27 90C27 PDFBibTeX XMLCite \textit{S. Assadi} et al., SIAM J. Comput. 50, No. 3, STOC16--341-STOC16--376 (2021; Zbl 1464.68124) Full Text: DOI
Zhang, Ningshan; Mohri, Mehryar; Hoffman, Judy Multiple-source adaptation theory and algorithms. (English) Zbl 1490.68194 Ann. Math. Artif. Intell. 89, No. 3-4, 237-270 (2021); addendum ibid. 90, No. 6, 569-572 (2022). MSC: 68T05 62B10 PDFBibTeX XMLCite \textit{N. Zhang} et al., Ann. Math. Artif. Intell. 89, No. 3--4, 237--270 (2021; Zbl 1490.68194) Full Text: DOI
Belovs, Aleksandrs; Blais, Eric A polynomial lower bound for testing monotonicity. (English) Zbl 1522.68238 SIAM J. Comput. 50, No. 3, STOC16-406-STOC16-433 (2021). MSC: 68Q17 06E30 68Q25 68W20 PDFBibTeX XMLCite \textit{A. Belovs} and \textit{E. Blais}, SIAM J. Comput. 50, No. 3, STOC16--406-STOC16--433 (2021; Zbl 1522.68238) Full Text: DOI
Ishizuka, Takashi On the complexity of finding a Caristi’s fixed point. (English) Zbl 1516.68038 Inf. Process. Lett. 170, Article ID 106119, 7 p. (2021). MSC: 68Q15 47H10 68Q17 68Q25 PDFBibTeX XMLCite \textit{T. Ishizuka}, Inf. Process. Lett. 170, Article ID 106119, 7 p. (2021; Zbl 1516.68038) Full Text: DOI
Huang, Dawei; Pettie, Seth; Zhang, Yixiang; Zhang, Zhijun The communication complexity of set intersection and multiple equality testing. (English) Zbl 1462.68058 SIAM J. Comput. 50, No. 2, 674-717 (2021). MSC: 68Q11 60C05 68W20 PDFBibTeX XMLCite \textit{D. Huang} et al., SIAM J. Comput. 50, No. 2, 674--717 (2021; Zbl 1462.68058) Full Text: DOI
Rosen, Alon; Segev, Gil; Shahaf, Ido Can PPAD hardness be based on standard cryptographic assumptions? (English) Zbl 1460.94064 J. Cryptology 34, No. 1, Paper No. 8, 65 p. (2021). MSC: 94A60 94A62 68Q25 PDFBibTeX XMLCite \textit{A. Rosen} et al., J. Cryptology 34, No. 1, Paper No. 8, 65 p. (2021; Zbl 1460.94064) Full Text: DOI
Bilò, Vittorio; Mavronicolas, Marios The complexity of computational problems about Nash equilibria in symmetric win-lose games. (English) Zbl 1509.91009 Algorithmica 83, No. 2, 447-530 (2021). MSC: 91A68 91A10 68Q17 PDFBibTeX XMLCite \textit{V. Bilò} and \textit{M. Mavronicolas}, Algorithmica 83, No. 2, 447--530 (2021; Zbl 1509.91009) Full Text: DOI arXiv
Chattopadhyay, Arkadev; Filmus, Yuval; Koroth, Sajin; Meir, Or; Pitassi, Toniann Query-to-communication lifting using low-discrepancy gadgets. (English) Zbl 1509.68086 SIAM J. Comput. 50, No. 1, 171-210 (2021). MSC: 68Q11 PDFBibTeX XMLCite \textit{A. Chattopadhyay} et al., SIAM J. Comput. 50, No. 1, 171--210 (2021; Zbl 1509.68086) Full Text: DOI arXiv
Bitansky, Nir; Degwekar, Akshay; Vaikuntanathan, Vinod Structure versus hardness through the obfuscation lens. (English) Zbl 1459.94098 SIAM J. Comput. 50, No. 1, 98-144 (2021). MSC: 94A60 68Q17 PDFBibTeX XMLCite \textit{N. Bitansky} et al., SIAM J. Comput. 50, No. 1, 98--144 (2021; Zbl 1459.94098) Full Text: DOI
Deligkas, Argyrios; Fearnley, John; Melissourgos, Themistoklis; Spirakis, Paul G. Computing exact solutions of consensus halving and the Borsuk-Ulam theorem. (English) Zbl 1477.68115 J. Comput. Syst. Sci. 117, 75-98 (2021). MSC: 68Q17 55M20 68Q15 91B32 PDFBibTeX XMLCite \textit{A. Deligkas} et al., J. Comput. Syst. Sci. 117, 75--98 (2021; Zbl 1477.68115) Full Text: DOI arXiv Link
Deng, Xiaotie; Edmonds, Jack R.; Feng, Zhe; Liu, Zhengyang; Qi, Qi; Xu, Zeying Understanding PPA-completeness. (English) Zbl 1464.68121 J. Comput. Syst. Sci. 115, 146-168 (2021). MSC: 68Q17 57M15 57Q15 68Q25 68U05 PDFBibTeX XMLCite \textit{X. Deng} et al., J. Comput. Syst. Sci. 115, 146--168 (2021; Zbl 1464.68121) Full Text: DOI Link
Ron, Dana; Rosin, Asaf Almost optimal distribution-free sample-based testing of \(k\)-modality. (English) Zbl 07758329 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 27, 19 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{D. Ron} and \textit{A. Rosin}, LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 27, 19 p. (2020; Zbl 07758329) Full Text: DOI
Rashtchian, Cyrus; Woodruff, David P.; Zhu, Hanlin Vector-matrix-vector queries for solving linear algebra, statistics, and graph problems. (English) Zbl 07758328 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 26, 20 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{C. Rashtchian} et al., LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 26, 20 p. (2020; Zbl 07758328) Full Text: DOI arXiv
Blais, Eric; Bommireddi, Abhinav On testing and robust characterizations of convexity. (English) Zbl 07758320 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 18, 15 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{E. Blais} and \textit{A. Bommireddi}, LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 18, 15 p. (2020; Zbl 07758320) Full Text: DOI
Bshouty, Nader H. Almost optimal testers for concise representations. (English) Zbl 07758307 Byrka, Jarosław (ed.) et al., Approximation, randomization, and combinatorial optimization. Algorithms and techniques. 23rd international conference, APPROX 2020, and 24th international conference, RANDOM 2020, August 17–19, 2020, Virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 176, Article 5, 20 p. (2020). MSC: 68W20 68W25 90C27 PDFBibTeX XMLCite \textit{N. H. Bshouty}, LIPIcs -- Leibniz Int. Proc. Inform. 176, Article 5, 20 p. (2020; Zbl 07758307) Full Text: DOI arXiv
Jansen, Bart M. P.; Włodarczyk, Michał Optimal polynomial-time compression for Boolean max CSP. (English) Zbl 07651202 Grandoni, Fabrizio (ed.) et al., 28th annual European symposium on algorithms. ESA 2020, September 7–9, 2020, Pisa, Italy, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 173, Article 63, 19 p. (2020). MSC: 68Wxx PDFBibTeX XMLCite \textit{B. M. P. Jansen} and \textit{M. Włodarczyk}, LIPIcs -- Leibniz Int. Proc. Inform. 173, Article 63, 19 p. (2020; Zbl 07651202) Full Text: DOI arXiv
Xie, Zhengwei; Qiu, Daowen Quantum and classical query complexities for generalized Deutsch-Jozsa problems. (English) Zbl 1508.81558 Quantum Inf. Process. 19, No. 5, Paper No. 150, 15 p. (2020). MSC: 81P68 68Q12 PDFBibTeX XMLCite \textit{Z. Xie} and \textit{D. Qiu}, Quantum Inf. Process. 19, No. 5, Paper No. 150, 15 p. (2020; Zbl 1508.81558) Full Text: DOI
Gupta, Nikhil; Saha, Chandan; Thankey, Bhargav A super-quadratic lower bound for depth four arithmetic circuits. (English) Zbl 07561751 Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 23, 31 p. (2020). MSC: 68Q25 PDFBibTeX XMLCite \textit{N. Gupta} et al., LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 23, 31 p. (2020; Zbl 07561751) Full Text: DOI
Chaugule, Prasad; Kumar, Mrinal; Limaye, Nutan; Mohapatra, Chandra Kanta; She, Adrian; Srinivasan, Srikanth Schur polynomials do not have small formulas if the determinant doesn’t. (English) Zbl 07561742 Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 14, 27 p. (2020). MSC: 68Q25 PDFBibTeX XMLCite \textit{P. Chaugule} et al., LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 14, 27 p. (2020; Zbl 07561742) Full Text: DOI arXiv
Cai, Jin-Yi; Liu, Tianyu; Lu, Pinyan; Yu, Jing Approximability of the eight-vertex model. (English) Zbl 07561732 Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 4, 18 p. (2020). MSC: 68Q25 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 4, 18 p. (2020; Zbl 07561732) Full Text: DOI arXiv
Chatterjee, Prerona; Kumar, Mrinal; She, Adrian; Volk, Ben Lee A quadratic lower bound for algebraic branching programs. (English) Zbl 07561730 Saraf, Shubhangi (ed.), 35th computational complexity conference, CCC 2020, July 28–31, 2020, Saarbrücken, Germany, virtual conference. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 169, Article 2, 21 p. (2020). MSC: 68Q25 PDFBibTeX XMLCite \textit{P. Chatterjee} et al., LIPIcs -- Leibniz Int. Proc. Inform. 169, Article 2, 21 p. (2020; Zbl 07561730) Full Text: DOI
Murthy, Janaky; Nair, Vineet; Saha, Chandan Randomized polynomial-time equivalence between determinant and trace-IMM equivalence tests. (English) Zbl 07559443 Esparza, Javier (ed.) et al., 45th international symposium on mathematical foundations of computer science, MFCS 2020, August 25–26, 2020, Prague, Czech Republic. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 170, Article 72, 16 p. (2020). MSC: 68Qxx PDFBibTeX XMLCite \textit{J. Murthy} et al., LIPIcs -- Leibniz Int. Proc. Inform. 170, Article 72, 16 p. (2020; Zbl 07559443) Full Text: DOI arXiv
Yehudayoff, Amir Pointer chasing via triangular discrimination. (English) Zbl 1504.68078 Comb. Probab. Comput. 29, No. 4, 485-494 (2020). MSC: 68Q17 68P30 68Q10 68W15 PDFBibTeX XMLCite \textit{A. Yehudayoff}, Comb. Probab. Comput. 29, No. 4, 485--494 (2020; Zbl 1504.68078) Full Text: DOI
Cai, Jin-Yi; Lu, Pinyan; Xia, Mingji Dichotomy for Holant\(^\ast\) problems on the Boolean domain. (English) Zbl 1503.68199 Theory Comput. Syst. 64, No. 8, 1362-1391 (2020). MSC: 68R05 68Q17 68Q25 68R07 68R10 68W05 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., Theory Comput. Syst. 64, No. 8, 1362--1391 (2020; Zbl 1503.68199) Full Text: DOI Link
Huang, Zengfeng; Radunovic, Bozidar; Vojnovic, Milan; Zhang, Qin Communication complexity of approximate maximum matching in the message-passing model. (English) Zbl 1497.68217 Distrib. Comput. 33, No. 6, 515-531 (2020). MSC: 68Q11 05C70 68R10 68W15 68W25 PDFBibTeX XMLCite \textit{Z. Huang} et al., Distrib. Comput. 33, No. 6, 515--531 (2020; Zbl 1497.68217) Full Text: DOI arXiv
Baleshzar, Roksana; Chakrabarty, Deeparnab; Pallavoor, Ramesh Krishnan S.; Raskhodnikova, Sofya; Seshadhri, C. Optimal unateness testers for real-valued functions: adaptivity helps. (English) Zbl 1462.68235 Theory Comput. 16, Paper No. 3, 36 p. (2020). MSC: 68W20 26-08 PDFBibTeX XMLCite \textit{R. Baleshzar} et al., Theory Comput. 16, Paper No. 3, 36 p. (2020; Zbl 1462.68235) Full Text: DOI arXiv
de Campos, Cassio P.; Stamoulis, Georgios; Weyland, Dennis A structured view on weighted counting with relations to counting, quantum computation and applications. (English) Zbl 1496.68153 Inf. Comput. 275, Article ID 104627, 25 p. (2020). MSC: 68Q15 68Q10 81P68 PDFBibTeX XMLCite \textit{C. P. de Campos} et al., Inf. Comput. 275, Article ID 104627, 25 p. (2020; Zbl 1496.68153) Full Text: DOI arXiv
Cai, Jin-Yi; Fu, Zhiguo; Shao, Shuai Beyond #CSP: a dichotomy for counting weighted Eulerian orientations with ARS. (English) Zbl 1496.68157 Inf. Comput. 275, Article ID 104589, 27 p. (2020). MSC: 68Q25 68R05 68R07 68R10 PDFBibTeX XMLCite \textit{J.-Y. Cai} et al., Inf. Comput. 275, Article ID 104589, 27 p. (2020; Zbl 1496.68157) Full Text: DOI arXiv
Hubáček, Pavel; Yogev, Eylon Hardness of continuous local search: query complexity and cryptographic lower bounds. (English) Zbl 1498.68122 SIAM J. Comput. 49, No. 6, 1128-1172 (2020). MSC: 68Q17 68Q25 68T20 90C59 94A60 PDFBibTeX XMLCite \textit{P. Hubáček} and \textit{E. Yogev}, SIAM J. Comput. 49, No. 6, 1128--1172 (2020; Zbl 1498.68122) Full Text: DOI
Bezáková, Ivona; Blanca, Antonio; Chen, Zongchen; Štefankovič, Daniel; Vigoda, Eric Lower bounds for testing graphical models: colorings and antiferromagnetic Ising models. (English) Zbl 1499.62192 J. Mach. Learn. Res. 21, Paper No. 25, 62 p. (2020). MSC: 62H22 62H15 68Q17 68Q25 82B20 PDFBibTeX XMLCite \textit{I. Bezáková} et al., J. Mach. Learn. Res. 21, Paper No. 25, 62 p. (2020; Zbl 1499.62192) Full Text: arXiv Link
Fearnley, John; Gordon, Spencer; Mehta, Ruta; Savani, Rahul Unique end of potential line. (English) Zbl 1461.68086 J. Comput. Syst. Sci. 114, 1-35 (2020). MSC: 68Q15 68Q17 68Q25 PDFBibTeX XMLCite \textit{J. Fearnley} et al., J. Comput. Syst. Sci. 114, 1--35 (2020; Zbl 1461.68086) Full Text: DOI arXiv Link
Feng, Weiming; Sun, Yuxin; Yin, Yitong What can be sampled locally? (English) Zbl 1445.68334 Distrib. Comput. 33, No. 3-4, 227-253 (2020). MSC: 68W15 60J22 68Q87 PDFBibTeX XMLCite \textit{W. Feng} et al., Distrib. Comput. 33, No. 3--4, 227--253 (2020; Zbl 1445.68334) Full Text: DOI arXiv
Feder, Tomás; Hell, Pavol Complexity of correspondence \(H\)-colourings. (English) Zbl 1440.05150 Discrete Appl. Math. 281, 235-245 (2020). MSC: 05C60 05C15 68Q17 PDFBibTeX XMLCite \textit{T. Feder} and \textit{P. Hell}, Discrete Appl. Math. 281, 235--245 (2020; Zbl 1440.05150) Full Text: DOI arXiv