cevi

8 ms·

31.
Quantified CSPs are either PSPACE-complete or inside Pi_2(arxiv.org)
2 points by cevi 2y ago|0 comments
32.
by cevi 3y ago
In 2017, Andrei Bulatov and Dmitriy Zhuk independently proved that every CSP template defines a problem which is either NP-complete or can be solved in polynomial time (they shared best paper at FOCS for this). However, the number of people
33.
Simplified proof of the Constraint Satisfaction Problem Dichotomy Conjecture(arxiv.org)
1 points by cevi 3y ago|1 comments
34.
by cevi 3y ago
evince recently added some features that I now find it hard to live without. The biggest is that if I mouseover an internal link in a pdf, it shows a little preview of where that link would take me - so if I'm reading a long document a
35.
by cevi 3y ago
I've been reading it over the past few days (picked it up after seeing it mentioned here). It's fantastic, much better than many similar attempts to make quantum field theory comprehensible to mathematicians.
36.
by cevi 3y ago
In practice, even storing the matrices that show up in the problem formulation can be prohibitive, let alone running a solver. Often you need to take advantage of sparsity in a nontrivial way (see e.g. COSMO [1]), or take advantage of cases
37.
by cevi 3y ago
This isn't exactly from a reputable institution, but I have a personal website with book recommendations: https://notzeb.com/rec.html (not having much money is no obstacle to reading books on math, so long as you are a
38.
by cevi 3y ago
I once used the hashlife algorithm to analyze the win/loss pattern of a game which I couldn't find any other way to analyze directly [1]. Of course, this is an application of cellular automata to a different sort of hobbyist mathe
39.
by cevi 3y ago
Watrous's notes are the best resource I know for learning quantum computing: https://cs.uwaterloo.ca/~watrous/QC-notes/QC-notes.pdf
40.
by cevi 3y ago
This may only be tangentially related, but you might be interested in the recent research on Qualitative Constraint Satisfaction Problems - a good introduction to the topic is Manuel Bodirsky's habilitation thesis [1]. The purpose of t
41.
by cevi 3y ago
At first, the results claimed here seem to clash with the fact that we know, for instance, that it is NP-hard to 5-color a graph which is promised to be 3-colorable [1]. Of course, the devil is in the details - on page 11, where they descri
42.
by cevi 3y ago
This may be a bit on the theoretical side, but it's the best reference for quickly getting up to speed on how quantum computing and entanglement works that I know of: https://cs.uwaterloo.ca/~watrous/QC-notes/
43.
by cevi 3y ago
Yes. You need spend a lot more time thinking about each line of a math proof than you do about each line of code you write, and you need to develop skills and techniques for catching and correcting errors. Your ability to catch errors tends
44.
by cevi 3y ago
This paper is a very good advertisement for Krohn-Rhodes theory, which shows how automata decompose into simpler automata. I think it's a somewhat obscure topic within math (among people who aren't semigroup theorists), so I was h
45.
by cevi 3y ago
For systems of polynomial inequalities, the appropriate tool is Cylindrical Algebraic Decomposition (this tool generalizes to systems of exponential inequalities as well).
46.
by cevi 4y ago
Thanks - I hadn't looked into Metamath Zero before, but it sounds like that would be the right thing to compare Abstraction Logic to! Skimming https://arxiv.org/abs/1910.10703 makes it seem like Metamath Zero stil
47.
by cevi 4y ago
How does your system compare to Metamath[0], aside from the obvious difference of not having set theory baked in? I notice both your Abstraction Logic and Metamath's system can state the induction axiom scheme as a single statement, wh
48.
by cevi 4y ago
Completely agree, speaking as a mathematician who put in the time to understand the details of sigma-algebras. It's an implementation detail. We don't need to talk about inductors and MOSFETs to describe how bubble-sort works, and
49.
by cevi 4y ago
A few immediately come to mind: 1. Winning Ways for Your Mathematical Plays 2. A Singular Mathematical Promenade, available for free online: https://perso.ens-lyon.fr/ghys/promenade/ There are many other math book
50.
by cevi 4y ago
I think this comes down to a disagreement about the definition of the words "local" and "non-local". There is a version of "locality" that is based on classical mechanics and classical probability - this versio
51.
by cevi 4y ago
If anyone wants to crank the difficulty up to 11, I suggest the puzzle types "Towers" and "Unequal" at max size/difficulty. These puzzles can get hard much faster than they have any right to - I play them whenever I
52.
by cevi 4y ago
The solution to the Dichotomy Conjecture for Constraint Satisfaction Problems [1] (also [2], but this proof is much more difficult). This gives a clear dividing line between the types of problems that are easy to solve exactly and the types
53.
by cevi 4y ago
My understanding is that we currently don't have enough data to be sure that the B meson anomaly is real, and not just a statistical fluctuation - it is only a few standard deviations away from what is expected. (A few more years of da
54.
by cevi 4y ago
There's the classic "Believing the Axioms" by Penelope Maddy [0] [1], the excellent study guide "Teach Yourself Logic" [2], plenty of great articles on the Stanford Encyclopedia of Philosophy (e.g. [3] or [4]), Dana
55.
by cevi 4y ago
Being a https://en.wikipedia.org/wiki/Perfect_graph is not monotonic under adding edges, and it's certainly an interesting property for a graph to have! (But yes, most interesting properties are monotonic under ad
56.
by cevi 4y ago
https://blngcc.files.wordpress.com/2008/11/viktor-prasolov-p...
57.
by cevi 5y ago
https://notzeb.com/ This used to be my personal academic website, but I'm no longer in academia so I recently had to figure out a new hosting solution. (Not much to see if you don't enjoy math or puzzle-solving.)
58.
by cevi 5y ago
Agreed on all counts.
59.
by cevi 5y ago
I don't know any reference for this - it's something I worked out after hearing about Phistomefel's Theorem from a friend. The idea goes like this: The standard Linear Programming relaxation of the constraint "the nine v
60.
by cevi 5y ago
Phistomefel’s Theorem (and the more general "set equivalence theory" described in the article) pops out directly from a standard technique known as the "Linear Programming relaxation" for Sudoku. Essentially, the Linear

More ›