2025-11-24T00:19:17.738116

Overlap Gap and Computational Thresholds in the Square Wave Perceptron

Benedetti, Bogdanov, Malatesta et al.
Square Wave Perceptrons (SWPs) form a class of neural network models with oscillating activation function that exhibit intriguing ``hardness'' properties in the high-dimensional limit at a fixed constraint density $α= O(1)$. In this work, we examine two key aspects of these models. The first is related to the so-called \emph{overlap-gap property}, that is a disconnectivity feature of the geometry of the solution space of combinatorial optimization problems proven to cause the failure of a large family of solvers, and conjectured to be a symptom of algorithmic hardness. We identify, both in the storage and in the teacher-student settings, the emergence of an overlap gap at a threshold $α_{\mathrm{OGP}}(δ)$, which can be made arbitrarily small by suitably increasing the frequency of oscillations $1/δ$ of the activation. This suggests that in this small-$δ$ regime, typical instances of the problem are hard to solve even for small values of $α$. Second, in the teacher-student setup, we show that the recovery threshold of the planted signal for message-passing algorithms can be made arbitrarily large by reducing $δ$. These properties make SWPs both a challenging benchmark for algorithms and an interesting candidate for cryptographic applications.
academic

বর্গ তরঙ্গ পার্সেপ্ট্রনে ওভারল্যাপ ফাঁক এবং গণনামূলক থ্রেশহোল্ড

মৌলিক তথ্য

  • পেপার আইডি: 2506.05197
  • শিরোনাম: Overlap Gap and Computational Thresholds in the Square Wave Perceptron
  • লেখক: Marco Benedetti, Andrej Bogdanov, Enrico M. Malatesta, Marc Mézard, Gianmarco Perrupato, Alon Rosen, Nikolaj I. Schwartzbach, Riccardo Zecchina
  • শ্রেণীবিভাগ: cond-mat.dis-nn (ঘনীভূত পদার্থ - বিশৃঙ্খল সিস্টেম এবং স্নায়ু নেটওয়ার্ক)
  • প্রকাশনার সময়: ২০২৫ সালের ১৩ অক্টোবর (arXiv প্রাক-প্রিন্ট)
  • পেপার লিঙ্ক: https://arxiv.org/abs/2506.05197

সারসংক্ষেপ

বর্গ তরঙ্গ পার্সেপ্ট্রন (SWP) হল দোলনশীল সক্রিয়করণ ফাংশন সহ স্নায়ু নেটওয়ার্ক মডেলের একটি শ্রেণী যা স্থির সীমাবদ্ধতা ঘনত্ব α = O(1) এর উচ্চ-মাত্রিক সীমায় আকর্ষণীয় "কঠোরতা" বৈশিষ্ট্য প্রদর্শন করে। এই গবেষণা এই মডেলগুলির দুটি মূল দিক পরীক্ষা করে: প্রথমত, ওভারল্যাপ ফাঁক সম্পত্তি (overlap-gap property), যা সমন্বয় অপ্টিমাইজেশন সমস্যার সমাধান স্থানের জ্যামিতির একটি অসংযুক্ত বৈশিষ্ট্য, যা বিস্তৃত সমাধানকারীর ব্যর্থতার কারণ হতে প্রমাণিত হয়েছে এবং অ্যালগরিদমিক কঠোরতার লক্ষণ হিসাবে অনুমান করা হয়েছে; দ্বিতীয়ত, শিক্ষক-শিক্ষার্থী সেটিংয়ে, বার্তা প্রেরণ অ্যালগরিদমের পুনরুদ্ধার থ্রেশহোল্ড δ হ্রাস করে নির্বিচারে বড় হতে পারে। এই বৈশিষ্ট্যগুলি SWPকে অ্যালগরিদমিক চ্যালেঞ্জের জন্য একটি চ্যালেঞ্জিং বেঞ্চমার্ক এবং ক্রিপ্টোগ্রাফিক অ্যাপ্লিকেশনের জন্য একটি আকর্ষণীয় প্রার্থী করে তোলে।

গবেষণা পটভূমি এবং প্রেরণা

সমস্যার পটভূমি

এই গবেষণা পার্সেপ্ট্রন সমস্যার গণনামূলক জটিলতার উপর দৃষ্টি নিবদ্ধ করে, বিশেষত পরিসংখ্যানগত পদার্থবিজ্ঞান এবং তাত্ত্বিক কম্পিউটার বিজ্ঞানের ছেদ ক্ষেত্রে কঠোরতা বিশ্লেষণ। পার্সেপ্ট্রন সবচেয়ে মৌলিক স্নায়ু নেটওয়ার্ক মডেল হিসাবে, এর শেখা এবং সংরক্ষণ সমস্যা আরও জটিল স্নায়ু নেটওয়ার্কের গণনামূলক সীমাবদ্ধতা বোঝার ক্ষেত্রে গুরুত্বপূর্ণ।

মূল সমস্যা

১. পরিসংখ্যানগত-গণনামূলক ফাঁক: অনেক সীমাবদ্ধতা সন্তুষ্টি সমস্যায়, তথ্য-তাত্ত্বিকভাবে সম্ভাব্য পরামিতি অঞ্চল এবং পরিচিত বহুপদী সময় অ্যালগরিদম কাজ করতে পারে এমন অঞ্চলের মধ্যে একটি ফাঁক রয়েছে

२. জ্যামিতিক কঠোরতা বৈশিষ্ট্য: সমাধান স্থানের জ্যামিতিক কাঠামো কীভাবে অ্যালগরিদমের গণনামূলক জটিলতাকে প্রভাবিত করে

३. ওভারল্যাপ ফাঁক সম্পত্তি: অ্যালগরিদমিক কঠোরতার পূর্বাভাস সূচক হিসাবে জ্যামিতিক অসংযোগ

গবেষণার প্রেরণা

  • বিদ্যমান বাইনারি পার্সেপ্ট্রন (যেমন ABP, SBP) পরিসংখ্যানগত-গণনামূলক ফাঁক প্রদর্শন করে, কিন্তু তাদের কঠোরতা থ্রেশহোল্ড তুলনামূলকভাবে স্থির
  • অ্যালগরিদমিক ব্যর্থতার জ্যামিতিক কারণগুলি আরও ভালভাবে বোঝার জন্য কঠোরতা বৈশিষ্ট্য সামঞ্জস্য করতে পারে এমন একটি মডেলের প্রয়োজন
  • ক্রিপ্টোগ্রাফিতে চরম কঠোরতা বৈশিষ্ট্য সহ মডেলগুলির প্রয়োগ সম্ভাবনা অন্বেষণ করা

মূল অবদান

१. বর্গ তরঙ্গ পার্সেপ্ট্রন মডেল প্রবর্তন: দোলনশীল সক্রিয়করণ ফাংশন φ_δ(h) = -sgn(sin(πh/δ)) সহ একটি নতুন পার্সেপ্ট্রন মডেল প্রস্তাব করা

२. ওভারল্যাপ ফাঁক থ্রেশহোল্ড বিশ্লেষণ: সংরক্ষণ এবং শিক্ষক-শিক্ষার্থী সেটিংয়ে ওভারল্যাপ ফাঁক থ্রেশহোল্ড α_OGP(δ) চিহ্নিত করা, যা দোলন ফ্রিকোয়েন্সি 1/δ বৃদ্ধি করে নির্বিচারে ছোট হতে পারে

३. চরম কঠোরতা বৈশিষ্ট্য: δ→0 সীমায় প্রমাণ করা যে যেকোনো α>0 এর জন্য ওভারল্যাপ ফাঁক বিদ্যমান, যা নির্দেশ করে যে এমনকি খুব ছোট সীমাবদ্ধতা ঘনত্বেও সমস্যা কঠিন

४. পুনরুদ্ধার থ্রেশহোল্ডের সামঞ্জস্যতা: শিক্ষক-শিক্ষার্থী সেটিংয়ে, বার্তা প্রেরণ অ্যালগরিদমের পুনরুদ্ধার থ্রেশহোল্ড δ হ্রাস করে নির্বিচারে বড় হতে পারে তা প্রদর্শন করা

५. ক্রিপ্টোগ্রাফিক প্রয়োগের সম্ভাবনা: পার্সেপ্ট্রন-ভিত্তিক ক্রিপ্টোগ্রাফিক নির্মাণ (যেমন সংঘর্ষ-প্রতিরোধী হ্যাশ ফাংশন) এর জন্য তাত্ত্বিক ভিত্তি প্রদান করা

পদ্ধতির বিস্তারিত ব্যাখ্যা

কাজের সংজ্ঞা

সংরক্ষণ সমস্যা

ডেটাসেট D = {(x^μ, y^μ)}^P_{μ=1} দেওয়া, ওজন ভেক্টর w ∈ {-1,+1}^N খুঁজে পান যাতে:

y^μ = φ(1/√N · w · x^μ) ∀μ ∈ [P]

যেখানে x^μ_i ~ N(0,1) স্বাধীন এবং সমানভাবে বিতরণ করা, y^μ = ±1 সমান সম্ভাবনা সহ এলোমেলো।

শিক্ষক-শিক্ষার্থী সমস্যা

একটি "শিক্ষক" ওজন w* ∈ {-1,+1}^N বিদ্যমান, লেবেল শিক্ষক দ্বারা উৎপন্ন:

y^μ = φ(1/√N · w* · x^μ) ∀μ ∈ [P]

লক্ষ্য শিক্ষক ওজন পুনরুদ্ধার করা বা যেকোনো সমাধান খুঁজে পাওয়া।

মডেল স্থাপত্য

বর্গ তরঙ্গ সক্রিয়করণ ফাংশন

φ_δ(h) = -sgn(sin(πh/δ))

এই সক্রিয়করণ ফাংশনের সময়কাল T = 2δ, পরামিতি δ দ্বারা দোলন ফ্রিকোয়েন্সি নিয়ন্ত্রণ করা হয়।

ফুরিয়ার প্রতিনিধিত্ব

φ_δ(h) = -4/π ∑_{n=0}^∞ 1/(2n+1) sin((2n+1)πh/δ)

ওভারল্যাপ ফাঁক সম্পত্তি বিশ্লেষণ

m-OGP সংজ্ঞা

প্রদত্ত উদাহরণ D এর জন্য, সেট S_m(q,ε,D) সংজ্ঞায়িত করুন যা m কনফিগারেশনের সমস্ত সেট {w^1,...,w^m} অন্তর্ভুক্ত করে, যা সন্তুষ্ট করে:

१. প্রতিটি w^a সীমাবদ্ধতা সন্তুষ্ট করে २. যেকোনো a≠b এর জন্য: q < (w^a·w^b)/N < q+ε

যদি Pr_DS_m(q,ε,D) ≠ ∅ → 0 (N→∞), তাহলে m-OGP সম্পত্তি বলা হয়।

ক্লোন পার্টিশন ফাংশন

N_m(q;D) = ∑_{w^1,...,w^m} ∏_{a=1}^m X_D(w^a) ∏_{a<b} δ(q - w^a·w^b/N)

অ্যানিলিং মুক্ত এন্ট্রপি

φ^{ann}_m(q) = lim_{N→∞} 1/(mN) ln E_D N_m(q;D)

প্রযুক্তিগত উদ্ভাবন পয়েন্ট

१. সামঞ্জস্যপূর্ণ কঠোরতা: পরামিতি δ এর মাধ্যমে সমস্যার গণনামূলক কঠোরতা ক্রমাগত সামঞ্জস্য করা, δ→0 এ চরম কঠোরতা অর্জন করা

२. জ্যামিতিক বিশ্লেষণ: সমাধান স্থানের জ্যামিতিক কাঠামো বিশ্লেষণ করতে পরিসংখ্যানগত পদার্থবিজ্ঞান পদ্ধতি ব্যবহার করা

३. বহু-স্কেল বিশ্লেষণ: বিভিন্ন নির্ভুলতার তাত্ত্বিক পূর্বাভাস প্রদান করতে অ্যানিলিং অনুমান এবং প্রতিলিপি প্রতিসাম্য বিশ্লেষণ একত্রিত করা

४. ছোট δ সীমার বিশ্লেষণাত্মক চিকিত্সা: ক্ষোভ সম্প্রসারণের মাধ্যমে সীমাবদ্ধ ক্ষেত্রে সঠিকভাবে বিশ্লেষণ করা

পরীক্ষামূলক সেটআপ

তাত্ত্বিক বিশ্লেষণ পদ্ধতি

  • অ্যানিলিং গণনা: OGP থ্রেশহোল্ডের উপরের সীমা অনুমান প্রদান করা
  • প্রতিলিপি প্রতিসাম্য (RS) বিশ্লেষণ: আরও সঠিক মুক্ত এন্ট্রপি গণনা
  • ছোট δ সম্প্রসারণ: δ→0 সীমার জন্য ক্ষোভ বিশ্লেষণ

সংখ্যাসূচক পরীক্ষা

  • সিস্টেম আকার: N = 4000-5000
  • নমুনা সংখ্যা: প্রতিটি ডেটা পয়েন্টের জন্য গড়ে 80 স্বাধীন নমুনা
  • অ্যালগরিদম পরীক্ষা: শক্তিশালী অনুমানিত বার্তা প্রেরণ (RAMP) অ্যালগরিদম ব্যবহার করা

মূল্যায়ন সূচক

  • সন্তুষ্টি থ্রেশহোল্ড: α_c(δ) - সমাধান বিদ্যমান থাকার সমালোচনামূলক সীমাবদ্ধতা ঘনত্ব
  • OGP থ্রেশহোল্ড: α_OGP(m,δ) - m-ওভারল্যাপ ফাঁক উপস্থিত হওয়ার থ্রেশহোল্ড
  • শিক্ষক থ্রেশহোল্ড: α_T(δ) - শিক্ষক অনন্য সমাধান হওয়ার থ্রেশহোল্ড
  • অ্যালগরিদম থ্রেশহোল্ড: α_alg(δ) - RAMP অ্যালগরিদম ব্যর্থ হওয়ার থ্রেশহোল্ড

পরীক্ষামূলক ফলাফল

প্রধান ফলাফল

সন্তুষ্টি থ্রেশহোল্ড

  • δ→∞ এর জন্য, ABP এর ক্ষমতা পুনরুদ্ধার করা α^{ABP}_c ≈ 0.833
  • δ→0 এর জন্য, ক্ষমতা উপরের সীমার দিকে প্রবণ α_c(0) = 1
  • RS অনুমান ছোট δ সীমায় অ্যানিলিং উপরের সীমার সাথে মিলিত হয়

ওভারল্যাপ ফাঁক থ্রেশহোল্ড

δ→0 সীমায়:

α^{ann}_{OGP}(m) = 1/m

অতএব α_(∞) = 0, যার অর্থ যেকোনো α > 0 এর জন্য ওভারল্যাপ ফাঁক বিদ্যমান।

শিক্ষক-শিক্ষার্থী সমস্যার ফলাফল

  • শিক্ষক থ্রেশহোল্ড α_T(δ) δ→0 এ 1 এর দিকে প্রবণ
  • পুনরুদ্ধার থ্রেশহোল্ড α_r(δ) δ হ্রাস করে নির্বিচারে বড় হতে পারে
  • বিপরীত ওয়েজ পার্সেপ্ট্রনে পুনরুদ্ধার থ্রেশহোল্ডের বিচ্যুতি অর্জন করা

অ্যালগরিদম কর্মক্ষমতা বিশ্লেষণ

RAMP অ্যালগরিদমের কর্মক্ষমতা পরীক্ষা দেখায়:

  • অ্যালগরিদম থ্রেশহোল্ড α_alg(δ) δ হ্রাসের সাথে হ্রাস পায়
  • RS অনুমানের OGP থ্রেশহোল্ড এবং অ্যালগরিদম থ্রেশহোল্ডের মধ্যে একটি ফাঁক বিদ্যমান
  • δ = 1.5 এর জন্য, ফাঁক শূন্যের কাছাকাছি, ABP এর পরিচিত ফলাফলের সাথে সামঞ্জস্যপূর্ণ

কেস স্টাডি: বিপরীত ওয়েজ পার্সেপ্ট্রন

সক্রিয়করণ ফাংশন ডিজাইন করে:

φ(h) = sgn((h-γ)h(h+γ))

γ = γ* = √(2log2) এ, পুনরুদ্ধার থ্রেশহোল্ড বিচ্যুত হয়:

α_r ≈ (π/8)(log2)^{-3/2} ε^{-1}

যেখানে ε = |γ - γ*|।

সম্পর্কিত কাজ

পার্সেপ্ট্রন তত্ত্ব

  • ক্লাসিক্যাল ফলাফল: Gardner-Derrida এর সংরক্ষণ ক্ষমতা বিশ্লেষণ
  • বাইনারি পার্সেপ্ট্রন: ABP এবং SBP মডেলের কঠোরতা বৈশিষ্ট্য
  • পরিসংখ্যানগত-গণনামূলক ফাঁক: Bansal-Spencer অ্যালগরিদম এবং তথ্য-তাত্ত্বিক সীমার মধ্যে পার্থক্য

ওভারল্যাপ ফাঁক সম্পত্তি

  • সংজ্ঞা এবং উন্নয়ন: Gamarnik-Zadik এর মূল সংজ্ঞা
  • অ্যালগরিদম ব্যর্থতার প্রমাণ: স্থিতিশীল অ্যালগরিদম শ্রেণীর জন্য সর্বজনীন ফলাফল
  • প্রয়োগের উদাহরণ: র্যান্ডম গ্রাফ, সন্তুষ্টি সমস্যা ইত্যাদি

পরিসংখ্যানগত পদার্থবিজ্ঞান পদ্ধতি

  • প্রতিলিপি পদ্ধতি: পার্টিশন ফাংশন এবং পর্যায় রূপান্তর গণনা করা
  • জ্যামিতিক পর্যায় রূপান্তর: সমাধান স্থান ক্লাস্টারিং কাঠামোর পরিবর্তন
  • বার্তা প্রেরণ: BP এবং AMP অ্যালগরিদমের তাত্ত্বিক বিশ্লেষণ

উপসংহার এবং আলোচনা

প্রধান উপসংহার

१. চরম কঠোরতা: SWP δ→0 সীমায় চরম গণনামূলক কঠোরতা প্রদর্শন করে, যেকোনো ইতিবাচক সীমাবদ্ধতা ঘনত্বে ওভারল্যাপ ফাঁক বিদ্যমান

२. সামঞ্জস্যতা: পরামিতি δ এর মাধ্যমে সমস্যার কঠোরতা বৈশিষ্ট্য ক্রমাগত সামঞ্জস্য করা যায়

३. ক্রিপ্টোগ্রাফিক সম্ভাবনা: এই বৈশিষ্ট্যগুলি SWPকে ক্রিপ্টোগ্রাফিক প্রয়োগের জন্য একটি শক্তিশালী প্রার্থী করে তোলে

४. জ্যামিতিক বোঝাপড়া: দোলনশীল সক্রিয়করণ ফাংশন সমাধান স্থানের সংযোগযোগ্যতা ভেঙে দেয়, অ্যালগরিদম ব্যর্থতার কারণ হয়

সীমাবদ্ধতা

१. প্রতিলিপি প্রতিসাম্য: RS বিশ্লেষণ নির্দিষ্ট পরামিতি অঞ্চলে অনির্ভুল হতে পারে, উচ্চতর প্রতিলিপি প্রতিসাম্য ভাঙার প্রয়োজন

२. সীমিত আকারের প্রভাব: তাত্ত্বিক বিশ্লেষণ তাপগতিবিদ্যা সীমার উপর ভিত্তি করে, প্রকৃত সীমিত সিস্টেম বিচ্যুতি থাকতে পারে

३. অ্যালগরিদম সীমাবদ্ধতা: শুধুমাত্র RAMP অ্যালগরিদম পরীক্ষা করা হয়েছে, অন্যান্য অ্যালগরিদমের কর্মক্ষমতা এখনও গবেষণা করা প্রয়োজন

४. পরামিতি নির্ভরতা: ফলাফল δ পরামিতির নির্বাচনের উপর দৃঢ়ভাবে নির্ভর করে

ভবিষ্যত দিকনির্দেশনা

१. সম্পূর্ণ RSB বিশ্লেষণ: সম্পূর্ণ প্রতিলিপি প্রতিসাম্য ভাঙার তত্ত্ব বিকাশ করা

२. অন্যান্য অ্যালগরিদম: বর্ণালী পদ্ধতি, SDP শিথিলকরণ ইত্যাদি অন্যান্য অ্যালগরিদম শ্রেণী পরীক্ষা করা

३. ক্রিপ্টোগ্রাফিক বাস্তবায়ন: SWP এর উপর ভিত্তি করে নির্দিষ্ট ক্রিপ্টোগ্রাফিক প্রোটোকল বিকাশ করা

४. সাধারণীকরণ: অন্যান্য দোলনশীল সক্রিয়করণ ফাংশনের অনুরূপ বৈশিষ্ট্য গবেষণা করা

গভীর মূল্যায়ন

সুবিধা

१. তাত্ত্বিক উদ্ভাবন: প্রথমবারের মতো দোলনশীল সক্রিয়করণ ফাংশনের গণনামূলক কঠোরতা পদ্ধতিগতভাবে অধ্যয়ন করা, নতুন তাত্ত্বিক দৃষ্টিভঙ্গি প্রদান করা

२. পদ্ধতি কঠোর: পরিসংখ্যানগত পদার্থবিজ্ঞান এবং তাত্ত্বিক কম্পিউটার বিজ্ঞানের পদ্ধতি একত্রিত করে, বিশ্লেষণ ব্যাপক এবং গভীর

३. ফলাফল গভীর: কঠোরতা সামঞ্জস্যের নতুন প্রক্রিয়া আবিষ্কার করা, অ্যালগরিদম সীমা বোঝার জন্য গুরুত্বপূর্ণ

४. প্রয়োগ সম্ভাবনা: ক্রিপ্টোগ্রাফির জন্য নতুন তাত্ত্বিক সরঞ্জাম প্রদান করা

অপূর্ণতা

१. প্রযুক্তিগত জটিলতা: বিশ্লেষণ পদ্ধতি অত্যন্ত জটিল, ফলাফলের অ্যাক্সেসযোগ্যতা সীমিত করতে পারে

२. পরীক্ষামূলক যাচাইকরণ: প্রধানত তাত্ত্বিক বিশ্লেষণের উপর নির্ভর করে, সংখ্যাসূচক পরীক্ষা তুলনামূলকভাবে সীমিত

३. ব্যবহারিকতা: চরম পরামিতি (δ→0) এ প্রকৃত বাস্তবায়নযোগ্যতা সন্দেহজনক

४. সাধারণীকরণ: ফলাফলের সর্বজনীনতা এবং অন্যান্য সমস্যায় প্রয়োগযোগ্যতা আরও যাচাইকরণ প্রয়োজন

প্রভাব

१. তাত্ত্বিক অবদান: গণনামূলক জটিলতা তত্ত্বের জন্য নতুন বিশ্লেষণ সরঞ্জাম এবং দৃষ্টিভঙ্গি প্রদান করা

२. আন্তঃশৃঙ্খলা মূল্য: পরিসংখ্যানগত পদার্থবিজ্ঞান, মেশিন লার্নিং এবং ক্রিপ্টোগ্রাফি সংযুক্ত করা

३. অনুপ্রেরণা তাৎপর্য: জ্যামিতিক কঠোরতা সম্পর্কে আরও গবেষণা অনুপ্রাণিত করতে পারে

४. ব্যবহারিক সম্ভাবনা: ক্রিপ্টোগ্রাফি এবং অ্যালগরিদম ডিজাইনে প্রয়োগ সম্ভাবনা

প্রযোজ্য পরিস্থিতি

१. তাত্ত্বিক গবেষণা: গণনামূলক জটিলতা তত্ত্ব এবং পরিসংখ্যানগত পদার্থবিজ্ঞান গবেষণা

२. অ্যালগরিদম বিশ্লেষণ: বার্তা প্রেরণ অ্যালগরিদমের সীমা এবং ব্যর্থতা প্রক্রিয়া বোঝা

३. ক্রিপ্টোগ্রাফি ডিজাইন: কঠোরতা অনুমানের উপর ভিত্তি করে নতুন ক্রিপ্টোগ্রাফিক আদিম বিকাশ করা

४. মেশিন লার্নিং: স্নায়ু নেটওয়ার্ক প্রশিক্ষণের গণনামূলক বাধা বোঝা

সংদর্ভ

পেপারটি 75টি সম্পর্কিত সংদর্ভ উদ্ধৃত করে, প্রধানত অন্তর্ভুক্ত:

१. Rosenblatt (1958): পার্সেপ্ট্রনের মূল সংজ্ঞা २. Gardner & Derrida (1989): পার্সেপ্ট্রন সংরক্ষণ ক্ষমতার ক্লাসিক্যাল ফলাফল ३. Gamarnik & Zadik (2019): ওভারল্যাপ ফাঁক সম্পত্তির সংজ্ঞা ४. Baldassi et al. (2015): বাইনারি পার্সেপ্ট্রনের অ্যালগরিদম থ্রেশহোল্ড বিশ্লেষণ ५. Mézard & Montanari (2009): পরিসংখ্যানগত পদার্থবিজ্ঞান পদ্ধতির পদ্ধতিগত পরিচয়

এই পেপারটি তাত্ত্বিক কম্পিউটার বিজ্ঞান এবং পরিসংখ্যানগত পদার্থবিজ্ঞানের ছেদ ক্ষেত্রে গুরুত্বপূর্ণ অবদান রাখে, সামঞ্জস্যপূর্ণ কঠোরতার বর্গ তরঙ্গ পার্সেপ্ট্রন মডেল প্রবর্তন করে, অ্যালগরিদম কঠোরতার জ্যামিতিক উৎস বোঝার জন্য নতুন সরঞ্জাম এবং দৃষ্টিভঙ্গি প্রদান করে। আবিষ্কৃত চরম কঠোরতা বৈশিষ্ট্য শুধুমাত্র তাত্ত্বিক মূল্য নয়, বরং ক্রিপ্টোগ্রাফিক প্রয়োগের জন্য নতুন সম্ভাবনাও খুলে দেয়।