Arie Matsliah - Manuscripts

Conference proceedings:

On the power of conditional samples in distribution testing IC3-guided abstraction Computing interpolants without proofs Relating proof complexity measures and practical hardness of SAT On Efficient Computation of Variable MUSes Perfect Hashing and CNF Encodings of Cardinality Constraints Junto-symmetric functions, hypergraph isomorphism, and crunching Incremental Formal Verification of Hardware Efficient Sample Extractors for Juntas with Applications Detecting and Exploiting Near-Sortedness for Efficient Relational Query Evaluation Nearly Tight Bounds on Testing Function Isomorphism Cycle Detection, Order Finding and Discrete Log with Jumps Query Complexity Lower Bounds for Reconstruction of Codes New Results on Quantum Property Testing Monotonicity Testing and Shortest-Path Routing on the Cube Hardness and Algorithms for Rainbow Connectivity Sound 3-Query PCPPs Are Long On the Query Complexity of Testing for Eulerian Orientations Approximate Hypergraph Partitioning and Applications Underapproximation for Model-Checking Based on Universal Circuits Testing ST connectivity Testing Graph Isomorphism On the Complexity of Physical Problems and a Swarm Algorithm for $k$-Clique Search in Physical Graphs

Journal publications:

Nearly tight bounds on testing function isomorphism Learning Parities in the Mistake-Bound Model Monotonicity Testing and Shortest-Path Routing on the Cube Hardness and Algorithms for Rainbow Connectivity Approximate Hypergraph Partitioning and Applications On the Query Complexity of Testing for Eulerian Orientations Underapproximation for Model-Checking Based on Universal Circuits Sound 3-Query PCPPs Are Long Testing Graph Isomorphism

Ph.D. thesis:

Property Testing and Combinatorial Approximation


Copyrights:*

Almost without exception, all publications are the copyright of the journal and/or proceeding publishers in which they appeared (and posting the versions here is within the generally acceptable practice for published articles). One notable exception is the open-content Theory of Computing journal that does not require a copyright transfer.
* Even this disclaimer itself is not mine - it was copied from Eldar Fischer's homepage


eXTReMe Tracker