undo a master-slave wall switch
It's hard to be certain exactly how your existing wiring is working.  It looks like the upstairs switch is just switching the hot feed to the downstairs switch.  (But looking at the white wires, it appears to be switching something else too.  Very odd.  Does the upstairs switch turn off more than one thing?) 

However, I think I can answer the question, "Can I make the switches operate independently without running new wires?" :  Probably not. What you want is a 3-way switch setup between the two switches, and it appears you only have a single conductor connecting the two switches.  You'd need additional conductors between the switches in order to install a three way configuration.  Sorry.