I'm going to agree with it being the GPU. The dGPU on my late 2011 MBP failed recently and had the logic board replaced under their quality assurance program which I believe covers you for 5 years from the date of purchase for that particular fault.
Anyway, after the first repair I started having similar issues to you. Kernel panics, random restarts or just locking up completely. Took it to Apple yesterday and they said thats what it is, so off for another Logic board.
Edit: Sorry as pointed out it is covered till the end of this year.