Hacker News<p>Computational Complexity of Neural Networks</p><p><a href="https://lunalux.io/introduction-to-neural-networks/computational-complexity-of-neural-networks/" rel="nofollow noopener" translate="no" target="_blank"><span class="invisible">https://</span><span class="ellipsis">lunalux.io/introduction-to-neu</span><span class="invisible">ral-networks/computational-complexity-of-neural-networks/</span></a></p><p><a href="https://mastodon.social/tags/HackerNews" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>HackerNews</span></a> <a href="https://mastodon.social/tags/ComputationalComplexity" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>ComputationalComplexity</span></a> <a href="https://mastodon.social/tags/NeuralNetworks" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>NeuralNetworks</span></a> <a href="https://mastodon.social/tags/AIResearch" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>AIResearch</span></a> <a href="https://mastodon.social/tags/MachineLearning" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>MachineLearning</span></a> <a href="https://mastodon.social/tags/TechTrends" class="mention hashtag" rel="nofollow noopener" target="_blank">#<span>TechTrends</span></a></p>
#computationalcomplexity
1 post1 participant0 posts today
Harm Derksen will be talking about "Invariant Theory and [Computational] Complexity" in tomorrow's online CodEx Seminar: https://www.math.colostate.edu/~king/codex/
Tue Jan 28, 2025 10am Pacific
Sign up on the website for the zoom link
www.math.colostate.eduCodEx SeminarCodEx Seminar
Replied in thread
@onlineparallels Adding more hashtags for visibility of what's shaping up to be a cool online event paralleling ITCS '25!
sites.google.comITCS'25 online parallelWhat we do
Welcome! This site is about an online parallel event for the conference ITCS'25 that aims to provide an inclusive platform for the TCS researchers unable to attend the conference in person. We believe that everyone, regardless of their ability to attend physical conferences, deserves the
Heard of AIM SQuaREs? (if you haven't, you should: https://aimath.org/programs/squares/)
Now we have Simons-Jane Circles (https://simons.berkeley.edu/participate/circles-call-proposals), at what I'd call the intersection of #Math and
#CS (#TheoryCS).
Both fund small collaborations (~3-6) for 3-4 weeklong visits over 2-3 yrs.
aimath.orgSQuaREs | American Inst. of Mathematics
Given a decision problem Π, I need a name for the polytope constructed by taking the convex hull of the characteristic vectors (or binary inputs of fixed length) corresponding to "yes" instances. If nobody has a better suggestion I might use "the characteristic polytope of Π". OTOH, for $reasons I'd much rather use something more standard / widespread.
#Tensors Everywhere in #Complexity
Me! At the colloquium.
With connections to geometric complexity theory, graph isomorphism, group isomorphism, #quantum entanglement, and post-quantum-secure cryptosystems.
Online Fri Oct 25 2024 at IU Bloomington CS: https://events.iu.edu/siceiub/event/1663944-tensors-everywhere-in-complexity
Indiana University CalendarTensors everywhere in complexityJoshua Grochow, Associate Professor, Dept. of Computer Science and (by courtesy) Mathematics at the University of Colorado Boulder, where he is a m...
Apparently I missed that Zhuk posted a *simplified* proof of the CSP Dichotomy Conjecture back in January: https://arxiv.org/abs/2404.01080
I'd really love to understand all of this!
arXiv.orgA simplified proof of the CSP Dichotomy Conjecture and XY-symmetric operationsWe develop a new theory of strong subalgebras and linear congruences that are defined globally. Using this theory we provide a new proof of the correctness of Zhuk's algorithm for all tractable CSPs on a finite domain, and therefore a new simplified proof of the CSP Dichotomy Conjecture. Additionally, using the new theory we prove that composing a weak near-unanimity operation of an odd arity $n$ we can derive an $n$-ary operation that is symmetric on all two-element sets. Thus, CSP over a constraint language $Γ$ on a finite domain is tractable if and only if there exist infinitely many polymorphisms of $Γ$ that are symmetric on all two-element sets.
Continued thread
Turns out rational approximation of irrationals is related to the Hartmanis-Stearns '65 Conjecture on real-time computability, from the same paper that introduced basic complexity classes like DTIME(f(n)). And sqrt(2) makes an appearance!
The Hartmanis-Stearns real-time computability conjecture is (equivalent to):
For a real number r, if there is an algorithm that computes the first n digits in O(n) time (for all n), then r is either rational or transcendental.
And, coming from this, sqrt(2) has an even cooler connection:
If the 1st n digits of sqrt(2) can't be computed in O(n) time, then n-bit integers can't be multiplied in O(n) time. -Lipton & Regan https://rjlipton.wpcomstaging.com/2012/06/15/why-the-hartmanis-stearns-conjecture-is-still-open/
(But...sqrt(2) probably isn't the only number for which the above is true. Still a cool connection, I think.)
Gödel's Lost Letter and P=NP · Why The Hartmanis-Stearns Conjecture Is Still OpenA missed? or forgotten? connection from 1976 Richard Brent is an illustrious Australian mathematician and computer scientist. He is known for Brent’s Theorem, which shows that a parallel algo…
It's well known you can find a solution to the linear Diophantine equation
\[ a_1x_1 + a_2x_2 + \ldots + a_nx_n = c \]
in polynomial time using the Extended Euclidean Algorithm. But I haven't been able to find a clear answer for the complexity of finding a non-negative integer solution, that is, \( x_i \geq 0 \).
The unbounded knapsack problem is NP-complete, and this is the case where the weights and costs are equal, but I'm not sure that the NP-hardness reduction applies given that additional constraint.
I have also found a statement that the "multidimensional knapsack problem" is NP-hard even with a single row, which seems to match this, but I lack a copy of Papadimitriou and Steiglitz to verify that statement, and can't figure out the reduction.
If this problem is NP-hard, then I'm also interested in showing that a related problem is also NP-hard: if we have one non-negative solution, can we find a second one? I'm trying to answer a question about the special case \( c = \sum_{i=1}^{n} a_i \).
I'm going to be talking about Algorithmic CGT in India in a few weeks. I really want to start with the fundamentals of #PSPACE, so I want to present the Boolean Formula Game (https://en.wikipedia.org/wiki/Formula_game). Whenever I talk about a game, I like to play it with the audience.
So... I coded a working version: http://kyleburke.info/DB/combGames/booleanFormula.html
It's not particularly fun, mostly because it's often very easy to win as the True player. (I didn't implement any deep strategies to generate more interesting formulas. Advice is welcome!)
Nevertheless, I'm very excited to use this next week and in future talks. #CombinatorialGames #ComputationalComplexity #WebGames
en.wikipedia.orgFormula game - Wikipedia
Replied in thread
A question that came to mind, possibly interesting or trivial: for TV (ℓ₁) there is no dependence on n in the entropy loss. For ℓ∞ a logarithmic dependence pops up.
Does it suddenly appear? Or does it gradually appear when one looks at ℓp guarantees for increasing p? #hashing #computationalcomplexity #theoreticalcomputerscience #theoreticalCompSci #randomness