Questions tagged [algebra]
The algebra tag has no usage guidance.
105 questions
28
votes
6
answers
3k
views
Alternative proofs of Schwartz–Zippel lemma
I'm only aware of two proofs of Schwartz–Zippel lemma. The first (more common) proof is described in the wikipedia entry. The second proof was discovered by Dana Moshkovitz.
Are there any other ...
- 3,674
6
votes
5
answers
285
views
What is/are the lower bounds for finding a something akin to complex residue?
Given a function $\sum_{i=-N}^N{c_i x^i}$:
$f(x) \equiv \sum_{i=-N}^N{c_i x^i}$ where $c_i$ is an integer; $0 \le c_i \le a$ for some $a$.
The constant $c_0$ is desired, and we start with only $f(x)...
16
votes
3
answers
745
views
Hardness Guarantees for AES
Many public-key cryptosystems have some kind of provable security. For example, the Rabin cryptosystem is provably as hard as factoring.
I wonder whether such kind of provable security exists for ...
- 16.6k
4
votes
1
answer
220
views
Optimizing multiplication in a partly commutative semigroup
Let us say I have a semigroup M and its basis B. I know which elements of B commute.
What is the most efficient way to do multiplication in such a semigroup?
Essentially, this is a question of how ...
- 9,011
6
votes
2
answers
673
views
Proof of a unique homomorphism from an initial object
What is the proof that there is only one homomorphism from an initial object to another object?
- 293