×

zbMATH — the first resource for mathematics

Found 1,093 Documents (Results 1–100)

Hits per Page
100
Display Format
MathJax
Result Sorting
Newest 1st
Wrona, Michał
On the relational width of first-order expansions of finitely bounded homogeneous binary cores with bounded strict width. (English) Zbl 07299525
Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-7104-9). 958-971 (2020).
MSC:  03B70
PDF BibTeX XML Cite
\textit{M. Wrona}, in: Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8--11, 2020. New York, NY: Association for Computing Machinery (ACM). 958--971 (2020; Zbl 07299525)
Full Text: DOI
Idziak, Paweł M.; Kawałek, Piotr; Krzaczkowski, Jacek
Intermediate problems in modular circuits satisfiability. (English) Zbl 07299497
Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-7104-9). 578-590 (2020).
MSC:  68
PDF BibTeX XML Cite
\textit{P. M. Idziak} et al., in: Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8--11, 2020. New York, NY: Association for Computing Machinery (ACM). 578--590 (2020; Zbl 07299497)
Full Text: DOI
Bodirsky, Manuel; Pakusa, Wied; Rydval, Jakub
Temporal constraint satisfaction problems in fixed-point logic. (English) Zbl 07299472
Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8–11, 2020. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-7104-9). 237-251 (2020).
MSC:  03B70
PDF BibTeX XML Cite
\textit{M. Bodirsky} et al., in: Proceedings of the 2020 35th annual ACM/IEEE symposium on logic in computer science, LICS 2020, virtual event, July 8--11, 2020. New York, NY: Association for Computing Machinery (ACM). 237--251 (2020; Zbl 07299472)
Full Text: DOI
Zhuk, Dmitriy; Martin, Barnaby
QCSP monsters and the demise of the Chen conjecture. (English) Zbl 07298233
Makarychev, Konstantin (ed.) et al., Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC ’20, Chicago, IL, USA, June 22–26, 2020. New York, NY: Association for Computing Machinery (ACM) (ISBN 978-1-4503-6979-4). 91-104 (2020).
MSC:  68Qxx
PDF BibTeX XML Cite
\textit{D. Zhuk} and \textit{B. Martin}, in: Proceedings of the 52nd annual ACM SIGACT symposium on theory of computing, STOC '20, Chicago, IL, USA, June 22--26, 2020. New York, NY: Association for Computing Machinery (ACM). 91--104 (2020; Zbl 07298233)
Full Text: DOI
Barto, Libor
Algebraic theory of promise constraint satisfaction problems, first steps. (English) Zbl 07160823
Gąsieniec, Leszek Antoni (ed.) et al., Fundamentals of computation theory. 22nd international symposium, FCT 2019, Copenhagen, Denmark, August 12–14, 2019. Proceedings. Cham: Springer (ISBN 978-3-030-25026-3/pbk; 978-3-030-25027-0/ebook). Lecture Notes in Computer Science 11651, 3-17 (2019).
MSC:  68Qxx
PDF BibTeX XML Cite
\textit{L. Barto}, Lect. Notes Comput. Sci. 11651, 3--17 (2019; Zbl 07160823)
Full Text: DOI
Bulín, Jakub; Krokhin, Andrei; Opršal, Jakub
Algebraic approach to promise constraint satisfaction. (English) Zbl 1433.68271
Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 602-613 (2019).
MSC:  68R07 05C15 68Q17 68Q25
PDF BibTeX XML Cite
\textit{J. Bulín} et al., in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 602--613 (2019; Zbl 1433.68271)
Full Text: DOI
Brakensiek, Joshua; Gopi, Sivakanth; Guruswami, Venkatesan
CSPs with global modular constraints: algorithms and hardness via polynomial representations. (English) Zbl 1433.68270
Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 590-601 (2019).
MSC:  68R07 68Q17 68Q25 68W40
PDF BibTeX XML Cite
\textit{J. Brakensiek} et al., in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 590--601 (2019; Zbl 1433.68270)
Full Text: DOI
Brakensiek, Joshua; Guruswami, Venkatesan
Bridging between 0/1 and linear programming via random walks. (English) Zbl 1433.68156
Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 568-577 (2019).
MSC:  68Q17 68R07 68W20 90C05 90C10 90C15
PDF BibTeX XML Cite
\textit{J. Brakensiek} and \textit{V. Guruswami}, in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 568--577 (2019; Zbl 1433.68156)
Full Text: DOI
Potechin, Aaron
On the approximation resistance of balanced linear threshold functions. (English) Zbl 1433.68160
Charikar, Moses (ed.) et al., Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC ’19, Phoenix, AZ, USA, June 23–26, 2019. New York, NY: Association for Computing Machinery (ACM). 430-441 (2019).
MSC:  68Q17
PDF BibTeX XML Cite
\textit{A. Potechin}, in: Proceedings of the 51st annual ACM SIGACT symposium on theory of computing, STOC '19, Phoenix, AZ, USA, June 23--26, 2019. New York, NY: Association for Computing Machinery (ACM). 430--441 (2019; Zbl 1433.68160)
Full Text: DOI
Davarnia, Danial; Hooker, J. N.
Consistency for \(0-1\) programming. (English) Zbl 07116696
Rousseau, Louis-Martin (ed.) et al., Integration of constraint programming, artificial intelligence, and operations research. 16th international conference, CPAIOR 2019, Thessaloniki, Greece, June 4–7, 2019. Proceedings. Cham: Springer (ISBN 978-3-030-19211-2/pbk; 978-3-030-19212-9/ebook). Lecture Notes in Computer Science 11494, 225-240 (2019).
MSC:  68T20 90C27
PDF BibTeX XML Cite
\textit{D. Davarnia} and \textit{J. N. Hooker}, Lect. Notes Comput. Sci. 11494, 225--240 (2019; Zbl 07116696)
Full Text: DOI
Larose, Benoît; Martin, Barnaby; Paulusma, Daniël
Surjective H-colouring over reflexive digraphs. (English) Zbl 07228440
Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-062-0). LIPIcs – Leibniz International Proceedings in Informatics 96, Article 49, 14 p. (2018).
MSC:  68Qxx
PDF BibTeX XML Cite
\textit{B. Larose} et al., LIPIcs -- Leibniz Int. Proc. Inform. 96, Article 49, 14 p. (2018; Zbl 07228440)
Full Text: DOI
Hirai, Hiroshi; Iwamasa, Yuni; Murota, Kazuo; Živný, Stanislav
Beyond JWP: a tractable class of binary VCSPs via M-convex intersection. (English) Zbl 1454.68059
Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 96, Article 39, 14 p. (2018).
MSC:  68Q27 90C27
PDF BibTeX XML Cite
\textit{H. Hirai} et al., LIPIcs -- Leibniz Int. Proc. Inform. 96, Article 39, 14 p. (2018; Zbl 1454.68059)
Full Text: DOI
Carbonnel, Clément; Cohen, David A.; Cooper, Martin C.; Živný, Stanislav
On singleton arc consistency for CSPs defined by monotone patterns. (English) Zbl 07228410
Niedermeier, Rolf (ed.) et al., 35th symposium on theoretical aspects of computer science, STACS 2018, Caen, France, February 28 – March 3, 2018. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik (ISBN 978-3-95977-062-0). LIPIcs – Leibniz International Proceedings in Informatics 96, Article 19, 15 p. (2018).
MSC:  68Qxx
PDF BibTeX XML Cite
\textit{C. Carbonnel} et al., LIPIcs -- Leibniz Int. Proc. Inform. 96, Article 19, 15 p. (2018; Zbl 07228410)
Full Text: DOI
Bauer, Sabine; Jost, Steffen; Hofmann, Martin
Decidable inequalities over infinite trees. (English) Zbl 1415.68059
Barthe, Gilles (ed.) et al., LPAR-22. 22nd international conference on logic for programming, artificial intelligence and reasoning, Awassa, Ethiopia, November 17–21, 2018. Selected papers. Manchester: EasyChair. EPiC Ser. Comput. 57, 111-130 (2018).
MSC:  68N30 03B25 03D05 68R15
PDF BibTeX XML Cite
\textit{S. Bauer} et al., EPiC Ser. Comput. 57, 111--130 (2018; Zbl 1415.68059)
Full Text: DOI
Culus, Jean-François; Toulouse, Sophie
How far from a worst solution a random solution of a \(k\,\)CSP instance can be? (English) Zbl 06932718
Iliopoulos, Costas (ed.) et al., Combinatorial algorithms. 29th international workshop, IWOCA 2018, Singapore, July 16–19, 2018. Proceedings. Cham: Springer (ISBN 978-3-319-94666-5/pbk; 978-3-319-94667-2/ebook). Lecture Notes in Computer Science 10979, 374-386 (2018).
MSC:  68Rxx 68Wxx
PDF BibTeX XML Cite
\textit{J.-F. Culus} and \textit{S. Toulouse}, Lect. Notes Comput. Sci. 10979, 374--386 (2018; Zbl 06932718)
Full Text: DOI
Culus, Jean-François; Toulouse, Sophie
2 CSPs all are approximable within a constant differential factor. (English) Zbl 1401.90182
Lee, Jon (ed.) et al., Combinatorial optimization. 5th international symposium, ISCO 2018, Marrakesh, Morocco, April 11–13, 2018. Revised selected papers. Cham: Springer (ISBN 978-3-319-96150-7/pbk; 978-3-319-96151-4/ebook). Lecture Notes in Computer Science 10856, 389-401 (2018).
MSC:  90C27
PDF BibTeX XML Cite
\textit{J.-F. Culus} and \textit{S. Toulouse}, Lect. Notes Comput. Sci. 10856, 389--401 (2018; Zbl 1401.90182)
Full Text: DOI
Takhanov, Rustem
Hybrid VCSPs with crisp and valued conservative templates. (English) Zbl 1457.68130
Okamoto, Yoshio (ed.) et al., 28th international symposium on algorithms and computation, ISAAC 2017, December 9–12, 2017, Phuket, Thailand. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 92, Article 65, 13 p. (2017).
MSC:  68Q25 08A02 08A70 68R07
PDF BibTeX XML Cite
\textit{R. Takhanov}, LIPIcs -- Leibniz Int. Proc. Inform. 92, Article 65, 13 p. (2017; Zbl 1457.68130)
Full Text: DOI
Atserias, Albert; Ochremiak, Joanna
Proof complexity meets algebra. (English) Zbl 1442.03031
Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 110, 14 p. (2017).
MSC:  03F20 68R07
PDF BibTeX XML Cite
\textit{A. Atserias} and \textit{J. Ochremiak}, LIPIcs -- Leibniz Int. Proc. Inform. 80, Article 110, 14 p. (2017; Zbl 1442.03031)
Full Text: DOI
Manurangsi, Pasin; Raghavendra, Prasad
A birthday repetition theorem and complexity of approximating dense CSPs. (English) Zbl 1441.68048
Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 78, 15 p. (2017).
MSC:  68Q10 68R07 68R10 68W25
PDF BibTeX XML Cite
\textit{P. Manurangsi} and \textit{P. Raghavendra}, LIPIcs -- Leibniz Int. Proc. Inform. 80, Article 78, 15 p. (2017; Zbl 1441.68048)
Full Text: DOI
Galanis, Andreas; Goldberg, Leslie Ann; Yang, Kuan
Approximating partition functions of bounded-degree Boolean counting constraint satisfaction problems. (English) Zbl 1441.68155
Chatzigiannakis, Ioannis (ed.) et al., 44th international colloquium on automata, languages, and programming, ICALP 2017, Warsaw, Poland July 10–14, 2017. Proceedings. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 80, Article 27, 14 p. (2017).
MSC:  68R07 68Q25
PDF BibTeX XML Cite
\textit{A. Galanis} et al., LIPIcs -- Leibniz Int. Proc. Inform. 80, Article 27, 14 p. (2017; Zbl 1441.68155)
Full Text: DOI
Carvalho, Catarina; Martin, Barnaby; Zhuk, Dmitriy
The complexity of quantified constraints using the algebraic formulation. (English) Zbl 1441.68087
Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 27, 14 p. (2017).
MSC:  68Q25 08A70 68R07
PDF BibTeX XML Cite
\textit{C. Carvalho} et al., LIPIcs -- Leibniz Int. Proc. Inform. 83, Article 27, 14 p. (2017; Zbl 1441.68087)
Full Text: DOI
Jonsson, Peter; Lagerkvist, Victor; Roy, Biman
Time complexity of constraint satisfaction via universal algebra. (English) Zbl 1441.68093
Larsen, Kim G. (ed.) et al., 42nd international symposium on mathematical foundations of computer science, MFCS 2017, August 21–25, 2017, Aalborg, Denmark. Wadern: Schloss Dagstuhl – Leibniz Zentrum für Informatik. LIPIcs – Leibniz Int. Proc. Inform. 83, Article 17, 15 p. (2017).
MSC:  68Q25 08A40 08A70 68Q17 68Q27 68R07
PDF BibTeX XML Cite
\textit{P. Jonsson} et al., LIPIcs -- Leibniz Int. Proc. Inform. 83, Article 17, 15 p. (2017; Zbl 1441.68093)
Full Text: DOI

Filter Results by …

Document Type
Reviewing State
all top 5
Author
all top 5
Serial
all top 5
Year of Publication
all top 3
Classification
all top 3
Software