Search results for "PCPs"

Hits ?▲	Authors	Title	Venue	Year	Link	Author keywords
146	Eli Ben-Sasson, Oded Goldreich 0001, Prahladh Harsha, Madhu Sudan 0001, Salil P. Vadhan	Robust pcps of proximity, shorter pcps and applications to coding.	STOC	2004	DBLP DOI BibTeX RDF	property testing, probabilistically checkable proofs, PCP, locally decodable codes, locally testable codes
102	Jorik Blaas, Charl P. Botha, Frits H. Post	Extensions of Parallel Coordinates for Interactive Exploration of Large Multi-Timepoint Data Sets.	IEEE Trans. Vis. Comput. Graph.	2008	DBLP DOI BibTeX RDF
102	Yael Tauman Kalai, Ran Raz	Interactive PCP.	ICALP (2)	2008	DBLP DOI BibTeX RDF
90	Oded Goldreich 0001, Madhu Sudan 0001	Locally testable codes and PCPs of almost-linear length.	J. ACM	2006	DBLP DOI BibTeX RDF	error-correcting codes, derandomization, probabilistically checkable proofs, Proof verification
90	Eli Ben-Sasson, Madhu Sudan 0001	Simple PCPs with poly-log rate and query complexity.	STOC	2005	DBLP DOI BibTeX RDF	PCPP, probabilistically checkable proofs, PCP, locally testable codes
90	Venkatesan Guruswami, Daniel Lewin 0001, Madhu Sudan 0001, Luca Trevisan	A Tight Characterization of NP with 3 Query PCPs.	FOCS	1998	DBLP DOI BibTeX RDF	Probabilistically Checkable Proofs (PCP), Proof composition, Two-prover one-round proof systems, Adaptive and non-adaptive verifiers, Completeness and soundness, Complexity Theory, Query complexity
73	Oded Goldreich 0001, Madhu Sudan 0001	Locally Testable Codes and PCPs of Almost-Linear Length.	FOCS	2002	DBLP DOI BibTeX RDF
68	Venkatesan Guruswami	On 2-Query Codeword Testing with Near-Perfect Completeness.	ISAAC	2006	DBLP DOI BibTeX RDF
66	Lance Fortnow, Rahul Santhanam	Infeasibility of instance compression and succinct PCPs for NP.	STOC	2008	DBLP DOI BibTeX RDF	instance compression, succinct PCPs, cryptography, parameterized complexity, polynomial hierarchy
56	Russell Impagliazzo, Valentine Kabanets, Avi Wigderson	New direct-product testers and 2-query PCPs.	STOC	2009	DBLP DOI BibTeX RDF	testing, PCP, parallel repetition, direct products
56	Lars Engebretsen, Jonas Holmerin	Three-Query PCPs with Perfect Completeness over non-Boolean Domains.	CCC	2003	DBLP DOI BibTeX RDF
51	Irit Dinur	The PCP theorem by gap amplification.	J. ACM	2007	DBLP DOI BibTeX RDF	Gap amplification, PCP
51	Dana Moshkovitz, Ran Raz	Sub-constant error low degree test of almost-linear size.	STOC	2006	DBLP DOI BibTeX RDF	plane vs. point test, probabilistically checkable proofs, locally testable codes, low degree testing
51	Jen-Shun Yang, Chien-Chao Tseng, Ray-Guang Cheng	A Signal-to-Interference Ratio Based Downlink Scheduling Scheme for WCDMA Mobile Communication System.	AINA	2005	DBLP DOI BibTeX RDF
51	Johan Håstad	Which NP-Hard Optimization Problems Admit Non-trivial Efficient Approximation Algorithms?	ICALP	2000	DBLP DOI BibTeX RDF
49	Sanjeev Arora	Reductions, Codes, PCPs, and Inapproximability.	FOCS	1995	DBLP DOI BibTeX RDF	NP-hard functions, code-like Levin reduction, complexity assumption, positive fraction, 3-colorable graph, code-like reduction, computational complexity, graph theory, error correction codes, error-correcting codes, NP-hardness, codes, inapproximability, PCPs, hardness, approximation ratio
49	Mihir Bellare, Oded Goldreich 0001, Madhu Sudan 0001	Free Bits, PCPs and Non-Approximability - Towards Tight Results.	FOCS	1995	DBLP DOI BibTeX RDF	free bits, logarithmic randomness, amortized free bits, Max Clique, Max-2-SAT, FGLSS connection, amortized free-bit complexity, amortized free bit complexity, FPCP parameters, triviality results, computational complexity, computational geometry, theorem proving, NP-hardness, NP complete problems, proof systems, chromatic number, PCPs, Max-cut, nonapproximability
44	Irit Dinur, Prahladh Harsha	Composition of Low-Error 2-Query PCPs Using Decodable PCPs.	SIAM J. Comput.	2013	DBLP DOI BibTeX RDF
44	Irit Dinur, Prahladh Harsha	Composition of Low-Error 2-Query PCPs Using Decodable PCPs.	Property Testing	2010	DBLP DOI BibTeX RDF
44	Irit Dinur, Prahladh Harsha	Composition of low-error 2-query PCPs using decodable PCPs.	Electron. Colloquium Comput. Complex.	2009	DBLP BibTeX RDF
44	Irit Dinur, Prahladh Harsha	Composition of Low-Error 2-Query PCPs Using Decodable PCPs.	FOCS	2009	DBLP DOI BibTeX RDF	locally decodable, low soundness error, composition, PCP
44	Eli Ben-Sasson, Oded Goldreich 0001, Prahladh Harsha, Madhu Sudan 0001, Salil P. Vadhan	Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.	SIAM J. Comput.	2006	DBLP DOI BibTeX RDF
44	Eli Ben-Sasson, Oded Goldreich 0001, Prahladh Harsha, Madhu Sudan 0001, Salil P. Vadhan	Robust PCPs of Proximity, Shorter PCPs and Applications to Coding	Electron. Colloquium Comput. Complex.	2004	DBLP BibTeX RDF
39	Irit Dinur	PCPs with small soundness error.	SIGACT News	2008	DBLP DOI BibTeX RDF
39	Eli Ben-Sasson, Oded Goldreich 0001, Prahladh Harsha, Madhu Sudan 0001, Salil P. Vadhan	Short PCPs Verifiable in Polylogarithmic Time.	CCC	2005	DBLP DOI BibTeX RDF
39	Eli Ben-Sasson, Madhu Sudan 0001, Salil P. Vadhan, Avi Wigderson	Randomness-efficient low degree tests and short PCPs via epsilon-biased sets.	STOC	2003	DBLP DOI BibTeX RDF	property testing, probabilistically checkable proofs, locally testable codes, linearity testing, low degree testing
39	Prahladh Harsha, Madhu Sudan 0001	Small PCPs with Low Query Complexity.	STACS	2001	DBLP DOI BibTeX RDF
34	Li Yan, Sunwoo Park, Shahab Sheikh-Bahaei, Glen E. P. Ropella, C. Anthony Hunt	Predicting hepatic disposition properties of cationic drugs using a physiologically based, agent-oriented In Silico Liver.	SpringSim	2008	DBLP DOI BibTeX RDF	drug disposition, hepatic, mechanistic, physiologically-based, prediction, systems biology, agent oriented
34	Subhash Khot	On the power of unique 2-prover 1-round games.	STOC	2002	DBLP DOI BibTeX RDF
34	Subhash Khot	On the Power of Unique 2-Prover 1-Round Games.	CCC	2002	DBLP DOI BibTeX RDF	2-prover games, Hardness of approximation, probabilistically checkable proofs
34	Ian Agol, Joel Hass, William P. Thurston	3-MANIFOLD KNOT GENUS is NP-complete.	CCC	2002	DBLP DOI BibTeX RDF	2-prover games, Hardness of approximation, probabilistically checkable proofs
34	Joe Kilian	Improved Efficient Arguments (Preliminary Version).	CRYPTO	1995	DBLP DOI BibTeX RDF
27	Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu 0002	Agnostic Learning of Monomials by Halfspaces Is Hard.	FOCS	2009	DBLP DOI BibTeX RDF	Hardness of Learning, Dictatorship Tests, PCPs, Agnostic Learning
27	Or Meir	Combinatorial construction of locally testable codes.	STOC	2008	DBLP DOI BibTeX RDF	pcps of proximity, probabilistically checkable proofs, locally testable codes
27	Offer Shai, Daniel Rubin	Representing and analysing integrated engineering systems through combinatorial representations.	Eng. Comput.	2004	DBLP DOI BibTeX RDF	Abbreviations CR Combinatorial Representations, FCFS Flow Controlled Flow Source, FCPS Flow Controlled Potential difference Source, FGR Flow Graph Representation, MCA Multidisciplinary Combinatorial Approach, PCFS Potential difference Controlled Flow Source, PCPS Potential difference Controlled Potential difference Source, PGR Potential Graph Representation, RGR Resistance Graph Representation
27	Jonas Holmerin, Subhash Khot	A new PCP outer verifier with applications to homogeneous linear equations and max-bisection.	STOC	2004	DBLP DOI BibTeX RDF	max-bisection, hardness of approximation, linear equations, PCPs
22	Dor Minzer, Kai Zhe Zheng	Near Optimal Alphabet-Soundness Tradeoff PCPs.	Electron. Colloquium Comput. Complex.	2024	DBLP BibTeX RDF
22	Tom Gur, Jack O'Connor, Nicholas Spooner	Perfect Zero-Knowledge PCPs for #P.	CoRR	2024	DBLP DOI BibTeX RDF
22	Harry Buhrman, Jonas Helsen, Jordi Weggemans	Quantum PCPs: on Adaptivity, Multiple Provers and Reductions to Local Hamiltonians.	CoRR	2024	DBLP DOI BibTeX RDF
22	Tom Gur, Jack O'Connor, Nicholas Spooner	Perfect Zero-Knowledge PCPs for #P.	IACR Cryptol. ePrint Arch.	2024	DBLP BibTeX RDF
22	Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal	Rigid Matrices from Rectangular PCPs.	SIAM J. Comput.	2024	DBLP DOI BibTeX RDF
22	Alessandro Chiesa, Ziyi Guan, Burcu Yildiz	On Parallel Repetition of PCPs.	ITCS	2024	DBLP DOI BibTeX RDF
22	Dani Kiyasseh, Tingting Zhu 0001, David A. Clifton	PCPs: Patient Cardiac Prototypes to Probe AI-based Medical Diagnoses, Distill Datasets, and Retrieve Patients.	Trans. Mach. Learn. Res.	2023	DBLP BibTeX RDF
22	Susumu Kiyoshima	No-Signaling Linear PCPs.	J. Cryptol.	2023	DBLP DOI BibTeX RDF
22	Alessandro Chiesa, Ziyi Guan, Burcu Yildiz	On Parallel Repetition of PCPs.	IACR Cryptol. ePrint Arch.	2023	DBLP BibTeX RDF
22	Shuichi Hirahara, Dana Moshkovitz	Regularization of Low Error PCPs and an Application to MCSP.	ISAAC	2023	DBLP DOI BibTeX RDF
22	Joshua Cook, Dana Moshkovitz	Tighter MA/1 Circuit Lower Bounds from Verifier Efficient PCPs for PSPACE.	APPROX/RANDOM	2023	DBLP DOI BibTeX RDF
22	Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss	ZK-PCPs from Leakage-Resilient Secret Sharing.	J. Cryptol.	2022	DBLP DOI BibTeX RDF
22	Joshua Cook, Dana Moshkovitz	Tighter MA/1 Circuit Lower Bounds From Verifier Efficient PCPs for PSPACE.	Electron. Colloquium Comput. Complex.	2022	DBLP BibTeX RDF
22	Mor Weiss	Shielding Probabilistically Checkable Proofs: Zero-Knowledge PCPs from Leakage Resilience.	Entropy	2022	DBLP DOI BibTeX RDF
22	Mor Weiss	Shielding Probabilistically Checkable Proofs: Zero-Knowledge PCPs from Leakage Resilience.	IACR Cryptol. ePrint Arch.	2022	DBLP BibTeX RDF
22	Liron Bronfman, Ron D. Rothblum	PCPs and Instance Compression from a Cryptographic Lens.	ITCS	2022	DBLP DOI BibTeX RDF
22	Orr Paradise	Smooth and Strong PCPs.	Comput. Complex.	2021	DBLP DOI BibTeX RDF
22	Orr Paradise	Correction to: Smooth and Strong PCPs.	Comput. Complex.	2021	DBLP DOI BibTeX RDF
22	Liron Bronfman, Ron Rothblum	PCPs and Instance Compression from a Cryptographic Lens.	Electron. Colloquium Comput. Complex.	2021	DBLP BibTeX RDF
22	Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss	ZK-PCPs from Leakage-Resilient Secret Sharing.	IACR Cryptol. ePrint Arch.	2021	DBLP BibTeX RDF
22	Liron Bronfman, Ron D. Rothblum	PCPs and Instance Compression from a Cryptographic Lens.	IACR Cryptol. ePrint Arch.	2021	DBLP BibTeX RDF
22	Carmit Hazay, Muthuramakrishnan Venkitasubramaniam, Mor Weiss	ZK-PCPs from Leakage-Resilient Secret Sharing.	ITC	2021	DBLP DOI BibTeX RDF
22	Jonathan R. Ullman, Salil P. Vadhan	PCPs and the Hardness of Generating Synthetic Data.	J. Cryptol.	2020	DBLP DOI BibTeX RDF
22	Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal	Rigid Matrices From Rectangular PCPs.	Electron. Colloquium Comput. Complex.	2020	DBLP BibTeX RDF
22	Dani Kiyasseh, Tingting Zhu 0001, David A. Clifton	PCPs: Patient Cardiac Prototypes.	CoRR	2020	DBLP BibTeX RDF
22	Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal	Rigid Matrices From Rectangular PCPs.	CoRR	2020	DBLP BibTeX RDF
22	Orr Paradise	Smooth and Strong PCPs.	ITCS	2020	DBLP DOI BibTeX RDF
22	Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal	Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs.	FOCS	2020	DBLP DOI BibTeX RDF
22	Orr Paradise	Smooth and Strong PCPs.	Electron. Colloquium Comput. Complex.	2019	DBLP BibTeX RDF
22	Mitali Bafna, Nikhil Vyas 0001	Imperfect Gaps in Gap-ETH and PCPs.	CoRR	2019	DBLP BibTeX RDF
22	Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai	How to Prove a Secret: Zero-Knowledge Proofs on Distributed Data via Fully Linear PCPs.	IACR Cryptol. ePrint Arch.	2019	DBLP BibTeX RDF
22	Moni Naor, Omer Paneth, Guy N. Rothblum	Incrementally Verifiable Computation via Incremental PCPs.	IACR Cryptol. ePrint Arch.	2019	DBLP BibTeX RDF
22	Moni Naor, Omer Paneth, Guy N. Rothblum	Incrementally Verifiable Computation via Incremental PCPs.	TCC (2)	2019	DBLP DOI BibTeX RDF
22	Marta Gomez-Perosanz, Alvaro Ras-Carmona, Pedro A. Reche	Prediction of proteasomal cleavage sites using PCPS.	BIBM	2019	DBLP DOI BibTeX RDF
22	Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, Yuval Ishai	Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs.	CRYPTO (3)	2019	DBLP DOI BibTeX RDF
22	Mitali Bafna, Nikhil Vyas 0001	Imperfect Gaps in Gap-ETH and PCPs.	CCC	2019	DBLP DOI BibTeX RDF
22	Lijie Chen 0001, R. Ryan Williams	Stronger Connections Between Circuit Analysis and Circuit Lower Bounds, via PCPs of Proximity.	CCC	2019	DBLP DOI BibTeX RDF
22	Devanathan Thiruvenkatachari	Approximation algorithms, Hardness, and PCPs.		2019	RDF
22	Susumu Kiyoshima	No-signaling Linear PCPs.	IACR Cryptol. ePrint Arch.	2018	DBLP BibTeX RDF
22	Susumu Kiyoshima	No-signaling Linear PCPs.	TCC (1)	2018	DBLP DOI BibTeX RDF
22	Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, Madars Virza	Computational Integrity with a Public Random String from Quasi-Linear PCPs.	EUROCRYPT (3)	2017	DBLP DOI BibTeX RDF
22	Or Meir	Combinatorial PCPs with Short Proofs.	Comput. Complex.	2016	DBLP DOI BibTeX RDF
22	Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth	Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity.	J. ACM	2016	DBLP DOI BibTeX RDF
22	Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza	Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs.	Electron. Colloquium Comput. Complex.	2016	DBLP BibTeX RDF
22	Alex Bredariol Grilo, Iordanis Kerenidis, Attila Pereszlényi	Pointer Quantum PCPs and Multi-Prover Games.	CoRR	2016	DBLP BibTeX RDF
22	Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza	Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs.	IACR Cryptol. ePrint Arch.	2016	DBLP BibTeX RDF
22	Eli Ben-Sasson, Iddo Bentov, Alessandro Chiesa, Ariel Gabizon, Daniel Genkin, Matan Hamilis, Evgenya Pergament, Michael Riabzev, Mark Silberstein, Eran Tromer, Madars Virza	Computational integrity with a public random string from quasi-linear PCPs.	IACR Cryptol. ePrint Arch.	2016	DBLP BibTeX RDF
22	Eli Ben-Sasson, Alessandro Chiesa, Ariel Gabizon, Madars Virza	Quasi-Linear Size Zero Knowledge from Linear-Algebraic PCPs.	TCC (A2)	2016	DBLP DOI BibTeX RDF
22	Yuval Ishai, Mor Weiss, Guang Yang 0020	Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits.	TCC (A2)	2016	DBLP DOI BibTeX RDF
22	Alex Bredariol Grilo, Iordanis Kerenidis, Attila Pereszlényi	Pointer Quantum PCPs and Multi-Prover Games.	MFCS	2016	DBLP DOI BibTeX RDF
22	Irit Dinur, Prahladh Harsha, Guy Kindler	Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.	Electron. Colloquium Comput. Complex.	2015	DBLP BibTeX RDF
22	Irit Dinur, Prahladh Harsha, Guy Kindler	Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.	CoRR	2015	DBLP BibTeX RDF
22	Yuval Ishai, Mor Weiss, Guang Yang 0020	Making the Best of a Leaky Situation: Zero-Knowledge PCPs from Leakage-Resilient Circuits.	IACR Cryptol. ePrint Arch.	2015	DBLP BibTeX RDF
22	Irit Dinur, Prahladh Harsha, Guy Kindler	Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.	STOC	2015	DBLP DOI BibTeX RDF
22	Or Meir	Combinatorial PCPs with Efficient Verifiers.	Comput. Complex.	2014	DBLP DOI BibTeX RDF
22	Eli Ben-Sasson, Emanuele Viola	Short PCPs with projection queries.	Electron. Colloquium Comput. Complex.	2014	DBLP BibTeX RDF
22	Eli Ben-Sasson, Emanuele Viola	Short PCPs with Projection Queries.	ICALP (1)	2014	DBLP DOI BibTeX RDF
22	Irit Dinur, Venkatesan Guruswami	PCPs via low-degree long code and hardness for constrained hypergraph coloring.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
22	Or Meir	Combinatorial PCPs with Short Proofs.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
22	Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth	Constant rate PCPs for circuit-SAT with sublinear query complexity.	Electron. Colloquium Comput. Complex.	2013	DBLP BibTeX RDF
22	Mohammad Mahmoody, David Xiao	Languages with Efficient Zero-Knowledge PCPs are in SZK.	TCC	2013	DBLP DOI BibTeX RDF
22	Irit Dinur, Venkatesan Guruswami	PCPs via Low-Degree Long Code and Hardness for Constrained Hypergraph Coloring.	FOCS	2013	DBLP DOI BibTeX RDF
22	Eli Ben-Sasson, Yohay Kaplan, Swastik Kopparty, Or Meir, Henning Stichtenoth	Constant Rate PCPs for Circuit-SAT with Sublinear Query Complexity.	FOCS	2013	DBLP DOI BibTeX RDF
22	Rosario Gennaro, Craig Gentry, Bryan Parno, Mariana Raykova 0001	Quadratic Span Programs and Succinct NIZKs without PCPs.	EUROCRYPT	2013	DBLP DOI BibTeX RDF