You can write an intent filter and then write a broadcast receiver from where you can start your app.
All this is okay but there is one weird problem. After installing this app you need to start it at least once before it actually starts automatically on BOOT_COMPLETED.
If you just install and think that on reboot it will start automatically. Not gonna happen.