As semiconductor scaling leads to high-density nanoscale computing fabrics, reconfigurable computing shows promise due to design flexibility, post-manufacturing programmability and fault-tolerance. Traditional CMOS FPGA fabrics have order of magnitude inefficiencies in power, performance and density due to emulated logic and interconnect reconfigurability with look-up tables. This calls for new paradigms enabled by emerging nano-materials, devices and physical phenomena. Our research explores two possible directions: a programmable nanowire crossbar fabric, which relies on both conventional and emerging manufacturing techniques for near-term realization and novel concepts for nanoscale circuit realization and thermal management; the other direction stems from the motivation to curb power-density issues by using electron spin as an alternate state variable for computation instead of charge transport. Our programmable nanowire fabric uses new circuit paradigms with uniform grid-based layout for high density. Fine-grained reconfigurability is achieved through programmable transistors at nanowire cross-points, which provides an opportunity for low-power reconfigurable ICs without emulation. A novel aspect is the built-in thermal management with an integrated graphene-based thermal network. The second direction is based on the spin-wave functions logic paradigm, programmable through non-volatile magneto-electric cells. It presents a unique opportunity to realize ultra low-power reconfigurable non-volatile fabrics with very high fan-in capability.