Is there a constant-space accumulator for a set of numbers to make it easy to test for set membership?

My question: What data structure or algorithm could I use to solve the following set membership problem efficiently?


Imagine I am generating a random 32-bit integer every second, and adding it to a list of N integers. Imagine that each time I generate an integer, I ship it (and any other information I might have easy access to) off to a client. Later, the client will submit an integer (along with any other information I have given it), and I want to be able to quickly determine if a given integer has ever appeared in my set, but I want to do it in constant time, using a small, constant amount of memory. In other words, I don’t want to just keep all of my generated numbers in a list or hash table and check the submitted integer against this list. Ideally, adding a number to this set is a constant-time operation. I do not ever need to delete numbers from the set.

Option 1: I could use a bloom filter and add each number to the bloom filter. Unfortunately, the set membership test would be probabilistic, but I could make the filter big enough to reduce my probability of a false positive quite low. I’m open to this approach, but want to know what other options I could have.

Option 2: I have been reading about cryptographic accumulators. If each of the numbers I was generating were prime, I believe I could use an RSA accumulator to store a single accumulator value of constant size. Each time I add a new prime to my set, I add it to the accumulator, then I generate its witness as well and ship both the number and the witness to my client. Later, the client would submit the integer it is testing and the witness, and I would be able to quickly determine if the number being submitted is in fact a member of my set or not. Possible problems: I need to be able to hash to a prime number deterministically. (Not the end of the world, but adds complexity) I think I have to update my witness values as I add new values to the accumulator. Lastly: My understanding of accumulators is rudimentary.

Possible modifications: 1: Would this be any easier if subsequent values in my chain of numbers were somehow dependent upon previous values in some way? You could imagine some sort of non-cryptographic hash chain, whose current hash value includes enough information about its previous values that it could quickly determine, “Yep, if my current hash value is X, and you submit Y, Y definitely was a previous member of my chain.” 2: If I understand them correctly, accumulators seem like a very space-efficient way to store sets of prime numbers (and perhaps other values), but in the literature they all assume potential adversaries. In my case, I don’t need my witness be be unforgeable, so I would think that would make the problem much easier to solve. Perhaps it just means that I get to use smaller constants (so I don’t have to use RSA-2048?). Or perhaps this simplifies my problem even further? 3: What if the “random” values I was generating were known to be increasing, or were simply timestamps? (I still need to know if that particular timestamp were ever used)

Related problems: This seems a lot like having a lot of hash values in a Merkle tree or hash chain (blockchain), and wanting to be able to determine if a particular hash value were ever seen in the chain, without having to store every value that had been seen in the chain. I’m hopeful that with the additional concept of generating a “witness” value of some sort to be stored along with the number, the server can make a membership determination with much less overhead than having to store all of the numbers. This also seems similar to a verifiable log or authenticated dictionary.

WooCommerce and Membership: Can I fetch the membership from the product?

I am working on a membership system. We have added our own in-app-purchase (IAP) plugin to communicate with Apple, Amazon, Google Play and Roku. So far, everything is working as we expect. The issue I am currently having is when I validate the receipt, I want to fetch the membership plan from the product, not a subscription, although I could get it to use that if I must. I have tested with a subscription too but still no luck. Since this will be an automated verification system the subscription seems to be more of a hassle as a simple product seems more ideal for our use case.

I have tried using:

$  _membershipPlan = \wc_memberships_get_memberships_from_subscription($  _productObj); 

Where $ _productObj has been a simple product and a simple subscription but it never returns the membership.

What I am trying to do is once the reciept is validated, I fetch the WC_Product (product or subscription) then I want to see what membership is attached to it and apply this to the user.

I have searched for this in their Docs and on Google and I haven’t been able to find anything. My last resort would be to write my own WP_Query object to handle this, as it seems I might have to do.

Something to note, the method wc_memberships_get_memberships_from_subscription is looking for _subscription_id but the membership doesn’t even have this as meta for it. It does have _product_ids stored in a serialized array which will be annoying to query. Not sure why this would be the case but this is where I am stuck.

Hoping someone here would have a little insight on this or point me in the right direction.

Thank you for your time.

Using conditional logic on fields in gravity form based on Paid Memberships Pro membership level

I’m trying to use conditional logic to hide/show fields in my gravity form based on user’s membership level determined by Paid Memberships Pro. I’ve tried all different variations using {user:membership_level} in a hidden field. Then, using conditional logic on selected fields, I’ve tried to hide/show based on the value of the membership level.

Any help would be appreciated. Is my meta key ({user:membership_level}) incorrect?

Proving Problems are Undecidable/ Semi decidable? E.g. Halting Problem, Membership Problem?

I am having issues finding similarities in different cases where a problem such as the Halting Problem or the Accept-Λ problem is reduced to the Membership problem to prove that it is semi-decidable and undecidable.

Each one is different to the last in some way which is a lot of information

I get the individual processes but is there a ‘method’ that I can apply to other problems that I haven’t come across before e.g. reducing the Uniform Halting Problem to the Halting Problem?

Check user membership of current user in security group using javascript

I am working on SharePoint 2016 on-premises environment. I need to implement the some functionality based on the result whether the currently logged-in user is a part of a security group or not using javascript/jquery. Can someone advise on how I can check the user membership in a security group?

Does a TM that recognizes K-SAT membership also recognizes K-TAUT in linear time with high probability?

Lets Take K $ > 2$ .

In this case we know that K-TAUT $ \in$ coNP-Complete and K-SAT $ \in$ NP-Complete. We also know that K-TAUT $ \subseteq$ K-SAT since every string $ x=\{0, 1\}^*$ that belongs to K-TAUT also belong to K-SAT but no vice-versa.

Lets take two Turing Machine, $ S$ and $ T$ such that:

$ S(x)=1$ $ iif$ $ x$ $ \in$ K-SAT

$ T(x)=1$ $ iif$ $ x$ $ \in$ K-TAUT

we leave out the working details of the two machines, let’s just say that both establish membership of the string through a brute force check on the input.

My question is: if we feed $ x$ to $ S$ and $ S$ accept (output $ 1$ ) in $ time$ $ O(n)$ , does this mean that $ Pr[x$ $ \in$ K-TAUT$ ]$ $ =1$ $ -$ $ (2^{-n})$ ?

Thank you for your time.

Sharepoint Groups : all users (membership) vs custom built groups

I don’t know if this had been answered already, but here’s my case : I have a Sharepoint site and some subsites are meant to be shared with external people. However I don’t want those external people to see the root site.

One of my colleagues created an AD account for this and we gave it a O365 license so it has access to the Sharepoint as well.

Since I gave read access to the “all users (membership)” account on the root site, this external account also has access to it, but I don’t want this.

So my question is : Would it be better to get rid of the “all users (membership)” and build new groups with all the users who have access to the Sharepoint ? I’d say it’s definitely better but I would need to update it every time a new person arrive in the company. I’ve started doing it for a few cases, but the update is what takes a lot of time.

We use Sharepoint Online.

Any suggestion is gladly welcome. Thanks !

Configure a SharePoint 2016 Web Application with Forms Based Authentication with a LDAP membership provider

I am trying to Configure a SharePoint 2016 Web Application with Forms Based Authentication with a LDAP membership provider, I followed the same steps mentioned in the below articles.

Configure a SharePoint 2013 Web Application with Forms Based Authentication with a LDAP membership provider

FBA with LDAP provider

when i browse web application and select forms-based authentication i get the following error in uls logs.

STS Call: Failed to issue new security token. Exception: System.ServiceModel.FaultException`1[Microsoft.IdentityModel.Tokens.FailedAuthenticationException]: The security token username and password could not be validated. (Fault Detail is equal to Microsoft.IdentityModel.Tokens.FailedAuthenticationException: The security token username and password could not be validated.).

An exception occurred when trying to issue security token: The security token username and password could not be validated.

i want to verify for SharePoint 2016 below dlls version number is valid or not?

type=”Microsoft.Office.Server.Security.LdapMembershipProvider, Microsoft.Office.Server, Version=16.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c”

Microsoft.Office.Server.Security.LdapRoleProvider, Microsoft.Office.Server, Version=16.0.0.0, Culture=neutral, PublicKeyToken=71e9bce111e9429c

Can potential x actual set membership evade set theoretic paradoxes?

If we informally view a set as a container, and view set membership as an invitation for entry into a container. If that invitation is fulfilled, i.e. there is an instance of entry into the container, then that kind of membership is actual, if never fulfilled then it is potential.

Lets denote set membership by $ \in$ ,actual membership by $ \in^!$ , and potential membership by $ \in^*$ , the latter is definable in terms of the former ones as a set membership that is not actual.

We can sketch that in spatial closed figures, so membership would be invitation for entry of objects to the compartment of space inside the closed figure. Obviously the figure itself even if it invites itself for entry (thus it would be a member of itself) cannot actuate this invitation, so in this circumstance it would be merely a potential member of itself.

Now the rules about set memberships (in $ \sf FOL(=,\in, \in^!)$ ) would be:

Membership: $ \forall x \forall y \ (y \in^! x \to y \in x)$

Extensionality: Two sets are equal only if they have the same members

$ $ \forall x \forall y \ [\forall z (z \in x \leftrightarrow z \in y ) \to x=y]$ $

Comprehension: If $ \phi^!$ is a formula that only use predicates of equality $ =$ and actual membership $ \in^!$ , in which the symbol $ “x”$ doesn’t occur free, then all closures of:$ $ \exists x \forall y \ (y \in x \leftrightarrow \phi^!)$ $ ; are axioms.

Define: $ A(x) \iff \forall y \ (y \in x \to y \in^! x)$

Where $ A$ means Actual set; so a set is actual if and only if its membership is its actual membership, for example the empty set $ \emptyset$ .

Actuality: $ \forall x [A(x) \leftrightarrow \forall y \in x (A(y))]$

Actualization: if $ \phi$ is a formula in which $ x$ is not free, that only use predicates $ “=”$ and $ “\in”$ , then all closures of: $ $ \forall y (\phi \to A(y)) \to \exists x \forall y (y \in x \leftrightarrow \phi)$ $ ; are axioms.

Induction: if $ \mathcal Q$ is a definable predicate, then all closures of: $ $ \mathcal Q(\emptyset) \land \forall \text{natural } n \ [\mathcal Q(n) \to \mathcal Q (n \cup \{n\})] \ \to \forall \text{natural } n \ (\mathcal Q(n))$ $ ; are axioms.

Where $ natural$ is defined as finite von Neumann ordinal in the customary manner [using membership relation $ \in$ ].

This theory would interpret Zermelo set theory over the realm of Actual sets, and it can actually prove its consistency over that realm. I’m not sure if it can even interpret ZFC? However this theory has a universal set!

Having a universal set, this theory definitly looks suspecious, so the chances of an inconsistency are high.

Question 1: is there a clear inconsistency with this theory?

Question 2: had there been prior known endeavors along lines of actual and potential membership that is similar to the above account?

Is Waterdeep faction membership mutually exclusive?

Waterdeep: Dragon Heist has multiple factions which PCs can belong to, or join. These include Lord’s Alliance, Emerald Enclave, Bregan D’aerthe, etc. If a PC matches the requisites for more than one of these factions, can he join multiple ones?

For example, could a drow druid join both Emerald Enclave and Bregan D’aerthe? Or is membership exclusive, and PCs have to pick a single faction to work with?

Yesterday, I told my players that they could belong to multiple factions as long as their missions and actions didn’t cross each other. But it was a DM’s call in the moment, and I wanted to confirm my ruling.