Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Ce Jin:

TR23-186 | 28th November 2023
Ce Jin, Ryan Williams, Nathaniel Young

A VLSI Circuit Model Accounting For Wire Delay

Given the need for ever higher performance, and the failure of CPUs to keep providing single-threaded performance gains, engineers are increasingly turning to highly-parallel custom VLSI chips to implement expensive computations. In VLSI design, the gates and wires of a logical circuit are placed on a 2-dimensional chip with a ... more >>>

TR21-159 | 15th November 2021
Lijie Chen, Ce Jin, Rahul Santhanam, Ryan Williams

Constructive Separations and Their Consequences

For a complexity class $C$ and language $L$, a constructive separation of $L \notin C$ gives an efficient algorithm (also called a refuter) to find counterexamples (bad inputs) for every $C$-algorithm attempting to decide $L$. We study the questions: Which lower bounds can be made constructive? What are the consequences ... more >>>

ISSN 1433-8092 | Imprint