Or Zamir

(Asst) Professor, department of Computer Science, Tel Aviv University @TelAvivUni
Formerly: @the_IAS, @Princeton

[Or Zamir @OREAXEAX]

@thomasahle @rrwilliams I'm traveling so will only be able to read in a few days, but this wouldn't surprise me at all. The real barrier seems to be getting to one exponential (as double exponential seems inherent in my low-deg algorithm that both solutions are using).

[Or Zamir @OREAXEAX]

Note this implies that (in this range) odd cycle detection is faster than MM when there are few even cycles of the following size.
Fun exercise: Show you can detect triangles in O(n^2+#C4(G)) time.

[Or Zamir @OREAXEAX]

With my first graduating MSc student Or Stern, we show an ~O(n^2+t) listing algorithm for even cycles of each length C8-C16, as well as for "all cycles of size up to 2k" for any k. Previously, this was known only for C4 and C6.

https://t.co/lf8ft7EtqL

[Or Zamir @OREAXEAX]

Sidenote: This was the first time I found brainstorming with AI tools useful to any extent. While all main ideas are biologically-generated, I added a short appendix detailing in length what benefit I did (and didn't) manage to get out of these tools and how + some extra thoughts

[Or Zamir @OREAXEAX]

Exciting result: k-Coloring is in (2-eps_k)^n time, where eps_k>0 for every fixed k!
Algorithms faster than the 2^n time needed to compute the chromatic number were previously known only for k<=6.
https://t.co/wzDIexHgjv

[Or Zamir @OREAXEAX]

This was among my fav problems for 5 yrs: In my PhD, I proved the k=5,6 cases and the general result for all sparse graphs (ICALP21 best student paper); In my postdoc I extended it to all almost-regular graphs (STOC23). Very satisfyingly, the final algorithm uses tools from both.

[Or Zamir @OREAXEAX]

@PoratEitan Each eps_k is a theoretically positive number (but not significantly more than that).

[Or Zamir @OREAXEAX]

“What are you doing?” asked the search committee chair.

“I’m preparing to answer your questions,” I said.

“With ChatGPT?”

“Yes,” I said. “How else would I do it?”

https://t.co/iWOKpj78Rb

[Or Zamir @OREAXEAX]

Hash algorithms are usually measured by the number of probes. We suggest considering locality instead: how far do we need to get from the first probe attempt? We show that the quadratic locality of linear-probing is optimal, explaining its practical appeal
https://t.co/4qJ5DQQ7Qz

[Or Zamir @OREAXEAX]

@wtgowers @__alpoge__ It seems like a very feasible brute-force after using an uncited prior work (Vitushkin's) as the basis to how the space should be limited to force a constant Jacobian while giving potential 3-to-1 collisions

[Or Zamir @OREAXEAX]

@kevinroose It is severely underwhelming in hindsight, because it turns out that decades of failed proof attempts were not because it is a very hard important question - but simply because it is false and humans were unable to come up with the concrete counter-example

[Or Zamir @OREAXEAX]

@Pooyahat I have yet to see a PhD thesis which is a one line counterexample.

[Or Zamir @OREAXEAX]

The recurring theme here is that humans are very bad with finding counter-examples. If mathematicians had the will to code, optimize and run smart enumerations we would have seen these refutations decades ago. The main advantage of AI here is generically allowing us to run these.

[levent @__alpoge__]

hello there the jacobian conjecture is false thanx to my close friend akhil for asking about it and my other close friend fable for working during the world cup final

((1+xy)^3 z + y^2 (1+xy) (4+3xy), y + 3 x (1+xy)^2 z + 3 x y^2 (4+3xy), 2 x - 3 x^2 y - x^3 z): \C^3\to \C^3, has jacobian determinant -2, and sends (0, 0, -1/4), (1, -3/2, 13/2), and (-1, 3/2, 13/2) to (-1/4, 0, 0)

[Foresight Institute @foresightinst]

Or Zamir from @TelAvivUni on AI security
via cryptography.

[Or Zamir @OREAXEAX]

@praveshkkothari We should probably recalibrate what things we so far accepted not for being interesting but for being "a worthy exercise" -- which unfortunately may cover a lot of undergrad/master/early grad research. It'd solve the attribution as we might no longer call this research anyway...

[Or Zamir @OREAXEAX]

@thomasahle I find it that then I need to repeat myself every time about writing style and many other default "quirks", but I agree it's probably not worth it.

[Or Zamir @OREAXEAX]

Whenever new models come out I test their research abilities with some "small" open problems I left in recent papers. I "caught" GPT5.6 going back to an unrelated conversation from months ago to try and use a construction I told it about for the current given problem. 1/3

[Or Zamir @OREAXEAX]

More often than not, the same people had given it significant context or suggested research directions in other conversations - which it still reads. Capturing another form of a major problem with the current AI proofs: a complete lack of attribution for the used ideas. 3/3

[Or Zamir @OREAXEAX]

In the final output, no mention of going back to that previous context appeared. This isn't surprising or new, but we should keep this in mind when people claim that AI models solved a research problem from a simple prompt or without guidance or context. 2/3

[Thomas Bloom @thomasfbloom]

This is definitely not the case. This is a frequent issue with AI-generated proofs and papers: they use ideas and proof strategies taken from the literature without proper citation.