joshuagrochow

joshuagrochow, 4 months ago (edited 4 months ago) to random

The Hoffman-Singleton graph can apparently be constructed as the Cayley graph of a magma: https://en.wikipedia.org/wiki/Hoffman%E2%80%93Singleton_graph#Construction_on_a_groupoid/magma

It:

• isn't a quasigroup
• has a 2-sided identity (0,0,0)
• isn't associatve
• isn't commutative

What is this magma?? Anyone have any ideas?

I think when the first coordinate is zero, the corresponding 25 elements are a copy of the cyclic group of order 25 (generated by (0,1,1)).

#algebra #graph

joshuagrochow, 4 months ago to random

Rogers's Equivalence Theorem (https://en.wikipedia.org/wiki/Admissible_numbering#Rogers'_equivalence_theorem) is more amazing than it sounds.

(Plus a question about it at the end)

It says that any two admissible numberings (aka programming languages: https://en.wikipedia.org/wiki/Numbering_(computability_theory)) of the partial computable functions are computably isomorphic.

To see how amazing this is: it's standard that you can write a program to compile Python programs to Java programs and vice versa. Just from those two compilers, Rogers's Equivalence Thm implies that there is a total computable function f that transforms Java programs into input-output-equivalent Python programs that is 1-to-1 (not so surprising) and onto - every Python program arises as f(p) for some Java program p, and p and f(p) compute the same function. That is pretty surprising!

#computability #programming #logic

joshuagrochow, 9 months ago to bluesky

I still find old-Twitter and #bluesky better than #mastodon for news, events, and info, but mastodon better than either for fostering medium-length convos. Just me?

Or are there #feditips for using mastodon I'm still not up on? I follow hashtags and ppl, use lists, and try to look at who my followds follow

joshuagrochow, 1 year ago to random

Whew! This result literally made me breathe a sigh of relief: https://arxiv.org/abs/2109.13702.

Let me explain why I'm excited, what their result is, and at the end, the key breadcrumb of the proof in one line (for those who know the statement of Tannaka duality).

(h/t @plain_simon)

1/8

joshuagrochow, 1 year ago to random

I kinda wish all papers had a one-paragraph section, similar in size and style to the Acknowledgement, on origin of the project. I think it'd make a lot more of the process of science more transparent, esp to newcomers.

#academia #openscience #research

joshuagrochow, 3 months ago to ComputerScience

The notion of reduction in #ComputerScience, and particularly the notion of NP-completeness lead to surprising connections between a variety of fields.

Two of my favorite NP-complete problems are:

• Kidney Donor Matching Markets (better algorithms literally save lives)
• Knot Genus (a seemingly very abstract problem in topology)

Like, oh, you thought you were working on kidney donor matching markets? Surprise your #algorithm can be used to find the genus of a knot! And vice versa!

Big caveat here is: NP-completeness of the decision problems doesn't, by itself, tell you the same relationship between the approximation problems, nor between heuristic algos that might not always get the exact optimum, nor FPT. But TheoryCS has different kinds of reductions that can tell you relationships between those things too!

Which makes me wonder if knot genus is hard to approximate...

h/t @CihanPostsThms for their post on the birdsite about knot genus

joshuagrochow, 10 months ago to physics

Anyone have good references and/or favorite examples of the use of generating functions (in the sense of combinatorics) in probability or physics? #combinatorics #physics #probability

joshuagrochow, 2 months ago to Matrix

No one defines a #matrix as "a thing that transforms like a matrix". Why define tensors that way?

Array=numbers in a (possibly high-dim) grid
Matrix=array representation of a linear map* in a chosen basis
Tensor=array representation of a multilinear map in a chosen basis

(* or linear endomorphism, or bilinear function, but we'll get there.)

Vectors=1-tensors, but not all 1-index arrays are vectors
Matrices=2-tensors, but not all 2-ary arrays are matrices

Similarly, not all k-ary arrays are tensors. Some examples:

Christoffel symbols aren't a tensor because they aren't (multi)linear in all of their arguments.

Most "tensors" in #MachineLearning #AI aren't tensors b/c they aren't multilinear - they are just multi-dim arrays of numbers. To say an array is (or represents) a tensor is to endow it with additional multilinear structure, same as with arrays vs matrices vs linear structure.

(1/4)

#tensors #matrix #algebra

joshuagrochow, 1 year ago (edited 1 year ago) to random

Is there a guide somewhere for making good, #accessible #hybrid (in-person/online) #workshops and #conferences for #academia?

If not, I want to make it. Let me know if you want to help.

(Lots of stuff on the web about this, but not for academic events, and it's not a perfect fit. Also lots of stuff that's "top 5 tips" or in blog post format - also not what I want. I want something I can hand to an organizer who was planning an in-person only event and have a hope that they might actually turn it into a good hybrid event. Or for someone who wants to plan a hybrid event from the get-go.)

joshuagrochow, 1 year ago to random

@christianp Thanks for moderating, and, in this particular case, helping moderate a large volume of spam.

joshuagrochow, 1 year ago (edited 1 year ago) to random

Quiver algebras have the property that, in any fixed dim, rep(Q) is a vector space. Is there some characterization of which algebras have this property?

(Unital algebras seem to be ruled out. Except kQ is unital, but for those you can just "throw away" the 1, and all the primitive idempotents in fact, and it works. I guess it's because they have an k-linear decomposition (kQ = E \oplus I) where E is the subalgebra of idempotents and I is an ideal, and any representation of Q is uniquely determined by what it does on I (which is a non-unital subalgebra), since it has no choice of what to do on E. Not quite sure what the right general principle is here though...)

#RepresentationTheory #quivers

joshuagrochow, 3 months ago to ArtificialIntelligence

I love big-O notation when doing theory to focus on big ideas,

but constants can matter in practice, and often do!

(Leading constants moreso. To focus on leading constant but still ignore lower order terms you can use asymptotic equality ~)

(Inspired by @ccanonne on the birdiste.)

#complexity #AsymptoticBehaviour #algorithms

joshuagrochow, 4 months ago to random

I posted a brief note about Hensel lifting for systems of polynomial equations when number of eqns ≠ number of vars.

Purely expository b/c I couldn't find it anywhere, even though it's elementary. Feedback appreciated before I decide about posting on arXiv!

https://home.cs.colorado.edu/~jgrochow/hensel-notes.pdf

#AlgebraicGeometry #algebra

joshuagrochow, 1 year ago to random

Is there a term for when a class of equations has sol'ns over an extension field iff it has sol'ns over the ground field?

Examples:

1. Linear eqns
2. Eqns saying that two fin. dim. rep'ns of a fin. generated algebra are equivalent

Non-ex: eqns saying two 3-tensors are isomorphic

#Algebra #AlgebraicGeometry

joshuagrochow, 10 months ago to random

An affine variety can be embedded into proj space in many ways. Do they all give the same Betti tables? Or are the Betti tables somehow related? So much I've found starts w projective varieties / graded rings. Are there good keywords to search for to understand 👆?

#AlgebraicGeometry #algebra

joshuagrochow, 1 year ago to random

Is there a language where all 7 days of the week start with different letters/sounds?

joshuagrochow, 1 year ago to random

Inaugural EC Gender #Inclusion Workshop @ #EC2023 https://sites.google.com/view/ecgiw23/home?authuser=0

Deadlines for grad students & postdocs:

• Rising star spotlight talk app due June 12th
• Poster session app due June 26th

All EC attendees:

• Childcare app due June 6th

Organized by an awesome group of PhD students! ->

Kate Donahue https://katedonahue.me
Bailey Flanigan https://sites.google.com/andrew.cmu.edu/baileyflanigan/home
Ezinne Nwankwo https://ezinnenwa.com
Maneesha Papireddygari https://papireddygari.github.io

joshuagrochow, 3 months ago (edited 3 months ago) to Pubtips

Can anyone explain to me how the "Subscribe to Open" (S2O) model (like MSP's, here: https://msp.org/publications/s2o/) is supposed to work and be sustainable?

I understand the mechanics, what I don't understand is what the equilibrium is supposed to be. If a journal regularly goes open because of S2O, won't ppl come to expect that, and then there's a tragedy of the commons issue?

#openaccess #publishing #academia

joshuagrochow, 8 months ago to Economics

Is there a term for when a company comes in, offers something for free(ish) to take customers from pre-existing competitors - while taking a loss, dipping into their other profits - thereby squashing the competitors, only to then ramp prices back up to exactly what their competitors were before?

(The example I have in mind is streaming services vs cable - where it's not just about prices about also about presence & frequency of ads - but surely there are others.)

#economics #business #streaming

joshuagrochow, 8 months ago to academia

Since the start of the (still ongoing) pandemic, almost anything that had a sign-up date for faculty (professional development opportunities, pedagogy training, hosting summer research undergrads, etc) has had to extend its deadline b/c of not getting enough ppl signing up. Yet no one seems to be doing anything about the burnout & overwork of faculty that that is so clearly a sign of.

#academia #CovidIsNotOver

joshuagrochow, 5 months ago (edited 5 months ago) to generativeAI

I don't understand something about the ACM's new policy on the use of #GenerativeAI in ACM publications (FAQ here: https://www.acm.org/publications/policies/frequently-asked-questions). They say it's OK subject to conditions.

One condition is: "That these [AI] systems do not plagiarize, misrepresent, or falsify content in ACM submissions."

How can this ever be verified, even by the author? One can try to search for direct copying, but it seems impossible to find non-verbatim plagiarization that lacks proper attribution?

(Unless you trained your own generative AI on your own corpus and can certify what's in that corpus. But clearly that's not what most people who use these systems are doing.)

joshuagrochow, 4 months ago (edited 4 months ago) to math

If R is a filtered ring, but filtered by an ordered commutative monoid (not necessarily N), is the associated graded a flat deformation?

#algebra #math #AlgebraicGeometry

joshuagrochow, 3 months ago to rust

Your first #rust error message is like

How long have you been living this way? You don't have to live this way. Let me show you something better.

joshuagrochow, 1 year ago to random

Is there an "addition function" that works simultaneously for the determinant and the permanent?

#complexity #permanent #determinant

There is a simple function that is multiplicative for both the determinant and permanent simultaneously, namely (\det(A \oplus B) = \det(A)\det(B)) and (perm(A \oplus B)=perm(A)perm(B)).

The map (A,B \mapsto A \oplus B) is a projection in Valiant's sense - every coordinate of the output is either one of the input coordinates or a constant.

Perm and det both have "addition functions" separately. They are slightly more complicated, but still projections. That is, there are projections f,g such that det(f(A,B))=det(A) + det(B) [Malod & Portier, Prop 7 https://doi.org/10.1016/j.jco.2006.09.006] and perm(g(A,B)) = perm(A) + perm(B) [see https://cstheory.stackexchange.com/a/51348/129].

But is there a single projection h such that

det(h(A,B)) = det(A) + det(B)
and
perm(h(A,B)) = perm(A) + perm(B)
?

I don't know, but would love to find out!

https://cstheory.stackexchange.com/q/51370/129

joshuagrochow, 8 months ago to community

If the way you build #community is entirely through in-person-only events with no SARS-CoV2 / #COVID precautions, you are excluding high-risk people from your community.