What does "All deadlines are: 11:59 PM UTC-12:00" mean?
"UTC-12" is a timezone 12 hours behind Coordinated Universal Time, which is (more or less) the time in Greenwich, UK. Nobody actually lives there, though.
A day is 24 hours, and the Earth is divided into 27 major timezones from UTC-12 to UTC+141, with the UK in the middle(ish). Therefore, someone in UTC-12 is the very last person to reach a time. At the time it is 12:01 AM UTC-12, it's 12:01 PM UTC+0, and 11:01 PM UTC+11.
So by setting the submission deadline to 11:59 PM UTC-12 on a given day, it ensures that anyone anywhere in the world who submits on the appropriate day will be on time. Hence, "anywhere on Earth."
New York is UTC-4 during the summer, which means the deadline is 7:59 AM the following day.
1: It would seem like only 24 timezones would be necessary, but a few regions chose to move to UTC+13 and UTC+14 for their own reasons. Someone in UTC+13 is 25 hours ahead of UTC-12 (so 1:01 AM the next day). The details aren't important, but in case you'd like to do your own reading.
UTC-12 means that it's 12 hours behind UTC. That's the maximum distance in our 24 hour day clock. So UTC-12 is the timezone where calendars end.
That's probably the motivation behind using it as a deadline. For example, if the deadline is January 31st UTC-12, then as soon as it's not January anymore anywhere, the deadline has passed.
Is UTC-12 the same as AoE ("Anywhere on Earth")?
AoE could be interpreted to apply daylight savings time. UTC never applies daylight savings time.
Since UTC-12:00 is the westernmost/'latest' timezone on Earth, this is indeed another way to denote 'Anywhere on Earth'.
Eastern Standard Time (EST) is not used in New York on July 1st; instead, they use Eastern Daylight Time which is UTC-04:00, so July 1st 11:59PM UTC-12:00 is July 2nd 7:59AM EDT.