pith. machine review for the scientific record. sign in

arxiv: 2604.22742 · v1 · submitted 2026-04-24 · 💻 cs.CC

Recognition: unknown

Boolean PCSPs through the lens of Fourier Analysis

Demian Banakh , Katzper Michno
Authors on Pith no claims yet

Pith reviewed 2026-05-08 08:39 UTC · model grok-4.3

classification 💻 cs.CC
keywords Boolean PCSPFourier analysisminionspolymorphismscoordinate influencesharp thresholdsunate functionspolynomial threshold functions
0
0 comments X

The pith

Boolean PCSPs can be classified as tractable or hard by checking whether their minions preserve coordinate influence under random 2-to-1 minors and exhibit sharp thresholds, as analyzed through Fourier methods on Boolean functions.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper applies Fourier analysis to polymorphisms of Boolean promise constraint satisfaction problems. It extends earlier results on ordered PCSPs by locating two recurring patterns inside Boolean minions that mark whether the associated problem is hard or tractable. One pattern is that the influence of individual coordinates stays stable when the minion is subjected to random 2-to-1 minors. The other is the emergence of sharp thresholds in the functions' behavior. These patterns produce concrete new classifications for minions built from unate functions and from polynomial threshold functions.

Core claim

The central claim is that two phenomena observed across Boolean minions—preservation of coordinate influence under random 2-to-1 minors and the presence of sharp thresholds—serve as reliable indicators of whether the corresponding Boolean PCSP is NP-hard or lies in P. The framework rests on Fourier analysis of the underlying Boolean functions and applies to a wider collection of minions than was previously known, including those consisting of unate or polynomial threshold functions.

What carries the argument

Coordinate influence in Boolean functions, examined via Fourier analysis, together with its stability under random 2-to-1 minor operations on the minion.

If this is right

  • Minions built from unate functions receive explicit hardness or tractability labels via the two phenomena.
  • Minions built from polynomial threshold functions receive explicit hardness or tractability labels via the two phenomena.
  • The same influence-stability and threshold tests apply to Boolean PCSPs outside the ordered case.
  • Problems whose minions fail both tests require separate analytic treatment.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Practical algorithms could be designed to test whether a given minion satisfies the two phenomena without enumerating all polymorphisms.
  • The same Fourier lens may help classify promise problems whose domains are larger than two values.
  • Links may exist between these sharp-threshold behaviors and threshold phenomena already studied in random Boolean functions.

Load-bearing premise

That influence preservation under random 2-to-1 minors and the presence of sharp thresholds remain dependable signals of hardness or tractability once the setting is widened to arbitrary Boolean PCSPs.

What would settle it

A concrete minion of unate functions that preserves coordinate influence under random 2-to-1 minors yet yields a polynomial-time solvable PCSP, or a minion that lacks sharp thresholds yet produces an NP-hard PCSP.

Figures

Figures reproduced from arXiv: 2604.22742 by Demian Banakh, Katzper Michno.

Figure 1
Figure 1. Figure 1: The graph of Ep,q at(3) with respect to (p, q) ∈ [0, 1]2 . We can see that the expected value admits a sharp 0-1 transition as p increases and q decreases simultane￾ously. We now proceed to outline the high-level proof strategy; the full proof is deferred to Section D. Before starting the discussion, we need to introduce new notation in order to simplify presentation. 20We implicitly use the (2-dimensional… view at source ↗
Figure 2
Figure 2. Figure 2: We split the random choice of π into two steps: (1) choosing the coordinate j with which the influential coordinate 2n should be identified, and (2) choosing the pairing of remaining coordinates. We show that after each step, the image of coordinate 2n remains influential with constant probability. This bound allows us to apply Lemma A.5 to h, as long as I Ω[h] ≤ ζ · (2n − 2) for some ζ = ζ(Ω, δ). However,… view at source ↗
read the original abstract

We develop an analytical framework for Boolean Promise Constraint Satisfaction Problems (PCSPs) that studies polymorphisms through the notion of influence from Fourier analysis of Boolean functions. Extending the work of Brakensiek, Guruswami, and Sandeep [ICALP'21] on Ordered PCSPs, we identify two general phenomena in Boolean minions indicative of hardness or tractability: (1) preservation of coordinate influence under random 2-to-1 minors and (2) the presence of sharp thresholds. We demonstrate that these phenomena occur in broader settings than previously established, yielding new hardness/tractability results for minions consisting of unate or polynomial threshold functions.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript develops a Fourier-analytic framework for studying polymorphisms in Boolean Promise Constraint Satisfaction Problems (PCSPs). Extending Brakensiek, Guruswami, and Sandeep (ICALP'21) on ordered PCSPs, it identifies two general phenomena in Boolean minions—(1) preservation of coordinate influence under random 2-to-1 minors and (2) the presence of sharp thresholds—as indicators of hardness or tractability. These phenomena are shown to apply in broader settings, yielding new hardness and tractability results for minions consisting of unate functions and polynomial threshold functions.

Significance. If the central claims hold, the work provides a useful extension of Fourier analysis tools to general Boolean PCSPs, offering concrete new results for unate and PTF minions that were not covered by the ordered case. The framework reuses standard Boolean Fourier analysis while defining new phenomena that could serve as reliable indicators across a wider class of minions; this is a proportionate advance with potential for further classification results.

minor comments (2)
  1. Abstract: the claim that the phenomena 'occur in broader settings than previously established' would be strengthened by a one-sentence statement of at least one concrete new hardness or tractability theorem obtained for unate or PTF minions.
  2. §2 (or wherever the random 2-to-1 minor is introduced): the operation should be defined explicitly with a short formal notation or pseudocode, as it is load-bearing for the first phenomenon even if the subsequent proofs are self-contained.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive summary, significance assessment, and recommendation of minor revision. The referee's description correctly reflects our extension of the Fourier-analytic framework from ordered PCSPs to general Boolean minions, with new results for unate and polynomial threshold functions.

Circularity Check

0 steps flagged

No significant circularity; derivation self-contained via external Fourier analysis and prior non-author work

full rationale

The paper extends the ICALP'21 framework of Brakensiek et al. (distinct authors) by applying standard Fourier-analytic notions of influence and thresholds to Boolean minions in general PCSPs. The two phenomena (influence preservation under random 2-to-1 minors; sharp thresholds) are defined using these external tools and then verified on unate/polynomial-threshold minions to obtain new hardness/tractability theorems. No step reduces by construction to a self-fit, self-citation chain, or author-imported uniqueness theorem; the central claims remain independently verifiable against the cited external results and the paper's own definitions.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on the standard mathematical properties of Fourier analysis over the Boolean hypercube and the definition of minions/polymorphisms from prior PCSP literature; no new free parameters, ad-hoc axioms, or invented entities are introduced in the abstract.

axioms (2)
  • standard math Fourier analysis decomposes Boolean functions into multilinear polynomials and influence is the sum of squared coefficients excluding the constant term.
    Invoked when the paper studies polymorphisms through the notion of influence.
  • domain assumption Minions are closed under composition and contain all projections; this is the standard definition used in PCSP theory.
    Used to frame the Boolean PCSP setting.

pith-pipeline@v0.9.0 · 5397 in / 1449 out tokens · 64806 ms · 2026-05-08T08:39:48.932600+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

75 extracted references · 59 canonical work pages

  1. [1]

    The expressive power of voting polynomials

    James Aspnes et al. “The expressive power of voting polynomials”. In:Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing. STOC ’91. New Orleans, Louisiana, USA: Association for Computing Machinery, 1991, pp. 402–409.isbn: 0897913973. DOI: 10.1145/103418.103461

    work page doi:10.1145/103418.103461 1991

  2. [2]

    (2 +ε)-Sat Is NP-hard

    Per Austrin, Venkatesan Guruswami, and Johan H ˚astad. “(2 +ε)-Sat Is NP-hard”. In:SIAM Journal on Computing46.5 (2017), pp. 1554–1573. DOI: 10.1137/15M1006507

    work page doi:10.1137/15m1006507 2017

  3. [3]

    On the Usefulness of Promises

    Per Austrin, Johan H ˚astad, and Bj¨orn Martinsson. “On the Usefulness of Promises”. In:Pro- ceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 6332–

    2026

  4. [4]

    DOI: 10.1137/1.9781611978971.228

    work page doi:10.1137/1.9781611978971.228

  5. [5]

    Nearly All k-SAT Functions Are Unate

    J ´ozsef Balogh et al. “Nearly All k-SAT Functions Are Unate”. In:Proceedings of the 55th Annual ACM Symposium on Theory of Computing. STOC 2023. Orlando, FL, USA: Association for Computing Machinery, 2023, pp. 958–962.isbn: 9781450399135. DOI: 10.1145/3564246. 3585123

    work page doi:10.1145/3564246 2023

  6. [6]

    Injective hardness condition for PCSPs

    Demian Banakh and Marcin Kozik. “Injective hardness condition for PCSPs”. In:Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science. LICS ’24. Tallinn, Estonia: Association for Computing Machinery, 2024.isbn: 9798400706608. DOI: 10.1145/ 3661814.3662072

    work page arXiv 2024

  7. [7]

    Talk at Dagstuhl Seminar 18231: The Constraint Satisfaction Problem: Complexity and Approximability

    Libor Barto.Cyclic operations in promise constraint satisfaction problems. Talk at Dagstuhl Seminar 18231: The Constraint Satisfaction Problem: Complexity and Approximability. Schloss Dagstuhl, Germany, June 2018

    2018

  8. [8]

    Combinatorial Gap Theorem and Reductions between Promise CSPs

    Libor Barto and Marcin Kozik. “Combinatorial Gap Theorem and Reductions between Promise CSPs”. In:Proceedings of the 2022 ACM-SIAM Symposium on Discrete Algorithms, SODA 2022, Virtual Conference / Alexandria, V A, USA, January 9 - 12, 2022. Ed. by Joseph (Seffi) Naor and Niv Buchbinder. SIAM, 2022, pp. 1204–1220. DOI: 10.1137/1.9781611977073. 50. 39

    work page doi:10.1137/1.9781611977073 2022

  9. [9]

    Polymorphisms, and How to Use Them

    Libor Barto, Andrei Krokhin, and Ross Willard. “Polymorphisms, and How to Use Them”. In: The Constraint Satisfaction Problem: Complexity and Approximability. Ed. by Andrei Krokhin and Stanislav Zivny. Vol. 7. Dagstuhl Follow-Ups. Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, 2017, pp. 1–44.isbn: 978-3-95977-003-3. DOI: 10 . 4230 ...

    2017

  10. [10]

    Algebraic Approach to Promise Constraint Satisfaction

    Libor Barto et al. “Algebraic Approach to Promise Constraint Satisfaction”. In:J. ACM68.4 (July 2021).issn: 0004-5411. DOI: 10.1145/3457606

    work page doi:10.1145/3457606 2021

  11. [11]

    The polynomial method in circuit complexity

    R. Beigel. “The polynomial method in circuit complexity”. In:[1993] Proceedings of the Eigth Annual Structure in Complexity Theory Conference. 1993, pp. 82–95. DOI: 10.1109/SCT.1993. 336538

    work page doi:10.1109/sct.1993 1993

  12. [12]

    Collective coin flipping, robust voting schemes and minima of Banzhaf values

    Michael Ben-Or and Nathan Linial. “Collective coin flipping, robust voting schemes and minima of Banzhaf values”. In:26th Annual Symposium on Foundations of Computer Science (sfcs 1985). 1985, pp. 408–416. DOI: 10.1109/SFCS.1985.15

    work page doi:10.1109/sfcs.1985.15 1985

  13. [13]

    Noise sensitivity of Boolean functions and applications to percolation

    Itai Benjamini, Gil Kalai, and Oded Schramm. “Noise sensitivity of Boolean functions and applications to percolation”. English. In:Publications Mathematiques90.1 (Dec. 1999), pp. 5– 43.issn: 0073-8301. DOI: 10.1007/BF02698830

    work page doi:10.1007/bf02698830 1999

  14. [14]

    Threshold functions

    B. Bollob ´as and A. G. Thomason. “Threshold functions”. In:Combinatorica7.1 (Mar. 1987), pp. 35–38.issn: 1439-6912. DOI: 10.1007/BF02579198

    work page doi:10.1007/bf02579198 1987

  15. [15]

    An Algorithmic Blend of LPs and Ring Equations for Promise CSPs

    Joshua Brakensiek and Venkatesan Guruswami. “An Algorithmic Blend of LPs and Ring Equations for Promise CSPs”. In:Proceedings of the 2019 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 436–455. DOI: 10.1137/1.9781611975482.28

    work page doi:10.1137/1.9781611975482.28 2019

  16. [16]

    New Hardness Results for Graph and Hy- pergraph Colorings

    Joshua Brakensiek and Venkatesan Guruswami. “New Hardness Results for Graph and Hy- pergraph Colorings”. In:31st Conference on Computational Complexity (CCC 2016). Ed. by Ran Raz. Vol. 50. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Ger- many: Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, 2016, 14:1–14:27.isbn: 978-3- 95977...

    work page doi:10.4230/lipics.ccc.2016.14 2016

  17. [17]

    Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy

    Joshua Brakensiek and Venkatesan Guruswami. “Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy”. In:SIAM Journal on Computing50.6 (2021), pp. 1663–1700. DOI: 10.1137/19M128212X

    work page doi:10.1137/19m128212x 2021

  18. [18]

    Conditional Dichotomy of Boolean Ordered Promise CSPs

    Joshua Brakensiek, Venkatesan Guruswami, and Sai Sandeep. “Conditional Dichotomy of Boolean Ordered Promise CSPs”. In:TheoretiCSVolume 2 (Jan. 2023). DOI: 10 . 46298 / theoretics.23.2

    2023

  19. [19]

    The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems

    Joshua Brakensiek et al. “The Power of the Combined Basic Linear Programming and Affine Relaxation for Promise Constraint Satisfaction Problems”. In:SIAM Journal on Computing 49.6 (2020), pp. 1232–1248. DOI: 10.1137/20M1312745

    work page doi:10.1137/20m1312745 2020

  20. [20]

    The Complexity of Promise SAT on Non-Boolean Domains

    Alex Brandts, Marcin Wrochna, and Stanislav ˇZivn´y. “The Complexity of Promise SAT on Non-Boolean Domains”. In:ACM Trans. Comput. Theory13.4 (Sept. 2021).issn: 1942-3454. DOI: 10.1145/3470867

    work page doi:10.1145/3470867 2021

  21. [21]

    Beyond PCSP(1-in-3,NAE)

    Alex Brandts and Stanislav ˇZivn´y. “Beyond PCSP(1-in-3,NAE)”. In:Information and Compu- tation289 (2022), p. 104954.issn: 0890-5401. DOI: https://doi.org/10.1016/j.ic.2022.104954. 40

    work page doi:10.1016/j.ic.2022.104954 2022

  22. [22]

    On Rich 2-to-1 Games , booktitle =

    Mark Braverman, Subhash Khot, and Dor Minzer. “On Rich 2-to-1 Games”. In:12th In- novations in Theoretical Computer Science Conference (ITCS 2021). Ed. by James R. Lee. Vol. 185. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, 2021, 27:1–27:20.isbn: 978-3-95977- 177-1. DOI:...

    work page doi:10.4230/lipics.itcs.2021.27 2021

  23. [23]

    An invariance principle for the multi-slice, with applications

    Mark Braverman et al. “An invariance principle for the multi-slice, with applications”. In: Advances in Mathematics480 (2025), p. 110460.issn: 0001-8708. DOI: https://doi.org/10. 1016/j.aim.2025.110460

    work page arXiv 2025

  24. [24]

    Correlation Decay and Tractability of CSPs

    Jonah Brown-Cohen and Prasad Raghavendra. “Correlation Decay and Tractability of CSPs”. In:43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016). Ed. by Ioannis Chatzigiannakis et al. Vol. 55. Leibniz International Proceedings in Informat- ics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum f ¨ur Informatik, 20...

    work page doi:10.4230/lipics.icalp.2016.79 2016

  25. [25]

    Classifying the Complexity of Con- straints Using Finite Algebras

    Andrei Bulatov, Peter Jeavons, and Andrei Krokhin. “Classifying the Complexity of Con- straints Using Finite Algebras”. In:SIAM Journal on Computing34.3 (2005), pp. 720–742. DOI: 10.1137/S0097539700376676

    work page doi:10.1137/s0097539700376676 2005

  26. [26]

    A Dichotomy Theorem for Nonuniform CSPs

    Andrei A. Bulatov. “A Dichotomy Theorem for Nonuniform CSPs”. In:2017 IEEE 58th Annual Symposium on Foundations of Computer Science (FOCS). 2017, pp. 319–330. DOI: 10.1109/ FOCS.2017.37

    2017

  27. [27]

    A Course in Metric Geometry

    Dmitri Burago, Yuri Burago, and Sergei Ivanov. “A Course in Metric Geometry”. In:Graduate Studies in Math.33 (Jan. 2001)

    2001

  28. [28]

    Distributional andL q norm inequalities for polyno- mials over convex bodies inR n

    Anthony Carbery and James Wright. “Distributional andL q norm inequalities for polyno- mials over convex bodies inR n”. In:Mathematical Research Letters8.3 (2001), pp. 233–248. issn: 1945-001X. DOI: 10.4310/mrl.2001.v8.n3.a1

    work page doi:10.4310/mrl.2001.v8.n3.a1 2001

  29. [29]

    Average Sensitivity and Noise Sensitivity of Polynomial Thresh- old Functions

    Ilias Diakonikolas et al. “Average Sensitivity and Noise Sensitivity of Polynomial Thresh- old Functions”. In:SIAM Journal on Computing43.1 (2014), pp. 231–253. DOI: 10 . 1137 / 110855223

    2014

  30. [30]

    Conditional Hardness for Approximate Col- oring

    Irit Dinur, Elchanan Mossel, and Oded Regev. “Conditional Hardness for Approximate Col- oring”. In:SIAM Journal on Computing39.3 (2009), pp. 843–873. DOI: 10.1137/07068062X

    work page doi:10.1137/07068062x 2009

  31. [31]

    On the fourier tails of bounded functions over the discrete cube

    Irit Dinur et al. “On the fourier tails of bounded functions over the discrete cube”. In: vol. 2006. May 2006, pp. 437–446. DOI: 10.1145/1132516.1132580

    work page doi:10.1145/1132516.1132580 2006

  32. [32]

    On Random Graphs I

    Paul Erd ¨os and Alfred R´enyi. “On Random Graphs I”. In:Publicationes Mathematicae Debre- cen6 (1959), pp. 290–297

    1959

  33. [33]

    On the evolution of random graphs

    Paul Erd ¨os and Alfred R ´enyi. “On the evolution of random graphs”. In:Publ. Math. Inst. Hungary. Acad. Sci.5 (1960), pp. 17–61

    1960

  34. [34]

    SIAM Journal on Computing , title =

    Tom ´as Feder and Moshe Y. Vardi. “The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory”. In:SIAM Journal on Computing28.1 (1998), pp. 57–104. DOI: 10.1137/S0097539794266766

    work page doi:10.1137/s0097539794266766 1998

  35. [35]

    Conjunctions of Unate DNF Formulas: Learning and Structure

    Aaron Feigelson and Lisa Hellerstein. “Conjunctions of Unate DNF Formulas: Learning and Structure”. In:Information and Computation140.2 (1998), pp. 203–228.issn: 0890-5401. DOI: https://doi.org/10.1006/inco.1997.2684. 41

    work page doi:10.1006/inco.1997.2684 1998

  36. [36]

    35 Marek Filakovský, Tamio-Vesa Nakajima, Jakub Opršal, Gianluca Tasinato, and Uli Wagner

    Miron Ficak et al. “Dichotomy for Symmetric Boolean PCSPs”. In:46th International Col- loquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece. Ed. by Christel Baier et al. Vol. 132. LIPIcs. Schloss Dagstuhl - Leibniz-Zentrum f ¨ur Informatik, 2019, 57:1–57:12. DOI: 10.4230/LIPICS.ICALP.2019.57

    work page doi:10.4230/lipics.icalp.2019.57 2019

  37. [37]

    Invariance Principle on the Slice

    Yuval Filmus et al. “Invariance Principle on the Slice”. In:ACM Trans. Comput. Theory10.3 (Apr. 2018).issn: 1942-3454. DOI: 10.1145/3186590

    work page doi:10.1145/3186590 2018

  38. [38]

    Boolean Functions With Low Average Sensitivity Depend On Few Coordi- nates

    Ehud Friedgut. “Boolean Functions With Low Average Sensitivity Depend On Few Coordi- nates”. In:Combinatorica18 (Jan. 1998), pp. 27–35. DOI: 10.1007/PL00009809

    work page doi:10.1007/pl00009809 1998

  39. [39]

    Sharp thresholds of graph properties, and thek-sat problem

    Ehud Friedgut and appendix by Jean Bourgain. “Sharp thresholds of graph properties, and thek-sat problem”. In:Journal of the American Mathematical Society12.4 (May 1999), pp. 1017–1054.issn: 1088-6834. DOI: 10.1090/s0894-0347-99-00305-7

    work page doi:10.1090/s0894-0347-99-00305-7 1999

  40. [40]

    Every monotone graph property has a sharp threshold

    Ehud Friedgut and Gil Kalai. “Every monotone graph property has a sharp threshold”. In: Proceedings of the American Mathematical Society124.10 (1996), pp. 2993–3002.issn: 0002-

    1996

  41. [41]

    DOI: 10.1090/s0002-9939-96-03732-x

    work page doi:10.1090/s0002-9939-96-03732-x

  42. [42]

    Spectral Properties of Threshold Functions

    Craig Gotsman and Nathan Linial. “Spectral Properties of Threshold Functions.” In:Combi- natorica14 (Mar. 1994), pp. 35–50. DOI: 10.1007/BF01305949

    work page doi:10.1007/bf01305949 1994

  43. [43]

    On the hardness of 4-coloring a 3-collorable graph

    V. Guruswami and S. Khanna. “On the hardness of 4-coloring a 3-collorable graph”. In:Pro- ceedings 15th Annual IEEE Conference on Computational Complexity. 2000, pp. 188–197. DOI: 10.1109/CCC.2000.856749

    work page doi:10.1109/ccc.2000.856749 2000

  44. [44]

    d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors

    Venkatesan Guruswami and Sai Sandeep. “d-To-1 Hardness of Coloring 3-Colorable Graphs with O(1) Colors”. In:47th International Colloquium on Automata, Languages, and Program- ming (ICALP 2020). Ed. by Artur Czumaj, Anuj Dawar, and Emanuela Merelli. Vol. 168. Leib- niz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl –...

    2020

  45. [45]

    Bounding the Sensitivity of Polynomial Threshold Functions

    Prahladh Harsha, Adam Klivans, and Raghu Meka. “Bounding the Sensitivity of Polynomial Threshold Functions”. In:Theory of Computing10.1 (2014), pp. 1–26. DOI: 10.4086/toc.2014. v010a001

    work page doi:10.4086/toc.2014 2014

  46. [46]

    On the complexity of H-coloring

    Pavol Hell and Jaroslav Ne ˇsetˇril. “On the complexity of H-coloring”. In:J. Comb. Theory Ser. B48.1 (Feb. 1990), pp. 92–110.issn: 0095-8956. DOI: 10.1016/0095-8956(90)90132-J

    work page doi:10.1016/0095-8956(90)90132-j 1990

  47. [47]

    On the algebraic structure of combinatorial problems

    Peter Jeavons. “On the algebraic structure of combinatorial problems”. In:Theor. Comput. Sci.200.1–2 (June 1998), pp. 185–204.issn: 0304-3975. DOI: 10.1016/S0304-3975(97)00230-2

    work page doi:10.1016/s0304-3975(97)00230-2 1998

  48. [48]

    Closure properties of constraints

    Peter Jeavons, David Cohen, and Marc Gyssens. “Closure properties of constraints”. In:J. ACM44.4 (July 1997), pp. 527–548.issn: 0004-5411. DOI: 10.1145/263867.263489

    work page doi:10.1145/263867.263489 1997

  49. [49]

    The influence of variables on Boolean functions

    J. Kahn, G. Kalai, and N. Linial. “The influence of variables on Boolean functions”. In:[Pro- ceedings 1988] 29th Annual Symposium on Foundations of Computer Science. 1988, pp. 68–80. DOI: 10.1109/SFCS.1988.21923

    work page doi:10.1109/sfcs.1988.21923 1988

  50. [50]

    Social Indeterminacy

    Gil Kalai. “Social Indeterminacy”. In:Econometrica72.5 (Sept. 2004), pp. 1565–1581.issn: 1468-0262. DOI: 10.1111/j.1468-0262.2004.00543.x. 42

    work page doi:10.1111/j.1468-0262.2004.00543.x 2004

  51. [51]

    A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions

    Daniel M. Kane. “A Structure Theorem for Poorly Anticoncentrated Gaussian Chaoses and Applications to the Study of Polynomial Threshold Functions”. In:Proceedings of the 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science. FOCS ’12. USA: IEEE Com- puter Society, 2012, pp. 91–100.isbn: 9780769548746. DOI: 10.1109/FOCS.2012.52

    work page doi:10.1109/focs.2012.52 2012

  52. [52]

    The Correct Exponent for the Gotsman-Linial Conjecture

    Daniel M. Kane. “The Correct Exponent for the Gotsman-Linial Conjecture”. In:2013 IEEE Conference on Computational Complexity. 2013, pp. 56–64. DOI: 10.1109/CCC.2013.15

    work page doi:10.1109/ccc.2013.15 2013

  53. [53]

    On the Hardness of Approximating the Chromatic Number

    Sanjeev Khanna, Nathan Linial, and Shmuel Safra. “On the Hardness of Approximating the Chromatic Number”. In:Combinatorica20 (Mar. 2000), pp. 393–415. DOI: 10 . 1007 / s004930070013

    2000

  54. [54]

    On the power of unique 2-prover 1-round games

    Subhash Khot. “On the power of unique 2-prover 1-round games”. In:Proceedings of the Thiry-Fourth Annual ACM Symposium on Theory of Computing. STOC ’02. Montreal, Quebec, Canada: Association for Computing Machinery, 2002, pp. 767–775.isbn: 1581134959. DOI: 10.1145/509907.510017

    work page doi:10.1145/509907.510017 2002

  55. [55]

    Learning intersections and thresholds of halfspaces

    Adam R. Klivans, Ryan O’Donnell, and Rocco A. Servedio. “Learning intersections and thresholds of halfspaces”. In:Journal of Computer and System Sciences68.4 (2004). Special Issue on FOCS 2002, pp. 808–840.issn: 0022-0000. DOI: https://doi.org/10.1016/j.jcss.2003. 11.002

    work page doi:10.1016/j.jcss.2003 2004

  56. [56]

    The Complexity of 3-Colouring H-Colourable Graphs

    Andrei Krokhin and Jakub Opr ˇsal. “The Complexity of 3-Colouring H-Colourable Graphs”. In:2019 IEEE 60th Annual Symposium on Foundations of Computer Science (FOCS). 2019, pp. 1227–1239. DOI: 10.1109/FOCS.2019.00076

    work page doi:10.1109/focs.2019.00076 2019

  57. [57]

    A new line of attack on the dichotomy conjecture

    G ´abor Kun and Mario Szegedy. “A new line of attack on the dichotomy conjecture”. In: Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. STOC ’09. Bethesda, MD, USA: Association for Computing Machinery, 2009, pp. 725–734.isbn: 9781605585062. DOI: 10.1145/1536414.1536512

    work page doi:10.1145/1536414.1536512 2009

  58. [58]

    Ineffectiveness for Search and Undecidability of PCSP Meta-Problems

    Alberto Larrauri. “ Ineffectiveness for Search and Undecidability of PCSP Meta-Problems ”. In:2025 IEEE 66th Annual Symposium on Foundations of Computer Science (FOCS). Los Alami- tos, CA, USA: IEEE Computer Society, Dec. 2025, pp. 1313–1350. DOI: 10.1109/FOCS63196. 2025.00070

    work page doi:10.1109/focs63196 2025

  59. [59]

    Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems

    Noam Lifshitz. “Hypergraph Removal Lemmas via Robust Sharp Threshold Theorems”. In: Discrete Analysis11 (Aug. 2020).issn: 2397-3129. DOI: 10.19086/da.14165

    work page doi:10.19086/da.14165 2020

  60. [60]

    Probabilistic properties of graphs with large connectivity

    G. A. Margulis. “Probabilistic properties of graphs with large connectivity”. Russian. In: Probl. Peredachi Inf.10.2 (1974), pp. 101–109.issn: 0555-2923

    1974

  61. [61]

    Unate Truth Functions

    Robert McNaughton. “Unate Truth Functions”. In:IRE Trans. Electron. Comput.10.1 (1961), pp. 1–6. DOI: 10.1109/TEC.1961.5219145

    work page doi:10.1109/tec.1961.5219145 1961

  62. [62]

    Efficient Computation of the Shapley Value for Game-Theoretic Net- work Centrality

    T. P. Michalak et al. “Efficient Computation of the Shapley Value for Game-Theoretic Net- work Centrality”. In:Journal of Artificial Intelligence Research46 (Apr. 2013), pp. 607–650. issn: 1076-9757. DOI: 10.1613/jair.3806

    work page doi:10.1613/jair.3806 2013

  63. [63]

    Noise stability of functions with low influences: Invariance and optimality

    Elchanan Mossel, Ryan O’Donnell, and Krzysztof Oleszkiewicz. “Noise stability of functions with low influences: Invariance and optimality”. In: vol. 171. Nov. 2005, pp. 21–30.isbn: 0- 7695-2468-0. DOI: 10.1109/SFCS.2005.53. 43

    work page doi:10.1109/sfcs.2005.53 2005

  64. [64]

    A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks

    Ramasuri Narayanam and Yadati Narahari. “A Shapley Value-Based Approach to Discover Influential Nodes in Social Networks”. In:IEEE Transactions on Automation Science and En- gineering8.1 (2011), pp. 130–147. DOI: 10.1109/TASE.2010.2052042

    work page doi:10.1109/tase.2010.2052042 2011

  65. [65]

    Extremal properties of polynomial threshold functions

    R. O’Donnell and R.A. Servedio. “Extremal properties of polynomial threshold functions”. In:18th IEEE Annual Conference on Computational Complexity, 2003. Proceedings.2003, pp. 3–

    2003

  66. [66]

    DOI: 10.1109/CCC.2003.1214406

    work page doi:10.1109/ccc.2003.1214406 2003

  67. [67]

    New degree bounds for polynomial threshold func- tions

    Ryan O’Donnell and Rocco A. Servedio. “New degree bounds for polynomial threshold func- tions”. In:Proceedings of the Thirty-Fifth Annual ACM Symposium on Theory of Computing. STOC ’03. San Diego, CA, USA: Association for Computing Machinery, 2003, pp. 325–334. isbn: 1581136749. DOI: 10.1145/780542.780592

    work page doi:10.1145/780542.780592 2003

  68. [68]

    2014 , address =

    Ryan O’Donnell.Analysis of Boolean Functions. Cambridge University Press, June 2014.isbn: 9781107471542. DOI: 10.1017/cbo9781139814782

    work page doi:10.1017/cbo9781139814782 2014

  69. [69]

    On a Nonsymmetric Version of the Khinchine-Kahane Inequal- ity

    Krzysztof Oleszkiewicz. “On a Nonsymmetric Version of the Khinchine-Kahane Inequal- ity”. In:Stochastic Inequalities and Applications. Birkh ¨auser Basel, 2003, pp. 157–168.isbn: 9783034880695. DOI: 10.1007/978-3-0348-8069-5 11

    work page doi:10.1007/978-3-0348-8069-5 2003

  70. [70]

    Multilinear extensions of games

    Guillermo Owen. “Multilinear extensions of games”. In:The Shapley Value. Cambridge Uni- versity Press, Oct. 1988, pp. 139–152.isbn: 9780511528446. DOI: 10.1017/cbo9780511528446. 011

    work page doi:10.1017/cbo9780511528446 1988

  71. [71]

    An approximate zero-one law

    Lucio Russo. “An approximate zero-one law”. In:Zeitschrift f ¨ur Wahrscheinlichkeitstheorie und Verwandte Gebiete61.1 (1982), pp. 129–139.issn: 1432-2064. DOI: 10.1007/bf00537230

    work page doi:10.1007/bf00537230 1982

  72. [72]

    Optimal algorithms and inapproximability results for every CSP?

    Thomas J. Schaefer. “The Complexity of Satisfiability Problems”. In:Proceedings of the Tenth Annual ACM Symposium on Theory of Computing. STOC ’78. San Diego, California, USA: Association for Computing Machinery, 1978, pp. 216–226.isbn: 9781450374378. DOI: 10. 1145/800133.804350

    work page arXiv 1978

  73. [73]

    A Method for Evaluating the Distribution of Power in a Committee System

    L.S. Shapley and Martin Shubik. “A Method for Evaluating the Distribution of Power in a Committee System”. In:Political Economy, Oligopoly and Experimental Games. Edward Elgar Publishing, Sept. 1999, pp. 510–515.isbn: 9781035378135. DOI: 10 . 4337 / 9781035378135 . 00048

    1999

  74. [74]

    Testably Learning Polynomial Threshold Functions

    Lucas Slot, Stefan Tiegel, and Manuel Wiedmer. “Testably Learning Polynomial Threshold Functions”. In:Advances in Neural Information Processing Systems 37. NeurIPS 2024. Neural Information Processing Systems Foundation, Inc. (NeurIPS), 2024, pp. 3781–3831. DOI: 10. 52202/079017-0124

    2024

  75. [75]

    A Proof of the CSP Dichotomy Conjecture , year =

    Dmitriy Zhuk. “A Proof of the CSP Dichotomy Conjecture”. In:J. ACM67.5 (Aug. 2020). issn: 0004-5411. DOI: 10.1145/3402029. A A proof of the Influence Preservation Lemma Before we proceed to the proof of Influence Preservation Lemma, we first make some general observations about reasonable distributions and prove some technical lemmas. 44 A.1 A closer look...

    work page doi:10.1145/3402029 2020